UNIDAD IV
"TIPOS DE GRÁFICAS ESPECIALES"
*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.
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.
*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.
*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.
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)
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.