UNIDAD IV 

"TIPOS DE GRÁFICAS ESPECIALES"

Presiona aquí para ver presentación

Robert C.Prim

*Nació en el año 1921 en Sweetwater,Estados Unidos. 

*Matemático y científico de la computación. 

*En 1941 se licenció en ingeniería eléctrica en la universidad de Princeton. 

*Trabajó en dicha universidad desde 1948 hasta 1949 como investigador asociado. 

*En los laboratorios Bell,trabajó como director de investigación matemática desde 1958 hasta 1961. Alli Prim desarrollo el conocido algoritmo de Prim que junto a su compañero Joseph Kruskal desarrollo dos algoritmos diferentes para encontrar los árboles abarcadores mínimos en un grafo ponderado.

Algoritmo de Prim 

Es un algoritmo perteneciente a la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.

El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol.

El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar.

          Pasos:

         1. Se inicia en cualquier nodo

         2. Seleccionar la arista de menor costo adyacente al nodo.

       3. Se busca la arista de menor costo de los nodos ya analizados adyacente 

         que no genere  circuitos. 

INFORMACIÓN

Wikipedia(2010).Robert C.Prim.20 Abril 2015.Wikimedia Fundation.Inc sitio web:

http://es.wikipedia.org/wiki/Robert_C._Prim

Wikipedia(2009).Algoritmo.Prim.20 Abril 2015.Wikimedia Fundation.Inc sitio web:

http://es.wikipedia.org/wiki/Algoritmo_de_Prim

IMAGEN

Robert C.Prim recuperado de:

https://www.google.com.mx/search?q=Robert+C+prim

Algoritmo de Prim recuperado de:

https://www.google.com.mx/search?q=Algoritmo+de+Robert+C+prim

Joseph Kruskal

*Nació el 29 de Enero de 1928 en Maplewood,Nueva Jersey.
*Murió el el 19 de Septiembre de 2010.
*Fue un matemático y estadístico estadounidense.

*Fue hermano del matemático y estadístico William Kruskal y del matemático-fisico Martín Kruskal (autor de las coordenadas de Kruskal) 

*En 1956 descubrió un algoritmo para la resolución del problema del árbol recubridor mínimo. 

