Árbol de expansión - Spanning tree
En la matemática campo de la teoría de grafos , un árbol de expansión T de un grafo no dirigido G es un subgrafo que es un árbol que incluye todos los vértices de G . 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 (consulte los bosques de expansión a continuación). Si todas las aristas de G son también aristas de un árbol de expansión T de G , entonces G es un árbol y es idéntico a T (es decir, un árbol tiene un árbol de expansión único y es él mismo).
Aplicaciones
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 paso intermedio para resolver el problema.
Para minimizar el costo de las redes eléctricas, 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 (o muchos árboles similares) 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 los nodos 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 , la ruta más corta abierta primero , el protocolo de enrutamiento de estado de enlace , el enrutamiento basado en árbol aumentado , etc., requieren que cada enrutador recuerde un árbol de expansión.
Un tipo especial de árbol de expansión, el árbol Xuong , se utiliza en la teoría de grafos topológicos para encontrar incrustaciones de grafos con el máximo género . Un árbol Xuong es un árbol de expansión tal que, en el gráfico restante, el número de componentes conectados con un número impar de aristas es lo más pequeño posible. Un árbol Xuong y una incrustación de género máxima asociada se pueden encontrar en tiempo polinomial .
Definiciones
Un árbol es un conectado grafo no dirigido sin ciclos . Es un árbol de expansión de un gráfico G si abarca G (es decir, incluye todos los vértices de G ) y es un subgráfico de G (cada borde del árbol pertenece a G ). Un árbol de expansión de un gráfico conectado G también se puede definir como un conjunto máximo de aristas de G que no contiene ningún ciclo, o como un conjunto mínimo de aristas que conectan todos los vértices.
Ciclos fundamentales
Agregar solo un borde a un árbol de expansión creará un ciclo; tal ciclo se llama ciclo fundamental . Hay un ciclo fundamental distinto para cada borde que no está en el árbol de expansión; por lo tanto, existe una correspondencia uno a uno entre los ciclos fundamentales y los bordes que no están en el árbol de expansión. Para un gráfico conectado con vértices V , cualquier árbol de expansión tendrá aristas V - 1 y, por lo tanto, una gráfica de aristas E y uno de sus árboles de expansión tendrá ciclos fundamentales E - V + 1 (el número de aristas restado por el número de aristas incluidas en un árbol de expansión; dando el número de aristas no incluidas en el árbol de expansión). Para cualquier árbol de expansión dado, el conjunto de todos los ciclos fundamentales E - V + 1 forma una base de ciclo , una base para el espacio de ciclo .
Cortes fundamentales
Doble a la noción de un ciclo fundamental es la noción de un corte fundamental . Al eliminar solo un borde del árbol de expansión, los vértices se dividen en dos conjuntos disjuntos. El conjunto de cortes fundamental se define como el conjunto de bordes que deben eliminarse del gráfico G para lograr la misma partición. Por lo tanto, cada árbol de expansión define un conjunto de cortes fundamentales V - 1, uno para cada borde del árbol de expansión.
La dualidad entre los cortes fundamentales y los ciclos fundamentales se establece al señalar que los bordes del ciclo que no están en el árbol de expansión solo pueden aparecer en los cortes de los otros bordes del ciclo; y viceversa : los bordes de un corte solo pueden aparecer en aquellos ciclos que contienen el borde correspondiente al corte. Esta dualidad también se puede expresar utilizando la teoría de las matroides , según la cual un árbol de expansión es una base de la matroide gráfica , un ciclo fundamental es el circuito único dentro del conjunto formado al agregar un elemento a la base, y se definen los cortes fundamentales. de la misma manera que el matroide dual .
Abarcando bosques
En los gráficos que no están conectados, no puede haber árbol de expansión y, en su lugar, se debe considerar la expansión de bosques . Aquí hay dos definiciones en competencia:
- Algunos autores consideran que un bosque de expansión es un subgráfico acíclico máximo del gráfico dado o, de manera equivalente, un gráfico que consta de un árbol de expansión en cada componente conectado del gráfico.
- Para otros autores, un bosque en expansión es un bosque que se extiende por todos los vértices, lo que significa solo que cada vértice del gráfico es un vértice en el bosque. Para esta definición, incluso un gráfico conectado puede tener un bosque de expansión desconectado, como el bosque en el que cada vértice forma un árbol de un solo vértice.
Para evitar confusiones entre estas dos definiciones, Gross y Yellen (2005) sugieren el término "bosque de extensión total" para un bosque de extensión con la misma conectividad que el gráfico dado, mientras que Bondy y Murty (2008) llaman a este tipo de bosque un " bosque de extensión máxima ".
Contando árboles que se extienden
El número t ( G ) de árboles de expansión de un gráfico conectado es un invariante bien estudiado .
En gráficos específicos
En algunos casos, es fácil calcular t ( G ) directamente:
- Si G es en sí mismo un árbol, entonces t ( G ) = 1 .
- Cuando G es el gráfico de ciclo C n con n vértices, entonces t ( G ) = n .
- Para un gráfico completo con n vértices, la fórmula de Cayley da el número de árboles de expansión como n n - 2 .
- Si G es el gráfico bipartito completo , entonces .
- Para el gráfico de hipercubo n- dimensional , el número de árboles de expansión es .
En gráficos arbitrarios
De manera más general, para cualquier gráfico G , el número t ( G ) se puede calcular en tiempo polinomial como el determinante de una matriz derivada del gráfico, utilizando el teorema del árbol de la matriz de Kirchhoff .
Específicamente, para calcular t ( G ), uno construye la matriz laplaciana de la gráfica, una matriz cuadrada en la que las filas y las columnas son tanto indexada por los vértices de G . La entrada en la fila i y la columna j es uno de tres valores:
- El grado del vértice i , si i = j ,
- −1, si los vértices i y j son adyacentes, o
- 0, si los vértices i y j son diferentes entre sí pero no adyacentes.
La matriz resultante es singular , por lo que su determinante es cero. Sin embargo, eliminar la fila y la columna de un vértice elegido arbitrariamente conduce a una matriz más pequeña cuyo determinante es exactamente t ( G ).
Deleción-contracción
Si G es un gráfico o multigrafo y e es un borde arbitrario de G , entonces el número t ( G ) de árboles de expansión de G satisface la deleción-contracción recurrencia T ( G ) = t ( G - e ) + t ( G / e ), donde G - e es la multigrafo obtenido mediante la eliminación de e y G / e es la contracción de G por e . El término t ( G - e ) en esta fórmula cuenta los árboles de expansión de G que no usan el borde e , y el término t ( G / e ) cuenta los árboles de expansión de G que usan e .
En esta fórmula, si el gráfico G dado es un multigraph , o si una contracción hace que dos vértices estén conectados entre sí por múltiples aristas, entonces las aristas redundantes no deben eliminarse, ya que eso daría lugar a un total incorrecto. Por ejemplo, un gráfico de enlace que conecta dos vértices por k aristas tiene k árboles de expansión diferentes, cada uno de los cuales consta de una sola de estas aristas.
Polinomio de Tutte
El polinomio de Tutte de un gráfico se puede definir como una suma, sobre los árboles de expansión del gráfico, de términos calculados a partir de la "actividad interna" y la "actividad externa" del árbol. Su valor en los argumentos (1,1) es el número de árboles de expansión o, en un gráfico desconectado, el número de bosques de expansión máximos.
El polinomio de Tutte también se puede calcular usando una recurrencia de deleción-contracción, pero su complejidad computacional es alta: para muchos valores de sus argumentos, calcularlo exactamente es # P-completo , y también es difícil de aproximar con una proporción de aproximación garantizada . El punto (1,1), en el que se puede evaluar mediante el teorema de Kirchhoff, es una de las pocas excepciones.
Algoritmos
Construcción
Se puede encontrar un único árbol de expansión de un gráfico en tiempo lineal ya sea mediante búsqueda en profundidad o búsqueda en amplitud . Ambos algoritmos exploran el gráfico dado, comenzando desde un vértice arbitrario v , recorriendo los vecinos de los vértices que descubren y agregando cada vecino inexplorado a una estructura de datos que se explorará más adelante. Se diferencian en si esta estructura de datos es una pila (en el caso de búsqueda en profundidad) o una cola (en el caso de búsqueda en amplitud). En cualquier caso, se puede formar un árbol de expansión conectando cada vértice, que no sea el vértice raíz v , al vértice desde el que se descubrió. Este árbol se conoce como árbol de búsqueda en profundidad o árbol de búsqueda en amplitud según el algoritmo de exploración de gráficos utilizado para construirlo. Los árboles de búsqueda en profundidad son un caso especial de una clase de árboles extensibles llamados árboles Trémaux , que llevan el nombre del descubridor del siglo XIX de la búsqueda en profundidad.
Los árboles de expansión son importantes en la computación paralela y distribuida, como una forma de mantener las comunicaciones entre un conjunto de procesadores; consulte, por ejemplo, el Protocolo de árbol de expansión utilizado por los dispositivos de capa de enlace OSI o el (protocolo) Shout para la computación distribuida. Sin embargo, los métodos de primero en profundidad y primero en amplitud para construir árboles de expansión en computadoras secuenciales no son adecuados para computadoras paralelas y distribuidas. En cambio, los investigadores han ideado varios algoritmos más especializados para encontrar árboles de expansión en estos modelos de cálculo.
Mejoramiento
En ciertos campos de la teoría de grafos, a menudo es útil encontrar un árbol de expansión mínimo de un gráfico ponderado . También se han estudiado otros problemas de optimización en árboles de expansión, incluido el árbol de expansión máximo, el árbol mínimo que abarca al menos k vértices, el árbol de expansión con la menor cantidad de aristas por vértice , el árbol de expansión con el mayor número de hojas , el árbol de expansión con la menor cantidad de hojas (estrechamente relacionado con el problema de la trayectoria de Hamilton ), el árbol de expansión de diámetro mínimo y el árbol de expansión de dilatación mínima.
También se han estudiado los problemas del árbol de expansión óptimo para conjuntos finitos de puntos en un espacio geométrico como el plano euclidiano . Para tal entrada, un árbol de expansión es nuevamente un árbol que tiene como vértices los puntos dados. La calidad del árbol se mide de la misma manera que en un gráfico, utilizando la distancia euclidiana entre pares de puntos como el peso de cada borde. Así, por ejemplo, un árbol de expansión mínimo euclidiano es lo mismo que un árbol de expansión mínimo de gráfico en un gráfico completo con pesos de borde euclidianos. Sin embargo, no es necesario construir este gráfico para resolver el problema de optimización; el problema del árbol de expansión mínimo euclidiano, por ejemplo, se puede resolver más eficientemente en tiempo O ( n log n ) construyendo la triangulación de Delaunay y luego aplicando un algoritmo de árbol de expansión mínimo de gráfico plano de tiempo lineal a la triangulación resultante.
Aleatorización
Un árbol de expansión elegido al azar entre todos los árboles de expansión con la misma probabilidad se denomina árbol de expansión uniforme . El algoritmo de Wilson se puede utilizar para generar árboles de expansión uniformes en tiempo polinomial mediante un proceso de realizar una caminata aleatoria en el gráfico dado y borrar los ciclos creados por esta caminata.
Un modelo alternativo para generar árboles de expansión de forma aleatoria pero no uniforme es el árbol de expansión mínimo aleatorio . En este modelo, a los bordes del gráfico se les asignan pesos aleatorios y luego se construye el árbol de expansión mínimo del gráfico ponderado.
Enumeración
Debido a que un gráfico puede tener exponencialmente muchos árboles de expansión, no es posible enumerarlos todos en tiempo polinomial . Sin embargo, los algoritmos son conocidos por enumerar todos los árboles de expansión en tiempo polinomial por árbol.
En gráficos infinitos
Cada gráfico conectado finito tiene un árbol de expansión. Sin embargo, para gráficos infinitos conectados, la existencia de árboles de expansión es equivalente al axioma de elección . Un grafo infinito está conectado si cada par de sus vértices forma el par de extremos de un camino finito. Al igual que con los gráficos finitos, un árbol es un gráfico conectado sin ciclos finitos, y un árbol de expansión se puede definir como un conjunto acíclico máximo de aristas o como un árbol que contiene todos los vértices.
Los árboles dentro de un gráfico pueden estar ordenados parcialmente por su relación de subgrafo, y cualquier cadena infinita en este orden parcial tiene un límite superior (la unión de los árboles en la cadena). El lema de Zorn , uno de los muchos enunciados equivalentes al axioma de elección, requiere que un orden parcial en el que todas las cadenas están delimitadas por arriba tenga un elemento máximo; en el orden parcial de los árboles del gráfico, este elemento máximo debe ser un árbol de expansión. Por lo tanto, si se asume el lema de Zorn, cada grafo infinito conectado tiene un árbol de expansión.
En la otra dirección, dada una familia de conjuntos , es posible construir un gráfico infinito tal que cada árbol de expansión del gráfico corresponda a una función de elección de la familia de conjuntos. Por lo tanto, si cada grafo infinito conectado tiene un árbol de expansión, entonces el axioma de elección es verdadero.
En multigrafos dirigidos
La idea de un árbol de expansión se puede generalizar a multigrafos dirigidos. Dado un vértice v en un multigrafo dirigido G , un árbol de expansión orientado T con raíz en v es un subgrafo acíclico de G en el que todos los vértices que no sean v tienen un grado superior a 1. Esta definición solo se satisface cuando las "ramas" de T apuntan hacia v .
Ver también
- Algoritmo de inundación
- Buen árbol de expansión: árbol de expansión para gráficos planos incrustados