Árbol de expansión

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 19 de septiembre de 2021; las comprobaciones requieren 2 ediciones .

El árbol de expansión de un gráfico es un árbol , un subgráfico de un gráfico dado, con el mismo número de vértices que el gráfico original. Hablando de manera informal, se obtiene un árbol de expansión del grafo original eliminando el número máximo de aristas incluidas en los ciclos, pero sin romper la conectividad del grafo. El árbol de expansión incluye todos los vértices del gráfico original y contiene un borde. $norte$ $n-1$

Definición

Un árbol de expansión es un subgrafo conectado acíclico de un gráfico no dirigido conectado dado que incluye todos sus vértices .

El concepto de un bosque extenso es ambiguo; puede significar uno de los siguientes subgrafos:

cualquier subgrafo acíclico que contenga todos los vértices del gráfico, pero no necesariamente conectados;
en un grafo desconectado, un subgrafo que consiste en la unión de árboles de expansión para cada uno de sus componentes conectados .

Un árbol de expansión también se denomina a veces árbol de expansión, árbol de expansión o esqueleto de gráfico . El acento en la palabra "ostovny" de diferentes autores se indica en la primera (de la palabra ostov) o en la segunda sílaba.

Propiedades

Cualquier árbol de expansión en un gráfico de vértices contiene exactamente una arista. $norte$ $n-1$
El número de árboles de expansión en un gráfico completo en los vértices es igual a esta declaración se llama fórmula de Cayley [1] : $norte$ ${\ estilo de visualización n^{n-2};}$
El número de árboles de expansión en un gráfico bipartito completo es $K_{{m, n}}$ $m^{n-1}\cdotn^{m-1}.$
En general, el número de árboles de expansión en un gráfico arbitrario se puede calcular usando el llamado teorema del árbol matriz .
Sea una arista en un grafo , denótese por la gráfica obtenida de la eliminación de la arista y por la gráfica obtenida de la contracción de la arista a un punto. Si el borde no es un bucle, entonces la siguiente relación es verdadera, llamada eliminación más contracción [2] : $\rho$ ${\ estilo de visualización \ gamma.}$ ${\ estilo de visualización \ gamma \ barra invertida \ rho}$ $\Gama$ ${\ estilo de visualización \ rho,}$ ${\ estilo de visualización \ gamma / \ rho}$ $\Gama$ $\rho$ $\rho$ ${\ estilo de visualización \ gamma,}$ ${\ estilo de visualización \ tau (\ Gamma) = \ tau (\ Gamma \ barra invertida \ rho) + \ tau (\ Gamma / \ rho),}$

donde denota el número de árboles de expansión en el gráfico

{\ estilo de visualización \ tau (\ gamma)}

{\ estilo de visualización \ gamma.}

Algoritmos

Un árbol de expansión se puede construir con casi cualquier algoritmo transversal de gráfico, como la búsqueda primero en profundidad o la búsqueda primero en amplitud . Consiste en todos los pares de aristas tales que el algoritmo, mirando un vértice , encuentra un vértice nuevo, previamente no descubierto en su lista de adyacencia. ${\ estilo de visualización (u, v),}$ $tu,$ ${\ estilo de visualización v.}$

Los árboles de expansión construidos al atravesar un gráfico desde un vértice por el algoritmo de Dijkstra tienen la propiedad de que el camino más corto en el gráfico desde cualquier otro vértice es (también es el único) camino desde este vértice en el árbol de expansión construido. $s$ $s$ $s$

También hay varios algoritmos de árbol de expansión paralelos y distribuidos. Como ejemplo práctico de algoritmo distribuido se puede dar el protocolo STP .

Si a cada borde del gráfico se le asigna un peso (longitud, costo, etc.), entonces se involucran numerosos algoritmos para encontrar el árbol de expansión mínimo para encontrar el árbol de expansión óptimo, que minimiza la suma de los pesos de los bordes incluidos en él. .

El problema de encontrar un árbol de expansión en el que el grado de cada vértice no exceda alguna constante predeterminada , es NP-completo [3] . $k,$

La selección del árbol de expansión y el conteo del número de aristas remotas en los gráficos de circuitos eléctricos se utiliza para calcular el número de circuitos independientes en el análisis del circuito eléctrico por el método de las corrientes de circuito [4] .

Véase también

Notas

↑ Martin Aigner, Günter M. Ziegler. Pruebas del libro . - Springer-Verlag, 2004. - P. 173-178 . — ISBN 978-3540404606 .
↑ Petrunin A. Cuántos árboles hay en un gráfico // Kvant . - 2018. - Nº 9 . - S. 9-13 . -doi : 10.4213 / kvant20180902 . (Ruso)
↑ Michael R. Garey, David S. Johnson. Computadoras e intratabilidad: una guía para la teoría de la integridad NP . - W. H. Freeman, 1979. - S. 206 . — ISBN 0-7167-1045-5 .
↑ Bessonov L. A. Fundamentos teóricos de la ingeniería eléctrica. Circuitos electricos. - M. : Gardariki, 2002. - 638 p. — ISBN 5-8297-0026-3 .