Matemáticas Discretas: Teoría de Graficas y Arboles

Mundo de las matemáticas

Teoría de graficas

4.5 Grafos de Similaridad

Estos surgen a partir de los grafos isomorfos con la diferencia de que entre cada adyacencia e incidencia deben tener la misma distancia entre cada vértice.

Por ejemplo.

Observando los grafos isomorfos vemos que ambos tienen la misma distancia entre cada uno de los vértices siendo así dos grafos similares en el caso contrario, aunque sean isomorfos si alguno de los grafos tiene una distancia diferente en uno de sus vértices ya no sería similares el cual es el caso contrario.

Ejercicio 1.

El siguiente ejercicio trata de agrupar objetos similares en clases basadas en las propiedades de los objetos. Suponga que cierto número de personas implementan en c++ un algoritmo dado y que se quiere agrupar los programas parecidos en clases determinadas por ciertas propiedades de los programas, como los siguientes...

1. El número de líneas en el programa.
2. El número de instrucciones para regresar(return).
3. El número de llamadas de funciones en el programa.

PROGRAMA	# DE LINEAS EN EL PROGRAMA	# DE INTRUCCIONES RETURN	# DE LLAMADAS DE FUNCIONES
1	66	20	1
2	41	10	2
3	68	5	8
4	90	34	5
5	75	12	14

En donde cada programa es un vértice y el grado de singularidad se da por: 

S(u, w) = (|p1-p2|) + (|p2-p3|) + (|p3-p4|) +...

La singularidad es dependiendo del rango que se le dé, por ejemplo:

S=25         S (U, V) <= 25

Entonces nuestro grafo y rango queda de la siguiente forma:

Quedando de esta forma debido a que solo se toman en cuenta las sustituciones que son menores o iguales al rango dado dejándonos la siguiente denotación:

para S (U, V) <= 25 es {v1, v3, v5}

A continuación, un video para una mejor comprensión:

4.6 Grafos Bipartidos

Un grafo bipartito es un grafo cuyos vértices se pueden dividir en dos conjuntos disjuntos e independientes U y V, es decir, cada arista conecta un vértice en U uno en V. Los conjuntos de vértices U y V generalmente se denominan partes del gráfico. De manera equivalente, un gráfico bipartito es un gráfico que no contiene ciclos de longitud impar.

Los dos conjuntos pueden considerarse como una coloración del gráfico con dos colores: si uno colorea todos los nodos en U azul y todos los nodos en verde, cada borde tiene extremos de diferentes colores, como se requiere en el problema de coloración del gráfico. En cambio, tal coloración es imposible en el caso de un grafo no bipartito, como un triángulo: después de que un nodo se colorea de azul y otro de verde, el tercer vértice del triángulo se conecta a vértices de ambos colores, impidiendo que siendo asignado cualquiera de los dos colores. VUV

A menudo se escribe G = (U, V, E) para denotar un gráfico bipartito cuya partición tiene las partes U y V, E denotando los bordes del gráfico. Si un gráfico bipartito no está conectado, puede tener más de una bipartición; en este caso, la (U, V, E) notación es útil para especificar una bipartición particular que puede ser importante en una aplicación. Si |U| = | V|, es decir, si los dos subconjuntos tienen la misma cardinalidad, entonces G se llama un gráfico bipartito balanceado. Si todos los vértices del mismo lado de la bipartición tienen el mismo grado, entonces G se llama biregular.

Los gráficos bipartitos se pueden caracterizar de varias maneras diferentes:

• Un grafo es bipartito si y solo si no contiene un ciclo impar.
• Un grafo es bipartito si y sólo si es bicoloreable (es decir, su número cromático es menor o igual a 2).
• Un grafo es bipartito si y solo si cada arista pertenece a un número impar de enlaces, subconjuntos mínimos de aristas cuya eliminación aumenta el número de componentes del grafo.
• Un grafo es bipartito si y solo si el espectro del grafo es simétrico.

4.7 Representación de graficas

