Dado un grafo conexo y no dirigido, un árbol recubridor, árbol de cobertura o árbol de expansión 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 de expansión mínimo es un árbol recubridor que pesa menos o igual que todos los otros árboles recubridores. Todo grafo tiene un bosque recubridor mínimo.
Un ejemplo de árbol recubridor mínimo. Cada punto representa un vértice, cada arista está etiquetada con su peso, que en este caso equivale a su longitud.
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á solo 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.
Aplicaciones
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,... .
El Algoritmo de Prim consiste en incrementar el tamaño de un árbol, empezando por un vértice inicial al cual se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto quiere decir que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol. Por tanto, el árbol recubridor mínimo estará completamente construido cuando no queden más vértices por agregar. Los requisitos para proceder con el Algoritmo de Prim son:
Grafo conexo
Tener todos los arcos etiquetados
La idea fundamental consiste en añadir en cada paso una arista de peso mínimo a un árbol previamente construido. Para verlo de un modo más explícito, se definen los siguientes pasos:
Se elige un vértice U de G y se considera el árbol S={U}.
Se considera la arista e de mínimo peso que une un vértice de S y un vértice que no es de S, y se hace S=S+e .
Si el número de aristas de T es n-1, el algoritmo termina. En caso contrario, volveríamos al paso 2.
Otakar Boruvka on Minimum Spanning Tree Problem (translation of the both 1926 papers, comments, history) (2000) Jaroslav Nesetril, Eva Milková, Helena Nesetrilová (section 7 gives his algorithm, which looks like a cross between Prim's and Kruskal's)
A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity, Bernard Chazelle, 1999
State-of-the-Art Algorithms for Minimum Spanning Trees: A Tutorial Discussion, Jason Eisner, 1997
Enlaces externos
Implementado en BGL, la "Boost Graph Library"
Datos:Q240464
Multimedia:Minimum spanning trees
Noviembre 19, 2021
Árbol, recubridor, mínimo, dado, grafo, conexo, dirigido, árbol, recubridor, árbol, cobertura, árbol, expansión, grafo, subgrafo, tiene, árbol, contener, todos, vértices, grafo, inicial, cada, arista, tiene, asignado, peso, proporcional, entre, ellos, número, . Dado un grafo conexo y no dirigido un arbol recubridor arbol de cobertura o arbol de expansion de ese grafo es un subgrafo que tiene que ser un arbol y contener todos los vertices del grafo inicial Cada arista tiene asignado un peso proporcional entre ellos que es un numero representativo de algun objeto distancia etc y se usa para asignar un peso total al arbol recubridor minimo computando la suma de todos los pesos de las aristas del arbol en cuestion Un arbol recubridor minimo o un arbol de expansion minimo es un arbol recubridor que pesa menos o igual que todos los otros arboles recubridores Todo grafo tiene un bosque recubridor minimo Un ejemplo de arbol recubridor minimo Cada punto representa un vertice cada arista esta etiquetada con su peso que en este caso equivale a su longitud Un ejemplo seria una compania de cable trazando cable a una nueva vecindad Si esta limitada a trazar el cable por ciertos caminos entonces se hara un grafo que represente los puntos conectados por esos caminos Algunos de estos caminos podran ser mas caros que otros por ser mas largos Estos caminos serian representados por las aristas con mayores pesos Un arbol recubridor para este grafo seria un subconjunto de estos caminos que no tenga ciclos pero que mantenga conectadas todas las casas Puede haber mas de un arbol recubridor posible El arbol recubridor minimo sera el de menos coste En el caso de un empate porque podria haber mas de un arbol recubridor minimo en particular si todos los pesos son iguales todo arbol recubridor sera minimo De todas formas si cada arista tiene un peso distinto existira solo un arbol recubridor minimo La demostracion de esto es trivial y se puede hacer por induccion Esto ocurre en muchas situaciones de la realidad como con la compania de cable en el ejemplo anterior donde es extrano que dos caminos tengan exactamente el mismo coste Esto tambien se generaliza para los bosques recubridores Si los pesos son positivos el arbol recubridor minimo es el subgrafo de menor costo posible conectando todos los vertices ya que los subgrafos que contienen ciclos necesariamente tienen mas peso total Indice 1 Aplicaciones 2 Algoritmo de Prim para el arbol recubridor minimo 3 Vease tambien 4 Referencias 5 Enlaces externosAplicaciones EditarUna de las aplicaciones mas destacadas del arbol minimo recubridor se encuentra en el ambito de las telecomunicaciones por ejemplo en las redes de comunicacion electrica telefonica etc Los nodos representarian puntos de consumo electrico telefonos aeropuertos o computadoras Las aristas podrian ser cables de alta tension fibra optica rutas aereas Algoritmo de Prim para el arbol recubridor minimo EditarArticulo principal Algoritmo de Prim El Algoritmo de Prim consiste en incrementar el tamano de un arbol empezando por un vertice inicial al cual se le van agregando sucesivamente vertices cuya distancia a los anteriores es minima Esto quiere decir que en cada paso las aristas a considerar son aquellas que inciden en vertices que ya pertenecen al arbol Por tanto el arbol recubridor minimo estara completamente construido cuando no queden mas vertices por agregar Los requisitos para proceder con el Algoritmo de Prim son Grafo conexo Tener todos los arcos etiquetadosLa idea fundamental consiste en anadir en cada paso una arista de peso minimo a un arbol previamente construido Para verlo de un modo mas explicito se definen los siguientes pasos Se elige un vertice U de G y se considera el arbol S U Se considera la arista e de minimo peso que une un vertice de S y un vertice que no es de S y se hace S S e Si el numero de aristas de T es n 1 el algoritmo termina En caso contrario volveriamos al paso 2 Vease tambien EditarAlgoritmo de Prim Algoritmo de Kruskal Algoritmo de DijkstraReferencias EditarOtakar Boruvka on Minimum Spanning Tree Problem translation of the both 1926 papers comments history 2000 Jaroslav Nesetril Eva Milkova Helena Nesetrilova section 7 gives his algorithm which looks like a cross between Prim s and Kruskal s A Minimum Spanning Tree Algorithm with Inverse Ackermann Type Complexity Bernard Chazelle 1999 1 Thomas H Cormen Charles E Leiserson Ronald L Rivest and Clifford Stein Introduction to Algorithms Second Edition MIT Press and McGraw Hill 2001 ISBN 0 262 03293 7 Chapter 23 Minimum Spanning Trees pp 561 579 Two Algorithms for Generating Weighted Spanning Trees in Order Harold Gabow 1977 State of the Art Algorithms for Minimum Spanning Trees A Tutorial Discussion Jason Eisner 1997Enlaces externos EditarImplementado en BGL la Boost Graph Library Datos Q240464 Multimedia Minimum spanning trees Obtenido de https es wikipedia org w index php title Arbol recubridor minimo amp oldid 130223322, wikipedia, wiki, leyendo, leer, libro, biblioteca,
