Árbol de expansión

En el campo matemático 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 acerca de 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

Several pathfinding algorithms, including Dijkstra 's algorithm and the A* search algorithm, internally build a spanning tree as an intermediate step in solving the problem.

Para minimizar el coste de las redes eléctricas, conexiones de cableado, tuberías, reconocimiento automático de voz, etc., la gente suele utilizar 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 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 dichas redes (incluido el protocolo de árbol de expansión, abrir primero la ruta más corta, 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 género máximo. 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áximo asociada se pueden encontrar en tiempo polinomial.

Definiciones

Un árbol es un gráfico conectado no dirigido sin ciclos. Es un árbol de expansión de un grafo G si abarca G (es decir, incluye todos los vértices de G) y es un subgrafo 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; dicho ciclo se denomina ciclo fundamental con respecto a ese árbol. Hay un ciclo fundamental distinto para cada borde que no está en el árbol de expansión; por tanto, existe una correspondencia uno a uno entre los ciclos fundamentales y las aristas 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á V − 1 aristas y, por lo tanto, un gráfico de E aristas y uno de sus árboles de expansión tendrán E − V + 1 ciclos fundamentales (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, es decir, una base para el espacio de ciclo.

Cortes fundamentales

Dual a la noción de ciclo fundamental es la noción de un conjunto de corte fundamental con respecto a un árbol de expansión dado. Al eliminar solo un borde del árbol de expansión, los vértices se dividen en dos conjuntos separados. El cutset fundamental se define como el conjunto de aristas 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 V − 1 conjuntos de cortes fundamentales, uno para cada borde del árbol de expansión.

La dualidad entre conjuntos de cortes fundamentales y ciclos fundamentales se establece al observar que los bordes del ciclo que no están en el árbol de expansión solo pueden aparecer en los conjuntos de cortes de los otros bordes del ciclo; y viceversa: las aristas en un cutset sólo pueden aparecer en aquellos ciclos que contengan la arista correspondiente al cutset. 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 conjuntos de cortes fundamentales. de la misma manera desde la matroide dual.

Bosques extensos

Una colección de árboles separados (no conectados) se describe como un bosque (consulte Árbol_(estructura_de_datos)#Terminología). Un bosque extenso en un gráfico es un subgrafo que es un bosque con un requisito adicional. Hay dos requisitos incompatibles en uso, de los cuales uno es relativamente raro.

• Casi todos los libros y artículos de la teoría del gráfico definen un bosque azotado como un bosque que abarca todos los vértices, lo que significa que cada vértice del gráfico es un vértice en el bosque. Un gráfico conectado puede tener un bosque de azotes desconectado, como el bosque sin bordes, en el que cada vértice forma un árbol de un solo vértice.

• Unos pocos autores de la teoría gráfica definen un bosque de azotes como un subgrafo acíclico maximal del gráfico dado, o equivalentemente un subgrafo que consiste en un árbol de azotes en cada componente conectado del gráfico.

Para evitar confusión entre estas dos definiciones, Gross & Yellen (2005) sugiere el término "bosque de extensión total" para un bosque extenso con el mismo número de componentes que el gráfico dado (es decir, un bosque máximo), mientras que Bondy & Murty (2008) en cambio llama a este tipo de bosque un "bosque de máxima extensión" (lo cual es redundante, ya que un bosque máximo contiene necesariamente todos los vértices).

Contando árboles de expansión

El número t(G) de árboles de expansión de un gráfico conectado es una invariante bien estudiada.

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 del ciclo C_n con n vertices, entonces t()G)n.
• Para un gráfico completo con n vertices, la fórmula de Cayley da el número de árboles azotados como n^{n− 2}.
• Si G es el gráfico bipartito completo Kp,q{displaystyle K_{p,q}Entonces t()G)=pq− − 1qp− − 1{displaystyle t(G)=p^{q-1}q^{p-1}.
• Para el n- gráfico hipercubo dimensional Qn{displaystyle Q_{n}, el número de árboles azotados es t()G)=22n− − n− − 1∏ ∏ k=2nk()nk){displaystyle t(G)=2^{2^{n}-n-1}prod ¿Por qué?.

En gráficos arbitrarios

De manera más general, para cualquier gráfico G, el número t(G) se puede calcular en tiempo polinómico como determinante de una matriz. derivado del gráfico, utilizando el teorema del árbol matricial de Kirchhoff.

Específicamente, para calcular t(G), se construye la matriz laplaciana del gráfico, una matriz cuadrada en la que las filas y columnas están indexadas por los vértices. de G. La entrada en la fila i y la columna j es uno de tres valores:

• El grado de vértice i, si i=j,
• −1, si vértices i y j son adyacentes, o
• 0, si 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).

Contracción-eliminación

Si G es un gráfico o multigrafo y e es una arista arbitraria de G, entonces el número t >(G) de árboles de expansión de G satisface la recurrencia de contracción-deleción t(G) = t(G − e) + t(G/e), donde G − e es el multigrafo obtenido al eliminar yo 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 borde e, y el término t(G/e) cuenta los árboles de expansión de G que usa e.

En esta fórmula, si el gráfico dado G es un multigrafo, o si una contracción hace que dos vértices estén conectados entre sí por múltiples aristas, entonces no se deben eliminar los bordes sobrantes, ya que esto conduciría a un total incorrecto. Por ejemplo, un gráfico de enlaces que conecta dos vértices mediante k aristas tiene k árboles de expansión diferentes, cada uno de los cuales consta de uno solo de estos aristas.

Polinomio tutte

El polinomio de Tutte de un gráfico se puede definir como una suma, sobre los árboles generadores del gráfico, de términos calculados a partir de la "actividad interna" y "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 contracción-deleción, pero su complejidad computacional es alta: para muchos valores de sus argumentos, calcularlo exactamente es #P-completo, y también es difícil aproximarlo con un valor garantizado relación de aproximación. El punto (1,1), en el que se puede evaluar utilizando 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 mediante una búsqueda en profundidad o 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 la búsqueda en profundidad) o una cola (en el caso de la búsqueda en amplitud). En cualquier caso, se puede formar un árbol de expansión conectando cada vértice, distinto del vértice raíz v, al vértice desde el cual 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 de expansión llamados árboles de Trémaux, que llevan el nombre del descubridor de la búsqueda en profundidad en el siglo XIX.

Los árboles de expansión son importantes en la computación distribuida y paralela, como una forma de mantener las comunicaciones entre un conjunto de procesadores; consulte, por ejemplo, el protocolo Spanning Tree utilizado por los dispositivos de capa de enlace OSI o el Shout (protocolo) para informática distribuida. Sin embargo, los métodos de profundidad y 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.

Optimización

En ciertos campos de la teoría de grafos, suele ser ú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 hamiltoniana), el árbol generador de diámetro mínimo y el árbol generador de dilatación mínima.

También se han estudiado problemas de á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 forma que en un gráfico, utilizando la distancia euclidiana entre pares de puntos como peso para cada arista. Así, por ejemplo, un árbol de expansión mínimo euclidiano es lo mismo que un árbol de expansión mínimo de un 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 de manera más eficiente en tiempo O(n log n) construyendo la triangulación de Delaunay y luego se aplica 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 aleatoriamente entre todos los árboles de expansión con igual probabilidad se llama árbol de expansión uniforme. El algoritmo de Wilson se puede utilizar para generar árboles de expansión uniformes en tiempo polinómico mediante un proceso de realizar un recorrido aleatorio sobre el gráfico dado y borrar los ciclos creados por este recorrido.

Un modelo alternativo para generar árboles de expansión aleatoriamente pero no uniformemente 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, se conocen algoritmos que enumeran todos los árboles de expansión en tiempo polinomial por árbol.

En gráficos infinitos

Cada gráfico conexo finito tiene un árbol de expansión. Sin embargo, para infinitos gráficos conectados, la existencia de árboles generadores es equivalente al axioma de elección. Un grafo infinito es conexo si cada par de sus vértices forma el par de puntos finales 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 parcialmente ordenados 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 tengan un límite superior 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 supone el lema de Zorn, todo gráfico 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 todo gráfico 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 cada vértice distinto de v tiene un grado superior a 1. Esta definición sólo se cumple cuando las "ramas" de T apunta hacia v.