Luces de árbol de costo mínimo
José Padrón C.I 28.462.837 P. no númerica 2 SAIA 2020-1 IUPSM Barcelona
Árbol recubridor mínimo
Definición de árbol de cubrimiento: Sea G= (V, E) un grafo conexo con una función de costos definida sobre las aristas. Un árbol de cubrimiento para G es un árbol libre que conecta todos los vértices en V. El costo de un árbol de cubrimiento es la suma de los costos de las aristas en el árbol.
Definición árbol de cubrimiento de mínimo costo: Sea G= (V, E) un grafo conexo con una función de costos definida sobre las aristas. Sea A= (V, F) [F E] un árbol de cubrimiento para G, A es un árbol de mínimo costo para G si no existe para G otro árbol de cubrimiento cuyo costo sea menor que el costo de A.
Propiedad de los árboles de cubrimiento de mínimo costo: Sea G= (V, E) un grafo conexo con una función de costos definida sobre las aristas. Sea U un subconjunto propio de V [U V]. Si uv es una arista de menor costo tal que u U y v V-U entonces existe un árbol de cubrimiento de mínimo costo que incluye uv como una de sus aristas.
Demostración: Supongamos que no existe para G un árbol de mínimo costo que incluya a uv. Sea A' un árbol de mínimo costo para G. Como A' es un árbol si añadimos uv a A' entonces introducimos un ciclo en A'. De esto se deduce que existe otra arista u'v' en A' tal que u' U y v' V. Si quitamos u'v' de A' entonces eliminamos el ciclo y obtenemos un árbol A cuyo costo no es mayor que el costo de A porque asumimos por hipótesis que costo ( uv ) = costo(u'v'). Ésto entra en contradicción con lo supuesto.
Dado un grafo conexo y no dirigido, un árbol recubridor de ese grafo es un subgrafo que tiene que ser un árbol y contener todos los vértices del grafo inicial. Cada arista tiene asignado un peso proporcional entre ellos, que es un número representativo de algún objeto, distancia, etc.; y se usa para asignar un peso total al árbol recubridor mínimo computando la suma de todos los pesos de las aristas del árbol en cuestión. Un árbol recubridor mínimo o un árbol expandido mínimo es un árbol recubridor que pesa menos o igual que otros árboles recubridores. Todo grafo tiene un bosque recubridor mínimo.
Un ejemplo sería una compañía de cable trazando cable a una nueva vecindad. Si está limitada a trazar el cable por ciertos caminos, entonces se hará un grafo que represente los puntos conectados por esos caminos. Algunos de estos caminos podrán ser más caros que otros, por ser más largos. Estos caminos serían representados por las aristas con mayores pesos. Un árbol recubridor para este grafo sería un subconjunto de estos caminos que no tenga ciclos pero que mantenga conectadas todas las casas. Puede haber más de un árbol recubridor posible. El árbol recubridor mínimo será el de menos coste.
En el caso de un empate, porque podría haber más de un árbol recubridor mínimo; en particular, si todos los pesos son iguales, todo árbol recubridor será mínimo. De todas formas, si cada arista tiene un peso distinto existirá sólo un árbol recubridor mínimo. La demostración de esto es trivial y se puede hacer por inducción. Esto ocurre en muchas situaciones de la realidad, como con la compañía de cable en el ejemplo anterior, donde es extraño que dos caminos tengan exactamente el mismo coste. Esto también se generaliza para los bosques recubridores.
Si los pesos son positivos, el árbol recubridor mínimo es el subgrafo de menor costo posible conectando todos los vértices, ya que los subgrafos que contienen ciclos necesariamente tienen más peso total.
Usos
Una de las aplicaciones más destacadas del árbol mínimo recubridor se encuentra en el ámbito de las telecomunicaciones, por ejemplo, en las redes de comunicación eléctrica, telefónica, etc. Los nodos representarían puntos de consumo eléctrico, teléfonos, aeropuertos o computadoras. Las aristas podrían ser cables de alta tensión, fibra óptica, rutas aéreas, etc.
Dos algoritmos para construir árboles de cubrimiento de mínimo costo para grafos no dirigidos, conexos y con costos sobre las aristas.
Algoritmo de Kruskal [1956]
El algoritmo de Kruskal construye el árbol de mínimo costo haciendo una iteración sobre el conjunto de las aristas del grafo. Se considera primero que el conjunto de las aristas del árbol a formar está vacío (F= { }).También se considera inicialmente el conjunto de vértices como árboles aislados, componentes conexas por sí mismos del árbol a construir. Entonces en cada paso se halla una arista de mínimo costo que conecte a dos componentes conexas diferentes y se le añade a F, formándose así una nueva componente conexa. Cuando todos los vértices pertenezcan a una misma componente entonces ésta es el árbol de cubrimiento de mínimo costo para el grafo dado.
¿Por qué funciona el algoritmo de Kruskal?
En el algoritmo de Kruskal se considera inicialmente cada vértice como un árbol, una componente conexa por sí mismo. Éstos son además árboles de cubrimiento de mínimo costo para el grafo compuesto solamente por ellos puesto que un vértice es también un grafo. Entonces inicialmente tenemos n (n: número de vértices del grafo inicial) árboles de cubrimiento de mínimo costo, componentes conexas. En cada paso elegimos una arista de menor costo que conecte dos componentes conexas, entonces se forma una nueva componente conexa que es también un árbol de mínimo costo del grafo formado con los vértices de las dos componentes conexas involucradas, puesto que hasta el paso anterior estas componentes eran árboles de mínimo costo y la arista hallada es una de las de menor costo que conecta ambas componentes, no existe otra arista con un costo menor que la elegida que conecte las dos componentes conexas.
Orden del algoritmo de Kruskal [implementación]
Nuestra implementación del algoritmo hace uso de una cola con prioridad para ordenar las aristas antes de comenzar a construir el árbol. Las operaciones de crear, insertar las aristas y ordenar la cola con todas las aristas toma O(e log( e ) ) (e: número de aristas) operaciones. En cada iteración se extrae una arista de la cola con prioridad, acción que toma O( log( e ) ) operaciones. Entonces en el peor de los casos, se da cuando la última arista es una arista de menor costo del árbol, el algoritmo tomará un tiempo de orden O(elog(e)) .
Algoritmo de Prim[1957]
Supongamos V= {1, 2,.., n}. El algoritmo de Prim comienza iniciando el conjunto U en cualquier vértice v V del grafo, tomemos por ejemplo U= {1}. Entonces se construye el árbol de cubrimiento, añadiendo una arista en cada paso, de la manera siguiente:
En cada paso buscamos la arista de menor costo (u, v) que conecta U y V-U, entonces se añade al conjunto de aristas F E del árbol, y se añade el vértice v V-U a U.
Se repite el paso 1 hasta que U = V.
¿Por qué funciona el algoritmo de Prim?
Este algoritmo es una aplicación directa de la propiedad de los árboles de cubrimiento de mínimo costo: En el primer paso buscamos una arista de menor costo y el árbol formado hasta el momento es de mínimo costo. De manera inductiva notemos que si hasta el paso n-1 tenemos un árbol de mínimo costo con los vértices de U y las aristas halladas, entonces, añadiendo en el paso n la arista de menor costo que conecta U con V-U, seguiremos teniendo un árbol de mínimo costo en U. En el paso n el conjunto de los vértices del árbol obtenido es igual al conjunto de los vértices del grafo (U = V), luego este árbol es de mínimo costo para el grafo en cuestión.
Orden del algoritmo de Prim [implementación]
Nuestra implementación del algoritmo hace una iteración sobre cada uno de los vértices en V-U y los añade a U hasta que U = V, por aquí tenemos n operaciones (n: número de vértices). Por cada una de estas operaciones tenemos que hallar una arista de menor costo (u, v) u pertenece a U y v pertenece a V-U, es decir, una arista que una el árbol que se va formando, con los vértices de U y las aristas halladas, a uno de los vértices restantes (V-U). La búsqueda se puede facilitar si desde el principio vamos archivando las aristas de menor costo que conectan a U con los vértices en V-U y en cada paso vamos rectificando, a medida que se le van añadiendo vértices a U. Como en cada paso tenemos que ir rectificando el archivo, esto nos tomará O(n) operaciones en el mejor de los casos. Por tanto, este algoritmo es de orden O(n²).
Comparación entre los algoritmos de Prim y Kruskal
Los algoritmos de Prim y Kruskal toman un tiempo de orden O(n²) y O(elog(e)) respectivamente (n, e: número de vértices y aristas del grafo, respectivamente). Por ésto si el grafo es denso, tiene muchas aristas con respecto a la cantidad de vértices (e ≈ n² ó e > n²), es aconsejable utilizar el algoritmo de Prim, de lo contrario,
