Problema del árbol de expansión mínima (I)

El problema del árbol de expansión mínima tiene algunas similitudes con la versión principal del problema de la ruta más corta que se presentó en la sección anterior. En ambos casos se considera una red no dirigida, en la que la información dada incluye los nodos y las distancias entre pares de nodos. Sin embargo, la diferencia crucial para el problema del árbol de expansión mímina es que las ligaduras (arcos no dirigidos) ya no se especifican. Entonces, en lugar de encontrar la ruta más corta a través de una red completamente definida, el problema elige las lugaduras en la red que tenga la longitud total más corta al mismo tiempo que proporciona una trayectoria ente cada par de nodos. Es necesario que las ligaduras se elijan de tal manera que la red resultante forme un árbol (según la definición dada en la sección ) que se expande (conecta) todos los nodos dados. En resumen, el programa es encontrar el árbol de expansión con la longitud total mínima de sus ligaduras.

La figura ilustra el concepto de árbol de expansión para el problema de Seervada Park. La sección a no es un árbol de expansión, pues los nodos (O,A, B, C) no están conectados con los nodos (D,E,T). Se necesita una rama más para hacer esta conexión. En realidad esta red consiste en dos árboles, uno para cada conjunto de nodos. Las ligaduras de la figura 10.4b si  se expanden por toda la red (esto es,  es una gráfica conexa según la definición de la sección 10.2) pero no es un árbol porque tiene dos ciclos (0-A-B-C-O Y D-T-E-D). Tiene demasiadas ligaduras. El problema de Seervada Prak tiene n=7 nodos, y coo se indicó en la sección 10.2, una red debe tener justo (n-1)= 6 ligaduras y no tener ciclos para calificar como un árbol de expansión. Esta condición se logra en la figura 10.4c, por lo que esta red es una solución factible (con una longitud total de 24 millas en las ramas) para el problema del árbol de mínima expansión.