5.6: Árboles de expansión óptimos
- Page ID
- 117102
En algunas aplicaciones, una gráfica\(G\) se aumenta asociando un peso o costo con cada borde; dicha gráfica se denomina gráfica ponderada. Por ejemplo, si una gráfica representa una red de carreteras, el peso de un borde podría ser la longitud de la carretera entre sus dos extremos, o la cantidad de tiempo requerido para viajar de un extremo a otro, o el costo de enterrar el cable a lo largo de la carretera de un extremo a otro. En tales casos, en lugar de estar interesados en cualquier árbol de expansión, podemos estar interesados en un árbol de expansión de menor costo, es decir, un árbol de expansión tal que la suma de los costos de los bordes del árbol sea lo más pequeña posible. Por ejemplo, esta sería la forma menos costosa de conectar un conjunto de pueblos mediante una red de comunicación, enterrando el cable de tal manera que se minimice el costo total de tendido del cable.
Este problema es uno que puede resolverse mediante un algoritmo codicioso. En términos generales, un algoritmo codicioso es aquel que toma decisiones que son óptimas a corto plazo. Normalmente esta estrategia no da como resultado una solución óptima a largo plazo, pero en este caso este enfoque funciona.
Definición\(\PageIndex{1}\): Weighted Graph
Un gráfico ponderado es un gráfico\(G\) junto con una función de costo\(c\colon E(G)\to \mathbb{R}^{>0}\). Si\(H\) es un subgrafo de\(G\), el costo de\(H\) es\(c(H)=\sum_{e\in E(H)} c(e)\).
Algorithm \(\PageIndex{1}\): The Jarník Algorithm
Dado un gráfico conectado ponderado\(G\), construimos un árbol de expansión de costos mínimos de la\(T\) siguiente manera. Elige cualquier vértice\(v_0\) en\(G\) e inclúyalo en\(T\). Si se\(S=\{v_0, v_1,\ldots,v_k\}\) han elegido vértices, elija una arista con un punto final\(S\) y un punto final no dentro\(S\) y con menor peso entre todas esas aristas. Dejar\(v_{k+1}\) ser el punto final de este borde no en\(S\), y agregarlo y el borde asociado a\(T\). Continuar hasta que todos los vértices de\(G\) estén en\(T\).
Este algoritmo fue descubierto por Vojtěch Jarník en 1930, y redescubierto independientemente por Robert C. Prim en 1957 y Edsger Dijkstra en 1959. A menudo se le llama Algoritmo de Prim.
El algoritmo procede construyendo una secuencia de árboles\(T_1, T_2,\ldots,T_{n-1}\), con\(T_{n-1}\) un árbol de expansión para\(G\). En cada paso, el algoritmo agrega un borde que hará lo más pequeño\(c(T_{i+1})\) posible entre todos los árboles que constan de\(T_i\) más un borde. Esta es la mejor opción a corto plazo, pero no es obvio que a la larga, es decir, para cuando\(T_{n-1}\) se construya, que esta va a resultar haber sido la mejor opción.
Teorema \(\PageIndex{1}\)
El Algoritmo Jarník produce un árbol de expansión de costo mínimo.
- Prueba
-
Supongamos que\(G\) está conectado en\(n\) vértices. \(T\)Sea el árbol de expansión producido por el algoritmo, y\(T_m\) un árbol de expansión de costo mínimo. Eso lo demostramos\(c(T)=c(T_m)\).
Dejar\(e_1, e_2,\ldots,e_{n-1}\) ser los bordes de\(T\) en el orden en que se agregaron\(T\); un punto final de\(e_i\) es\(v_i\), el otro está en\(\{v_0,\ldots,v_{i-1}\}\). Formamos una secuencia de árboles\(T_m=T_0, T_1,\ldots, T_{n-1}=T\) tal que para cada uno\(i\),\(c(T_i)=c(T_{i+1})\), y concluimos que\(c(T_m)=c(T)\).
Si\(e_1\) está dentro\(T_0\), vamos\(T_1=T_0\). De lo contrario, agregue borde\(e_1\) a\(T_0\). Esto crea un ciclo que contiene\(e_1\) y otro incidente de borde en\(v_0\), digamos\(f_1\). Retirar\(f_1\) para formar\(T_1\). Dado que el algoritmo agregó borde\(e_1\),\(c(e_1)\le c(f_1)\). Si\(c(e_1)< c(f_1)\), entonces\(c(T_1)< c(T_0)=c(T_m)\), una contradicción, así\(c(e_1)=c(f_1)\) y\(c(T_1)=c(T_0)\).
Supongamos que hemos construido árbol\(T_i\). Si\(e_{i+1}\) está dentro\(T_i\), vamos\(T_{i+1}=T_i\). De lo contrario, agregue borde\(e_{i+1}\) a\(T_i\). Esto crea un ciclo, uno de cuyos bordes, lo llaman\(f_{i+1}\), no está en\(e_1, e_2,\ldots,e_i\) y tiene exactamente un punto final en\(\{v_0,\ldots,v_i\}\). Quitar\(f_{i+1}\) para crear\(T_{i+1}\). Dado que el algoritmo agregó\(e_{i+1}\),\(c(e_{i+1})\le c(f_{i+1})\). Si\(c(e_{i+1})< c(f_{i+1})\), entonces\(c(T_{i+1})< c(T_i)=c(T_m)\), una contradicción, así\(c(e_{i+1})=c(f_{i+1})\) y\(c(T_{i+1})=c(T_i)\).