6.7: Árboles de expansión
- Page ID
- 110619
Una empresa requiere conectividad confiable a Internet y teléfono entre sus cinco oficinas (llamadas A, B, C, D y E por simplicidad) en Nueva York, por lo que deciden arrendar líneas dedicadas a la compañía telefónica. La compañía telefónica cobrará por cada enlace realizado. Los costos, en miles de dólares anuales, se muestran en la gráfica.
En este caso, no necesitamos encontrar un circuito, ni siquiera un camino específico; todo lo que tenemos que hacer es asegurarnos de poder hacer una llamada desde cualquier oficina a cualquier otra. En otras palabras, necesitamos estar seguros de que hay un camino desde cualquier vértice a cualquier otro vértice.
Un árbol de expansión es una gráfica conectada que utiliza todos los vértices en los que no hay circuitos.
En otras palabras, hay un camino desde cualquier vértice a cualquier otro vértice, pero no hay circuitos.
A continuación se muestran algunos ejemplos de árboles de expansión. Observe que no hay circuitos en los árboles, y está bien tener vértices con grado superior a dos.
Por lo general tenemos una gráfica de inicio para trabajar, como en el ejemplo telefónico anterior. En este caso, formamos nuestro árbol de expansión al encontrar una subgrafía, una nueva gráfica formada usando todos los vértices pero solo algunos de los bordes de la gráfica original. No se crearán bordes donde no existieran ya.
Por supuesto, cualquier árbol de expansión aleatorio no es realmente lo que queremos. Queremos el árbol de expansión de costo mínimo (MCST).
El árbol de expansión de costo mínimo es el árbol de expansión con el menor peso total de borde.
Un enfoque de estilo vecino más cercano no tiene tanto sentido aquí ya que no necesitamos un circuito, así que en su lugar tomaremos un enfoque similar a los bordes ordenados.
- Seleccione el borde no utilizado más barato en la gráfica.
- Repita el paso 1, agregando el borde sin usar más barato, a menos que:
- agregar el borde crearía un circuito
- Repita hasta que se forme un árbol de expansión
Usando nuestro gráfico de líneas telefónicas desde arriba, comience a agregar bordes:
\ (\ begin {array} {lll}\ mathrm {AB} &\ $4 &\ mathrm {OK}\\\ mathrm {AE} &\ $5 &\ mathrm {OK}
\\\ text {BE} &\ $\ text {6} &\ text {{rechect-cierra circuito ABEA}\\\ text {DC} &\ $7 &\ text {OK}\\ text {AC} &\ $8 &\ text {OK}\ end {array}\)
En este punto nos detenemos — cada vértice ahora está conectado, así que hemos formado un árbol de expansión con un costo de 24 mil dólares al año.
Notablemente, el algoritmo de Kruskal es óptimo y eficiente; estamos garantizados para producir siempre el MCST óptimo.
La compañía eléctrica necesita establecer líneas de distribución actualizadas que conecten las diez ciudades de Oregón a continuación a la red eléctrica. ¿Cómo pueden minimizar la cantidad de nueva línea a colocar?
\ (\ begin {array} {|c|c|c|c|c|c|c|c|c|c|c|c|}
\ hline & & & & & & & & & & & & &
& &\ texto {Ashland} &\ texto {Astoria} &\ texto {Curva} &\ texto {Corvallis} &\ text {Lago del cráter} &\ texto {Eugene} &\ texto {Newport} & amp;\ text {Portland} &\ texto {Salem} &\ texto {Mar}\\
\ hline\ texto {Ashland} &\ _ & 374 & 200 & 223 & 108 & 178 & 252 & 285 & 240 & 356\
\ hline\ texto {Astoria} & 374 &\ _ & 255 & 166 & 433 & 199 & 135 & 95 & 136 & 17\
\ hline\\ hline\ text {Curva} & 200 & 255 &\ _ & 128 & 277 & 128 & 180 & 160 & 131 & 247
\\ hline\ texto {Corvallis} & 223 & 166 & 128 &\ _ & 430 & 47 & 52 & 84 y 40 & 155\
\ hline\ text {Lago del cráter} & 108 & 433 & 277 & 430 &\ _ & 453 & 478 & 344 & 389 & 423\\
\ hline\ texto {Eugene} & 178 & 199 & 128 & 47 & 453 &\ _ & 91 & 110 & 64 & 181\\
\ hline\ text {Newport} & 252 & 135 & 180 & 52 & 478 & 91 &\ _ & 114 & 83 & 117\\
\ hline\ text {Portland} & 285 & 95 & 160 & 84 & 344 & 110 & 114 &\ _ & 47 & 78\
\ hline\ texto {Salem} & 240 y 136 & 131 & 40 & 389 & 64 & 83 & 47 &\ _ & 118\\
\ hline\ text {Seaside} & 356 & 17 & 247 & 155 & 423 & 181 & 117 & 78 & 118 &\ _\
\ hline
\ end {array}\)
Solución
Usando el algoritmo de Kruskal, agregamos bordes de los más baratos a los más caros, rechazando cualquiera que cierre un circuito. Nos detenemos cuando la gráfica está conectada.
\(\begin{array}{ll} \text{Seaside to Astoria} & 17 \text{ miles} \\ \text{Corvallis to Salem} & 40 \text{ miles} \\ \text{Portland to Salem} & 47 \text{ miles} \\ \text{Corvallis to Eugene} & 47 \text{ miles} \\ \text{Corvallis to Newport} & 52 \text{ miles} \\ \text{Salem to Eugene} & \text{reject – closes circuit} \\ \text{Portland to Seaside} & 78 \text{ miles} \end{array}\)
La gráfica hasta este punto se muestra a la derecha.
Continuando,
\(\begin{array}{ll} \text{Newport to Salem} & \text{reject} \\ \text{Corvallis to Portland} & \text{reject} \\ \text{Eugene to Newport} & \text{reject} \\ \text{Portland to Astoria} & \text{reject} \\ \text{Ashland to Crater Lk} & 108\text{ miles} \\ \text{Eugene to Portland} & \text{reject} \\ \text{Newport to Portland} & \text{reject} \\ \text{Newport to Seaside} & \text{reject} \\ \text{Salem to Seaside} & \text{reject} \\ \text{Bend to Eugene} & 128\text{ miles} \\ \text{Bend to Salem} & \text{reject} \\ \text{Astoria to Newport} & \text{reject} \\ \text{Salem to Astoria} & \text{reject} \\ \text{Corvallis to Seaside} & \text{reject} \\ \text{Portland to Bend} & \text{reject} \\ \text{Astoria to Corvallis} & \text{reject} \\ \text{Eugene to Ashland} & 178\text{ miles} \end{array}\)
Esto conecta la gráfica. La longitud total del cable a tender sería de 695 millas.
Encuentre un árbol de expansión de costos mínimos en la gráfica a continuación utilizando el algoritmo de Kruskal.
- Responder
-
AB: Agregar, costo 11BG: Agregar, costo 13
AE: Agregar, costo 14
AG: Skip, crearía circuito ABGA
EF: Agregar, costo 16
EC: Agregar, costo 17
Esto completa el árbol de expansión