*El objetivo del algoritmo de Kruskal es construir un árbol(subgrafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.

Algoritmo de Kruskal 

Es un algoritmo de la teoria de grafos  para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado.

Funciona de la siguiente manera:

• Se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado.

• Se crea un conjunto C que contenga a todas las aristas del grafo.

• Mientras C es no vacío.

• Eliminar una arista de peso mínimo de C.

• Si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol.

• En caso contrario, se desecha la arista.

Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo. 

 

INFORMACIÓN

Wikipedia(2009).Joseph.Kruskal.20 Abril 2015.Wikimedia Fundation.Inc sitio web:

http://es.wikipedia.org/wiki/Joseph_Kruskal

Wikipedia(2009).Algoritmo Kruskal.20 Abril 2015.Wikimedia Fundation.Inc sitio web:

http://es.wikipedia.org/wiki/Algoritmo_de_Kruskal

IMAGEN

Joseph Kruskal recuperado de:

https://www.google.com.mx/search?q=joseph+kruska

Algoritmo de Kruskal recuperado de:

https://www.google.com.mx/search?q=algoritmo+de+kruskal

 

Philip Hall

*Nació el 11 de Abril de 1904 en Londres,Inglaterra.

*Murió el 30 de Diciembre de 1982 en Cambrige,Inglaterra.

*Fue un matemático británico . 

*Fue profesor de matemática pura en la universidad de Cambrige de 1953 a 1967. 

*Su área de interés fue la teoría de dos grupos y combinatoria. 

*Fue galardonado en 1961 por la Royal Society.

Teorema del matrimonio

Sea G=(V,E) un grafo bipartido con V divido como V1uV2.Existe un emparejamiento completo de V1 en V2 si y sólo si para cada subconjunto A de V1, |A|≤|R(A)| donde R(A) es el subconjunto de V2 que consta de los vértices adyacentes al menos a un vertice de A.Al número de elementos de A se le llama cardinalidad y se denota con |A|La deficiencia se denota por (A)= |A|- |R(A)|Se dice que A es no deficiente si (A) es cero o negativo con respecto a R(A) (Existe emparejamiento completo)

INFORMACIÓN

Wikipedia.(2010).Philip. Hall.20 Abril 2015,de Wikimedia Foundation,Inc sitio web:
http://En.wikipedia.org/wikis/Philip .Hall.

IMAGEN

Philip Hall recuperado de:

https://www.google.com.mx/search?q=philip+hall

Tarea III "Conectividad"

Presiona aquí para ver presentación

Palabra Clave "Unidad II"

Matriz Incidencia para una gráfica

Para obtener la matriz de incidencia de una gráfica: 

*Se etiquetan los renglones con los vértices y las columnas con las aristas  

*La entrada del renglón v y la columna e es: 

1 si e es incidente en v

0 en caso contrario

*La matriz de incidencia nos permite representar las aristas paralelas y los lazos.

*La suma de los elementos de un renglón representa el grado 

del vértice identificado con ese renglón.

Información recuperada de:

http://www.dspace.espol.edu.ec/retrieve/2767/DMD5_teoria_de_graficas.pdf.

Imagen recuperada de:

https://www.google.com.mx/search?q=matriz+incidencia

Palabra Clave "Unidad I"

Gráfica Completa

En teoría de Gráficas un grafo o gráfica completa es un grafo simple donde cada par de vértices está conectado por una arista.

Un grafo completo de n vértices tiene n(n-1)/2 aristas,y se denota como Kn. 

Es un grafo regular con todos sus vértices de grado n-1.

Ningún grafo completo tiene lazos y está conectado totalmente ,por ende,la única forma de hacer disconexo el grafo con una eliminación de vértices es aplicarla a todos.

Ejemplos:

Información

http://es.slideshare.net/lawiz_witinea/grafos-8357081

Imagen

Grafo completo recuperado de 

https://www.google.com.mx/search?q=grafo+completo

 Unidad 1 "Introducción a la Teoría de Gráficas" (Mapa mental)

Referencias de las imágenes:

"Grafo simple", imagen recuperada de 

https://www.google.com.mx/search?q=grafica+simple+teoria+de+grafos

"Gráfica Bipartida" ,imagen recuperada de

https://www.google.com.mx/search?q=+teoria+de+graficas+grafica+bipartida

"Bosque", imagen recuperada de

https://www.google.com.mx/search?isch&q=teoria+de+graficas+bosque

"Multigráfo" ,imagen recuperada de

https://www.google.com.mx/search?q=teoria+de+graficas+multigrafo&img

"Lema del Apretón de manos",imagen recuperada de

https://www.google.com.mx/search?q=teoria+de+graficas+lema+del+apreton+de+manos

"Línea dirigida" ,imagen recuperada de

https://www.google.com.mx/search?qq=teoria+de+graficas+linea+dirigida

"Línea no dirigida", imagen recuperada de

https://www.google.com.mx/search?q=teoria+de+graficas+linea+no+dirigida

"Bucles", imagen recuperada de

https://www.google.com.mx/search?q=teoria+de+graficas+lineas+bucles

"Nodo colgante", imagen recuperada de 

https://www.google.com.mx/search?q=teoria+de+graficas+nodos+colgantes

"Paseo", imagen recuperada de

https://www.google.com.mx/search?q=teoria+de+graficas+paseo

                                                      
                                                Biografía de Václav Havel

Matemático checo, especializado en teoría de grafos, cuyo trabajo más importante es la resolución del problema de la secuencia de enteros gráfica en 1955, resuelta independientemente por Hakimi en 1962.

El problema de la secuencia de enteros gráfica consiste en determinar si una secuencia de enteros no negativos cualquiera es o no gráfica, es decir, es una secuencia de grados de un grafo. Havel publica en 1955 el paper Poznámka o existenci konečných grafů  en la revista de matemática checa Časopis pro pěstování matematiky donde da solución al problema a través del siguiente teorema:

Teorema de Havel-Hakimi

Una secuencia de enteros  es gráfica sí, y sólo sí también lo es la lista: , que resulta de eliminar el primer elemento y restar una unidad a los siguientes  valores de la lista.

Publicó alrededor de 90 artículos matemáticos entre los años 1955 y 1994, siendo uno de los primeros «Harmonical quadruplet in Moufang plane» en la revista Czechoslovak Mathematical Journal y el último: «Kdo poprvé užil ve fyzice delta funkci?» (Who first used the delta-function in physics?) en la revista Pokroky matematiky, fyziky a astronomie.

INFORMACION
Wikipedia.(2010).Vaclav J.Havel.20 February 2015,de Wikimedia Foundation,Inc sitio web:
http://En.wikipedia.org/wikis/Vaclav .J.Havel.

IMAGEN
Vaclav J.Havel Recuperado de:
http://felixjtapia.org/blog/2013/12/13/las-tentaciones-del-poder-por-vaclav-havel/

Algoritmo de  Havel-Hakimi

*Pasos del Algoritmo de  Havel-Hakimi:

-Sucesión decreciente de enteros no negativos.

-Se elimina el primer numero de la lista,es decir s.

-Se resta una unidad a los siguientes valores comprendidos entre t1 y df.

-Si alguno de los valores resulta negativo entonces quiere decir que el grafo no existe por lo tanto la sucesión no es gráfica.

-Se conecta en el grafo el vértice asociado a s con los vértices asociados a t1,t2,...,ts por medio de aristas.
En caso de que la lista no sea decreciente,se re ordenara sin confundir los nombres de los vértices.

-Se repite el paso 2 hasta que no queden números en la lista.

*Resuelve si la siguiente es una sucesión gráfica(5,5,4,4,3,2,1,1).

Esta sucesión no es gráfica puesto que es impar tomando en cuenta que el Lema del apretón de manos nos dice que "El numero de grados en una gráfica sin bucles debe ser par".