Árbol recubridor mínimo
Una serie de problemas de la teoría de grafos se denominan Árbol de extensión mínima. En la teoría de grafos, un árbol es una forma de conectar todos los vértices entre sí, de manera que haya exactamente un camino desde cualquier vértice, a cualquier otro vértice del árbol. Si el grafo representa una serie de ciudades conectadas por carreteras, se podría seleccionar un número de caminos, de manera que se pueda llegar a cada ciudad desde cualquier otra, pero que no haya más de un camino para viajar de una ciudad a otra.
Un grafo puede tener más de un árbol de expansión, al igual que puede haber más de una forma de seleccionar las carreteras entre las ciudades.
La mayoría de las veces, los grafos están ponderados; cada conexión entre dos ciudades tiene un peso: puede costar algo viajar por una determinada carretera, o una conexión puede ser más larga que la otra, lo que significa que se tarda más en viajar por esa conexión. En el lenguaje de la teoría de grafos, las conexiones se denominan aristas.
Un árbol de mínima extensión es un árbol. Se diferencia de otros árboles en que minimiza el total de los pesos de las aristas. Dependiendo de cómo sea el gráfico, puede haber más de un árbol de mínima extensión. En un grafo en el que todas las aristas tienen el mismo peso, cada árbol es un árbol de mínima extensión. Si todas las aristas tienen pesos diferentes (es decir, no hay dos aristas con el mismo peso), hay exactamente un árbol de mínima extensión.
El árbol mínimo de un gráfico plano. Cada arista está etiquetada con su peso, que aquí es aproximadamente proporcional a su longitud.
Encontrar el árbol de expansión mínimo
Un primer intento
Puede ser muy sencillo hacer un algoritmo que descubra un árbol de expansión mínimo:
función MST(G,W): T = {} mientras T no forme un árbol de expansión: encuentra la mínima arista ponderada en E que sea segura para T T = T unión {(u,v)} return TEn este caso, "seguro" significa que al incluir la arista no se forma un ciclo en el gráfico. Un ciclo significa empezar en un vértice, viajar a varios otros vértices y terminar de nuevo en el punto de partida sin utilizar la misma arista dos veces.
Historia
El científico checo Otakar Borůvka desarrolló en 1926 el primer algoritmo conocido para encontrar un árbol de extensión mínima. Quería resolver el problema de encontrar una cobertura eficiente de Moravia con electricidad. Hoy en día, este algoritmo se conoce como el algoritmo de Borůvka. Otros dos algoritmos se utilizan habitualmente en la actualidad. Uno de ellos fue desarrollado por Vojtěch Jarník en 1930, y puesto en práctica por Robert Clay Prim en 1957. Edsger Wybe Dijkstra lo redescubrió en 1959 y lo llamó algoritmo de Prim. El otro algoritmo se llama algoritmo de Kruskal, y fue pulido por Joseph Kruskal en 1956. Los tres algoritmos son codiciosos y se ejecutan en tiempo polinómico.
El algoritmo de árbol mínimo más rápido hasta la fecha fue desarrollado por Bernard Chazelle. El algoritmo se basa en el montón suave, una cola de prioridad aproximada. Su tiempo de ejecución es O(m α(m,n)), donde m es el número de aristas, n es el número de vértices y α es la función clásica inversa de la función de Ackermann. La función α crece muy lentamente, por lo que a efectos prácticos puede considerarse una constante no superior a 4; así, el algoritmo de Chazelle tarda un tiempo muy cercano a la linealidad.
¿Cuál es el algoritmo más rápido posible para este problema? Esta es una de las preguntas abiertas más antiguas de la informática. Está claro que hay un límite inferior lineal, ya que debemos examinar al menos todos los pesos. Si los pesos de las aristas son enteros con una longitud de bits limitada, se conocen algoritmos deterministas con un tiempo de ejecución lineal. Para pesos generales, existen algoritmos aleatorios cuyo tiempo de ejecución esperado es lineal.
El problema también puede plantearse de forma distribuida. Si se considera que cada nodo es un ordenador y que ningún nodo conoce nada más que sus propios enlaces conectados, se puede seguir calculando el árbol de expansión mínimo distribuido.
Preguntas y respuestas
P: ¿Qué es un árbol de extensión mínima en la teoría de grafos?
R: Un árbol de envergadura mínima es un árbol que minimiza los pesos totales asignados a las aristas en la teoría de grafos.
P: ¿Qué es un árbol en la teoría de grafos?
R: Un árbol es una forma de conectar todos los vértices entre sí en la teoría de grafos, de forma que sólo haya un camino desde cualquier vértice a cualquier otro vértice del árbol.
P: ¿Cuál es el propósito de seleccionar carreteras en un escenario de teoría de grafos que representa ciudades?
R: El propósito de seleccionar carreteras en un escenario de teoría de grafos que represente ciudades es permitir que se pueda llegar a cada ciudad desde cualquier otra ciudad, pero sin que haya más de un camino posible para viajar de una ciudad a otra.
P: ¿Puede un grafo tener más de un árbol de expansión?
R: Sí, un grafo puede tener más de un árbol de expansión.
P: ¿Cuál es la diferencia entre un árbol de expansión mínima y otros árboles de la teoría de grafos?
R: Un árbol de expansión mínima minimiza los pesos totales asignados a las aristas, mientras que otros árboles no tienen esta característica.
P: ¿Qué son las aristas en la teoría de grafos?
R: Las aristas son las conexiones entre dos vértices en la teoría de grafos.
P: ¿Puede haber más de un árbol de expansión mínima en un grafo con distintas aristas ponderadas?
R: Sí, dependiendo del aspecto del grafo, puede haber más de un árbol de expansión mínima.