Existen diferentes formas de representar un grafo (simple), además de la geométrica y muchos métodos para almacenarlos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas

4.7.1 Matrices

Una matriz es una representación de la relación entre dos conjuntos de elementos mediante una matriz binaria compuesta por ceros "0" o unos "1". Para comprender mejor su estructura, consideremos dos clases: X y Y. La matriz se organiza de tal manera que cada fila corresponde a un elemento del conjunto X, mientras que cada columna representa un elemento del conjunto Y. Así, la matriz se compone de filas y columnas que cruzan estos dos conjuntos.

4.7.1.1 De incidencia

 La matriz de incidencia es una matriz de tipo lógica y establece una conexión inequívoca entre los conjuntos. A los cuartiles que representan la relación entre los elementos de los conjuntos se les denomina relación de incidencia.

En el cruce de una fila n de X con una columna m de Y, encontramos un valor clave: si este valor es 1, indica que el elemento n del conjunto X está relacionado o incide con el elemento m del conjunto Y. Por el contrario, un valor 0 en esta intersección señala que no existe tal relación o incidencia entre los elementos n y m.

Este concepto es fundamental para las matemáticas en general, ya que una matriz de incidencia es una herramienta matemática versátil y efectiva para representar y analizar las relaciones entre dos conjuntos de elementos.

4.7.1.2 De adyacencia

Una matriz de adyacencia es una matriz cuadrada utilizada para representar un gráfico finito. Los elementos de la matriz indican si los pares de vértices son adyacentes o no en el gráfico.

En el caso especial de un gráfico simple finito, la matriz de adyacencia es una matriz (0,1) con ceros en su diagonal. Si el gráfico no está dirigido (es decir, todos sus bordes son bidireccionales), la matriz de adyacencia es simétrica. La relación entre un gráfico y los valores propios y los vectores propios de su matriz de adyacencia se estudia en la teoría de gráficos espectrales.

La matriz de adyacencia de un grafo debe distinguirse de su matriz de incidencia, una representación de matriz diferente cuyos elementos indican si los pares vértice-arista son incidentes o no, y su matriz de grado, que contiene información sobre el grado de cada vértice.

Ejercicio 1

4.8 Caminos de circuitos

En un grafo se puede recorrer la información de diferentes maneras para llegar de un punto a otro.

4.8.1 Longitud de un camino

 La longitud de un camino es su número de aristas. Así, en un grafo no dirigido, los vértices adyacentes están conectados por un camino de longitud 1, los segundos vecinos por un camino de longitud 2, y así sucesivamente. Un grafo no dirigido es conexo si todos sus vértices están conectados a través de un camino.​ Un grafo conexo cuyos vértices y aristas permiten definir un camino es un grafo camino.

4.8.2 Algoritmo del camino más corto

Cuando se trabaja con grafos dirigidos etiquetados o ponderados con factores de peso no negativos, es frecuente buscar el camino más corto entre dos vértices dados; es decir, el camino que nos permita llegar desde un vértice origen a un vértice destino recorriendo la menor distancia o con el menor costo. Los algoritmos más usados para este fin son: Dijkstra, Floyd y Warshall. Los tres algoritmos utilizan una matriz de adyacencia ponderada o etiquetada: que es la misma matriz de adyacencia utilizada para representar grafos, pero con la diferencia que en lugar de colocar un número “1” cuando dos vértices son adyacentes, se coloca el peso o ponderación asignado a la arista que los une. Con frecuencia en la matriz etiquetada suele utilizarse la siguiente notación: Suponiendo que M [i, j] representa la matriz de adyacencia, tenemos: M [i, j] = 0, si i = j M [i, j] = 1000 ó ∞, si no existe un camino de i a j, donde i j M [i, j] = costo de ir del vértice i al vértice j Otro nombre con el cual suele llamarse a una matriz de adyacencia etiquetada es matriz de distancias o matriz de costos. El problema de buscar un camino más corto entre dos nodos dados se puede resolver mediante un algoritmo voraz conocido como Algoritmo de Dijkstra.

