El árbol de expansión mínimo capacitado es un árbol de expansión de costo mínimo de un gráfico que tiene un nodo raíz designado y satisface la restricción de capacidad . La restricción de capacidad asegura que todos los subárboles (subgrafos máximos conectados a la raíz por un solo borde) incidan en el nodo raíz no tener más de nodos. Si los nodos del árbol tienen ponderaciones, entonces la restricción de capacidad se puede interpretar de la siguiente manera: la suma de las ponderaciones en cualquier subárbol no debe ser mayor que. Los bordes que conectan los subgrafos con el nodo raíz se denominan puertas . Encontrar la solución óptima es NP-difícil. [1]
Algoritmos
Supongamos que tenemos una gráfica , con una raíz . Dejar ser todos los otros nodos en . Dejarser el costo de la ventaja entre vértices y que forman una matriz de costos .
Heurística de Esaú-Williams
La heurística de Esau-Williams encuentra CMST subóptimas que están muy cerca de las soluciones exactas, pero en promedio EW produce mejores resultados que muchas otras heurísticas.
Inicialmente, todos los nodos están conectados a la raíz. (gráfico de estrella) y el costo de la red es ; cada uno de estos bordes es una puerta. En cada iteración, buscamos al vecino más cercano para cada nodo en y evaluar la función de compensación: . Buscamos lo mas grande entre las compensaciones positivas y, si el subárbol resultante no viola las restricciones de capacidad, elimine la puerta conectando el -th subárbol a por un borde . Repetimos las iteraciones hasta que no podamos realizar más mejoras en el árbol.
Heurística de Esaú-Williams para calcular un CMST subóptimo:
función CMST ( c , C , r ): T = {, , ..., } while tener cambios: para cada nodo = nodo más cercano en un subárbol diferente = - t_max = max ( ) k = i tal que = t_max si ( costo (i) + costo (j) <= c ) T = T - T = unión T volver T
Es fácil ver que EW encuentra una solución en tiempo polinomial.
La heurística de Sharma
La heurística de Sharma. [3]
Aplicaciones
El problema de CMST es importante en el diseño de redes: cuando muchas computadoras terminales tienen que estar conectadas al concentrador central, la configuración en estrella generalmente no es el diseño de costo mínimo. Encontrar un CMST que organice los terminales en subredes puede reducir el costo de implementación de una red.
Referencias
- ^ Jothi, Raja; Raghavachari, Balaji (2005), "Algoritmos de aproximación para el problema del árbol de expansión mínimo capacitado y sus variantes en el diseño de redes", ACM Trans. Algoritmos , 1 (2): 265–282, doi : 10.1145 / 1103963.1103967 , S2CID 8302085
- ^ Esaú, LR; Williams, KC (1966). "Sobre el diseño de redes de teleprocesamiento: Parte II. Un método para aproximar la red óptima". Revista de sistemas de IBM . 5 (3): 142-147. doi : 10.1147 / sj.53.0142 .
- ^ Sharma, RL; El-Bardai, MT (1977). "Síntesis de redes de comunicaciones subóptimas". En Proc. De la Conferencia Internacional de Comunicaciones : 19.11-19.16.