Árbol de expansión

Un árbol de expansión (aristas azules gruesas) de un grafo de rejilla.

En el campo matemático de la teoría de grafos, un árbol de expansión T de un grafo conexo, no dirigido G es un árbol compuesto por todos los vértices y algunas (quizá todas) de las aristas de G. Informalmente, un árbol de expansión de G es una selección de aristas de G que forman un árbol que cubre todos los vértices. Esto es, cada vértice está en el árbol, pero no hay ciclos. Por otro lado, todos los puentes de G deben estar contenidos en T.

Un árbol de expansión o árbol recubridor de un grafo conexo G puede ser también definido como el mayor conjunto de aristas de G que no contiene ciclos, o como el mínimo conjunto de aristas que conecta todos los vértices.

En ciertos campos de la teoría de grafos es útil encontrar el mínimo árbol de expansión de un grafo ponderado. También se han abordado otros problemas de optimización relacionados con los árboles de expansión, como el máximo árbol de expansión, el máximo árbol que cubre al menos k vértices, el mínimo árbol de expansión con k aristas por vértice como máximo (árbol de expansión de mínimo grado, MDST por sus siglas en inglés), el árbol de expansión con el máximo número de hojas (estrechamente relacionado con el problema del menos conjunto dominante y conexo), el árbol de expansión con el menor número de hojas (relacionado con el problema del camino hamiltoniano), el árbol de expansión de mínimo diámetro o el árbol de expansión de la mínima dilación.

Ciclos fundamentales y cortes fundamentales

Si se añade una sola arista a un árbol de expansión, se crea un ciclo: los ciclos de ese tipo se denominan ciclos fundamentales. Hay un ciclo fundamental distinto para cada arista; es decir, hay una correspondencia biyectiva (uno a uno) entre ciclos fundamentales y aristas ausentes del árbol de expansión. Para un grafo conexo con V vértices, cualquier árbol de expansión tiene V-1 aristas, y así, un grafo con E aristas tiene E-V+1 ciclos fundamentales. En cualquier árbol de expansión dado, esos ciclos forman una base del espacio de ciclos.

De manera dual a la noción de ciclo fundamental, existe el concepto de corte fundamental. Al eliminar una arista del árbol de expansión, los vértices se dividen en dos conjuntos disjuntos (desconectados). El corte fundamental se define como el conjunto de aristas que deben ser eliminados de un grafo G para llegar a la misma división. Por tanto, hay exactamente V-1 cortes fundamentales en un grafo, uno por cada arista del árbol de expansión.

La dualidad entre cortes y ciclos fundamentales se manifiesta al observar que las aristas de un ciclo que no pertenece al árbol de expansión sólo pueden aparecer en los cortes de otras aristas del ciclo, y viceversa: las aristas en un corte sólo pueden aparecer en aquellos ciclos no contenidos en la arista correspondiente al corte.

Bosques de expansión

Un bosque de expansión es un tipo de subgrafo que generaliza el concepto de árbol de expansión. Hay dos definiciones de uso común:

• Según la primera, un bosque de expansión es un subgrafo que consiste en un árbol de expansión en cada componente conexo del grafo (equivalentemente, es un subgrafo libre de ciclos maximal). Esta definición es frecuente en informática y optimización, así como la que se emplea habitualmente al tratar los bosques mínimos de expansión, la generalización a subgrafos disconexos de árboles de expansión minimales.

• Otra definición, empleada en teoría de grafos, es la de un bosque de expansión es un subgrafo que es a la vez bosque (es decir, no contiene ciclos) y de expansión (es decir, incluye a todos los vértices).

Conteo de árboles de expansión

El número t(G) de árboles de expansión de un grafo conexo es un invariante importante. En algunos casos, es fácil calcular t(G) directamente, y es un elemento de uso frecuente en estructuras de datos en distintos lenguajes de programación.

Trivialmente, si G es un árbol, entonces t(G)=1. Si G es un ciclo C_n con n vértices, entonces t(G)=n.

Para un grafo genérico G, el número t(G) puede obtenerse a través del teorema de matriz-árbol de Kirchhoff.

La fórmula de Cayley es una fórmula para obtener el número de árboles de expansión en un grafo completo K_n con n vértices. La fórmula establece que t(K_n) = n^{n − 2}. Otra prueba de la fórmula de Cayley es la existencia de exactamente n^{n − 2} árboles etiquetados con n vértices. La fórmula de Cayley puede ser demostrada mediante el teorema de matriz-árbol de Kirchhoff o mediante el código de Prüfer.

Si G es un grafo completo bipartido K_p,q, entonces se cumple t(G) = p^{q − 1}q^{p − 1}. Si G es el grafo hipercúbico n-dimensions Q_n, entonces se verifica que . Estas fórmulas son también corolarios del teorema matriz-árbol.

Si G es un multigrafo y e es una arista de G, entonces el número t(G) satisface la recurrencia de supresión-contracción:

t(G) = t(G − e) + t(G / e)

donde G-e es el multigrafo que se obtiene al eliminar la arista e, y G/e es la contracción de G sobre e, en la que las múltiples aristas de esta contracción no son eliminadas.

Árboles de expansión uniforme

Un árbol de expansión escogido aleatoriamente, con igual probabilidad, entre todos los árboles de expansión se denomina árbol de expansión uniforme (AEU). Este modelo ha sido ampliamente investigado en los ámbitos de la Probabilidad y la Física matemática.

Algoritmos

El algoritmo clásico para los árboles de expansión, Depth-First Search (DFS, búsqueda priorizando la profundidad en español), fue diseñado por Robert Tarjan. Otro algoritmo relevante está basado en la búsqueda priorizando la amplitud (Breadth-First Search, BFS).