4.9 Grafos Conexos 

Se obtienen a partir de un par ordenado (a, b). Existiendo un camino que los une los cuales se grafican como aristas y vértices.

Un grafo conexo fuertemente conectado se obtiene cuando cada par de vértices tiene una o más aristas que los une.

A continuación, un video para una mejor comprensión:

4.9.1 Circuito de Euler y de Hamilton

Circuito de Euler

Es aquel ciclo que recorre todos los vértices pasando por todos los lados solamente una vez. Un grafo tiene un camino Euleriano, pero no un circuito Euler si y solo si tiene exactamente 2 vértices de grado impar. 

 Un multígrafo conexo tiene un circuito Euleriano si y solo si cada vértice tiene grado par.

Condiciones para saber si un grafo dado tiene un paseo o circuito de Euler.

1) Un grafo no dirigido G tiene un paseo de Euler si y solo si tiene cero o dos vértices de valencia impar.

2) Si un grafo no dirigido G tiene un circuito de Euler entonces todo vértice de G tiene valencia par, además de ser conexo.

3) Si G es un grafo no dirigido con vértices {v1, v2, ... , vn} y la suma

(v1), (v2), ... , (vn) es par, entonces el grafo tiene un circuito de Euler.

4) Un grafo G tiene un camino de Euler de v , w si y solo si v y w son los únicos vértices de valencia (grado de grafos) impar.

Circuito de Hamilton

Se trata de un problema similar al del circuito de Euler, con la diferencia que en lugar de pasar por todos los lados del grafo solamente una vez, en el circuito de Hamilton se pasa por cada vértice solamente una vez.

4.9.2 Graficas ponderadas

Se dice que G es ponderado, si cada arista tiene u valor asociado al que se le llama peso o coste. Los valores de un grafo ponderado habitualmente se presentan en forma de matriz.

En general se asignan a los pesos cantidades que sean esteros no negativos.

Se puede definir una matriz similar a loa de la adyacencia donde reflejaremos el valor de los pesos.

4.9.3 Coloración de grafos

Sea G(V,A) un grafo y sea C un conjunto de colores. La coloración de los vértices V del grafo usando un color del conjunto C se encuentra dada por la función. 

• Esto significa que cada par de vértices adyacentes deberán estar iluminados con un color diferente 
• En la coloración de grafos se busca usar la menor cantidad de colores posible 

4.9.3.1 Numero cromático

Se llama número cromático del grafo G al número mínimo de colores con que se puede colorear un grafo, cuidando que los vértices adyacentes no tengan el mismo color. 

 Pasos para colorear un grafo: 

1. Seleccionar el vértice v de mayor grado e iluminarlo con cualquier color del conjunto C 

2. Colorear los vértices adyacentes al vértice v verificando que no existan vértices adyacentes del mismo color. En caso de ser necesario intercambiar colores. Si ya están coloreados todos los vértices, terminamos, en caso contrario continuar con el paso 

3 seleccionar el vértice v de mayor grado que ya este coloreado y que todavía tenga vértices adyacentes sin colorear. Regresar al paso 2

El número cromático posee las siguientes siete características fundamentales:

4.9.4 Graficas isomorfas

Dos grafos son isomorfos si tienen el mismo número de vértices y los vértices de cada grafo se pueden numerar de 1 hasta n de modo que dos vértices del segundo grafo están unidos por una arista si y sólo si los dos vértices del primer grafo que tienen los mismos números están unidos por una arista.

O mejor dicho son isomorfos porque coinciden en: 

• El número de aristas 
• El número de vértices 
• El conjunto de grados 
• Ser o no conexos 
• El número de circuitos de longitud n 
• Tener o no circuito de Euler

A continuación, un video para una mejor comprensión:

4.9.5 Graficas planas

