Introducción:
- Un árbol de expansión T de un gráfico G no dirigido es un subgráfico que es un árbol que incluye todos los vértices de G, con el mínimo número posible de aristas.
- En general, un gráfico puede tener varios árboles de expansión, pero un gráfico que no está conectado no contendrá un árbol de expansión.
- Si todos los bordes de G son también bordes de un árbol de expansión T de G, entonces G es un árbol y es idéntico a T, eso significa que un árbol tiene un árbol de expansión único y es él mismo.
Definición:
- Un árbol es un gráfico conectado no dirigido sin ciclos. Es un árbol de expansión de un gráfico G si incluye todos los vértices de G y es un subgrafo de G significa que cada borde del árbol pertenece a G.
- Un árbol de expansión de un gráfico G conectado también se puede definir como un conjunto máximo de bordes de G que no contiene ningún ciclo, o como un conjunto mínimo de bordes que conectan todos los vértices.
- El peso de un árbol de expansión es la suma de los pesos dados a cada borde del árbol de expansión.
Aplicaciones:
- ¿Cuál es el mejor algoritmo para encontrar si 3 números son coprimos? ¿Como funciona?
- ¿Puedo obtener el algoritmo para un enfoque iterativo en una búsqueda binaria de doble pivote?
- ¿Qué es mejor entre la búsqueda binaria y el árbol de búsqueda binaria para buscar?
- ¿En qué punto una gran notación O de velocidad de aumento más rápida ignora una notación O grande de velocidad de aumento más lenta?
- ¿Cuáles son los algoritmos necesarios para resolver div2 500 y div2 1000 fácilmente en topcoder?
- Varios algoritmos de búsqueda de rutas, incluido el algoritmo de Dijkstra y el algoritmo de búsqueda A *, construyen internamente un árbol de expansión como un paso intermedio para resolver el problema.
- Con el fin de minimizar el costo de las redes de energía, conexiones de cableado, tuberías, reconocimiento automático de voz, etc., las personas a menudo usan algoritmos que construyen gradualmente un árbol de expansión como pasos intermedios en el proceso de encontrar el árbol de expansión mínimo.
- Internet y muchas otras redes de telecomunicaciones tienen enlaces de transmisión que conectan nodos entre sí en una topología de malla que incluye algunos bucles.
- Para “evitar bucles de puente y” bucles de enrutamiento “, muchos protocolos de enrutamiento diseñados para tales redes, incluido el Protocolo de árbol de expansión, Abrir primero la ruta más corta, el protocolo de enrutamiento de estado de enlace, Enrutamiento basado en árbol aumentado, etc., requieren cada enrutador para recordar un árbol de expansión.
