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