Cuando un grafo o multígrafo se puede dibujar en un plano sin que dos segmentos se corten, se dice que es plano. Un juego muy conocido es el siguiente: Se dibujan tres casas y tres pozos. Todos los vecinos de las casas tienen el derecho de utilizar los tres pozos. Como no se llevan bien en absoluto, no quieren cruzarse jamás. ¿Es posible trazar los nueve caminos que juntan las tres casas con los tres pozos sin que haya cruces? Cualquier disposición de las casas, los pozos y los caminos implica la presencia de al menos un cruce. Sea Kn el grafo completo con n vértices, Kn, p es el grafo bipartito de n y p vértices. El juego anterior equivale a descubrir si el grafo bipartito completo K3,3 es plano, es decir, si se puede dibujar en un plano sin que haya cruces, siendo la respuesta que no. En general, puede determinarse que un grafo no es plano, si en su diseño puede encontrase una estructura análoga (conocida como menor) a K5 o a K3,3 . Establecer qué grafos son planos no es obvio, y es un problema que tiene que ver con topología.

A continuación, un video para comprender mejor

4.9.6 Graficas homeomorfas

En Teoría de grafos, se dice que dos grafos 𝐺1 y 𝐺2 son homeomorfos si ambos pueden obtenerse a partir de un mismo grafo por una sucesión de subdivisiones elementales de aristas. Suele notarse por 𝐺1≅𝐻𝐺2.

Este concepto, de naturaleza combinatoria, está relacionado con el concepto topológico de homeomorfismo: cualquier grafo puede representarse como un espacio topológico en que cada vértice queda representado por un punto distinto y cada arista por un arco homeomorfo con el intervalo [0,1]. Dos grafos son homeomorfos en el sentido de la teoría de grafos si y solo si lo son como espacios topológicos.

 ARBOLES

5.1 PROPIEDADES DE LOS ARBOLES

Las propiedades en los árboles se componen de:

• Grado: es el número de nodos hijos de un nodo.
• Grado del árbol: es el máximo grado de todos los nodos.
• Nivel: número de arcos que se recorren para ir a un determinado nodo.
• La raíz: es de nivel 1(primer vértice).
• Altura del árbol: máximo número de niveles de todos los nodos.
• Rama: camino del nodo raíz a una hoja.
• Todo árbol que no es vacío, tiene un nodo raíz.
• Un nodo X es descendiente directo de un nodo Y, si el nodo X apunta al nodo Y; entonces X es hijo de Y.
• Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. entonces X es el padre de Y.
• Se dice que todos los nodos son descendiente directo; entonces, se dice que todos los nodos que son descendientes directos (hijos), de un mismo nodo (padre), son hermanos.
• Todo nodo que no tiene ramificaciones (hijos) se conoce con el nombre de terminal u hoja.
• Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de nodo interior.

A continuación, un video para una mejor comprensión:

5.2 ARBOLES GENERADORES

Un grafo generador es un subgrafo mínimo conexo de un grafo conexo en el sentido de que a partir de un subgrafo conexo el cual no sea un árbol generador, una o más de sus aristas pueden eliminarse, de manera que el grafo resultante aún sea un subgrafo conexo y, por otra parte, ninguna arista puede eliminarse de un árbol generador de manera que el subgrafo resultante aún sea un subgrafo conexo.

A continuación, un video para una mejor comprensión:

5.3 ARBOLES GENERADORES MINIMALES

Un árbol generador de un grafo es un subgrafo conexo del mismo, que contiene a todos los vértices y es un árbol. Estas propiedades son equivalentes a decir que es un árbol que contiene todos los nodos del grafo en cuestión, y a partir del cual se puede llegar al grafo agregando aristas.

El árbol generador mínimo (AGM, o “MST” por sus siglas en inglés) de un grafo con aristas con pesos, es el grafo generador cuya suma de las aristas del árbol es mínimo dentro de todas las sumas de aristas de árboles generadores.

A continuación, un video para una mejor comprensión:

5.4 RECORRIDO DE ARBOL

El recorrido de un árbol es el proceso para recorrer (desplazarse a lo largo) un árbol de manera sistemática a fin de que cada vértice se visite y procese exactamente una vez .Hay tres métodos para recorrer un árbol binario a saber recorridos de pre orden , de in orden y de pos orden.

En ciencias de la computación, el recorrido de árboles se refiere al proceso de visitar de una manera sistemática, exactamente una vez, cada nodo en una estructura de datos de árbol (examinando y/o actualizando los datos en los nodos). Tales recorridos están clasificados por el orden en el cual son visitados los nodos. Los siguientes algoritmos son descritos para un árbol binario, pero también pueden ser generalizados a otros árboles.

 Recorridos

Comparado a las estructuras de datos lineales como las listas enlazadas y arreglos unidimensionales, que tienen un método canónico de recorrido, las estructuras arborescentes pueden ser recorridas de muchas maneras diferentes. Comenzando en la raíz de un árbol binario, hay tres pasos principales que pueden ser realizados y el orden en la cual son realizados define el tipo de recorrido. Estos pasos (en ningún orden particular) son: ejecución de una acción en el nodo actual (referido como “visitando” el nodo), recorriendo al nodo hijo de la izquierda, y recorriendo al nodo hijo de la derecha. Así el proceso más fácilmente descrito a través de la recursión.

 Los nombres dados para un estilo particular de recorrido vienen de la posición del elemento de raíz con respecto a los nodos izquierdo y derecho. Imagine que los nodos izquierdo y derecho son constantes en espacio, entonces el nodo raíz pudiera colocarse a la izquierda del nodo izquierdo (pre-orden), entre el nodo izquierdo y derecho (in-orden), o a la derecha del nodo derecho (post-orden).

Con el fin de ilustrar, se asume que los nodos izquierdos tienen siempre prioridad sobre los nodos derechos. Este ordenamiento puede ser invertido mientras el mismo orden sea asumido para todos los métodos de recorrido.

5.4.1. Notación prefija y posfija

Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en

preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo,

comenzando con el nodo de raíz:

• Visite la raíz

• Atraviese el sub-árbol izquierdo

• Atraviese el sub-árbol derecho

Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden

(simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

• Atraviese el sub-árbol izquierdo

• Visite la raíz

• Atraviese el sub-árbol derecho

Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:

• Atraviese el sub-árbol izquierdo

• Atraviese el sub-árbol derecho

• Visite la raíz

A continuación, un video para una mejor comprensión:

5.5 EJECUCIONES DE LOS PRINCIPALES ALGORITMOS

Hay dos algoritmos conocidos para encontrar el AGM: el de Prim y el de Kruskal.

5.3.1. Algoritmo de Prim

En informática, el algoritmo de Prim es un algoritmo codicioso que encuentra un árbol de expansión mínimo para un gráfico no dirigido ponderado. Esto significa que encuentra un subconjunto de las aristas que forma un árbol que incluye todos los vértices, donde se minimiza el peso total de todas las aristas del árbol. El algoritmo opera construyendo este árbol un vértice a la vez, desde un vértice inicial arbitrario, en cada paso agregando la conexión más económica posible del árbol a otro vértice.

El algoritmo fue desarrollado en 1930 por el matemático checo Vojtěch Jarník y luego redescubierto y vuelto a publicar por los informáticos Robert C. Prim en 1957 y Edsger W. Dijkstra en 1959. Por lo tanto, a veces también se le llama Jarník' algoritmo;s, algoritmo Prim-Jarník, algoritmo Prim-Dijkstra o el algoritmo DJP.

Otros algoritmos conocidos para este problema incluyen el algoritmo de Kruskal y el algoritmo de Borůvka. Estos algoritmos encuentran el bosque de expansión mínimo en un gráfico posiblemente desconectado; por el contrario, la forma más básica del algoritmo de Prim solo encuentra árboles de expansión mínimos en gráficos conectados. Sin embargo, al ejecutar el algoritmo de Prim por separado para cada componente conectado del gráfico, también se puede usar para encontrar el bosque de expansión mínimo. En términos de su complejidad temporal asintótica, estos tres algoritmos son igualmente rápidos para gráficos dispersos, pero más lentos que otros algoritmos más sofisticados. Sin embargo, para gráficos que son lo suficientemente densos, el algoritmo de Prim puede ejecutarse en tiempo lineal, cumpliendo o mejorando los límites de tiempo de otros algoritmos.

El algoritmo de Prim comienza en el vértice A. En el tercer paso, los bordes BD y AB tienen peso 2, por lo que BD es elegido arbitrariamente. Después de ese paso, AB ya no es un candidato para añadir al árbol porque vincula dos nodos que ya están en el árbol.

Descripción

El algoritmo puede describirse de manera informal realizando los siguientes pasos:

Inicia un árbol con un solo vértice, elegido arbitrariamente del gráfico.

Crece el árbol por un borde: de los bordes que conectan el árbol a los vértices que aún no están en el árbol, encontrar el borde mínimo-peso, y transferirlo al árbol.

Repita el paso 2 (hasta que todos los vértices estén en el árbol).

Describa la acción del algoritmo de Prim para el grafo en la figura siguiente como un punto de partida.

calculamos el número de aristas y vértices. vértices = 8-1

visitamos la arista de menor peso =74

volvemos a elegir el de menor peso = 262 G

elegimos nueva línea incidente = 242 E

el siguiente de menor peso es =83 D

el siguiente de menor peso =151 F

el siguiente que encontramos =230 C

y el último es ultimo A =355

74+232+242+83+151+230+355=1267

5.3.2. Algoritmo de Kruskal

El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa).

Descripción

El algoritmo de Kruskal es un ejemplo de algoritmo voraz que 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.

En un árbol de expansión mínimo se cumple:

la cantidad de aristas del árbol es la cantidad de nodos menos uno.

A continuación, un video para una mejor comprensión:

Referencias

Diestel, R. (2010). Graph Theory (4th ed.). Springer. ISBN 9783642142789.

West, D. B. (2001). Introduction to Graph Theory (2nd ed.). Prentice Hall. ISBN 9780130144003.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. ISBN 9780262033848.

Chartrand, G., & Zhang, P. (2012). A First Course in Graph Theory. Dover Publications. ISBN 9780486483689.

Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley. ISBN 9780321573513.
Kleinberg, J., & Tardos, E. (2006). Algorithm Design. Pearson. ISBN 9780321295354.

Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory (Graduate Texts in Mathematics). Springer. ISBN 9781846289699.

Chartrand, G., & Zhang, P. (2012). Introduction to Graph Theory (4th ed.). McGraw-Hill.

Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory (Vol. 244). Springer.

Wilson, R. J. (2010). Introduction to Graph Theory (5th ed.). Pearson.

Gross, J. L., & Yellen, J. (2005). Graph Theory and Its Applications (2nd ed.). Chapman and Hall/CRC.

West, D. B. (2001). Introduction to Graph Theory (2nd ed.). Prentice Hall.

Diestel, R. (2017). Graph Theory (5th ed.). Springer.

Harary, F. (1969). Graph Theory. Addison-Wesley.

Deo, N. (2004). Graph Theory with Applications to Engineering and Computer Science. Dover Publications.

Tutte, W. T. (2001). Graph Theory As I Have Known It. Clarendon Press.

Mohar, B., & Thomassen, C. (2001). Graphs on Surfaces. Johns Hopkins University Press.

Whitney, H. (1932). Congruent Graphs and the Connectivity of Graphs. American Journal of Mathematics, 54(1), 150-168.

Bollobás, B. (1998). Modern Graph Theory. Springer.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

Jarník, V. (1930). O jistém problému minimálním. Práce Moravské Přírodovědecké Společnosti, 6, 57-63.

Prim, R. C. (1957). Shortest Connection Networks And Some Generalizations. Bell System Technical Journal, 36(6), 1389-1401.

Kruskal, J. B. (1956). On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society, 7(1), 48-50.