Árbol de expansión

Á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.

Contenido

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 Cn 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 Kn con n vértices. La fórmula establece que t(Kn) = nn − 2. Otra prueba de la fórmula de Cayley es la existencia de exactamente nn − 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 Kp,q, entonces se cumple t(G) = pq − 1qp − 1. Si G es el grafo hipercúbico n-dimensions Qn, entonces se verifica que t(G)=2^{2^n-n-1}\prod_{k=2}^n k^{{n\choose k}}. 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(Ge) + 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).


Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Árbol (teoría de grafos) — Para otros usos de este término, véase Árbol (desambiguación). Árbol Árbol etiquetado con 6 vértices y 5 aristas. El único camino simple que conecta los vértices 2 y 6 es 2 4 5 6 …   Wikipedia Español

  • Expansión utoazteca — Saltar a navegación, búsqueda Expansión de las lenguas uto aztecas hacia el sur. La expansión utoazteca designa el proceso histórico cultural y demográfico de difusión y migración de pueblos y culturas que hablaban lenguas uto aztecas, desde el… …   Wikipedia Español

  • Expansión afroasiática — Saltar a navegación, búsqueda Mapa de lenguas afroasiáticas que muestra las rutas probables de expansión de pueblos afroasiáticos, de acuerdo con Ehret (1995) La expansión afroasiática designa el proceso histórico cultural y demográfico de… …   Wikipedia Español

  • Árbol filogenético — Introducción teórica en Filogenia Diagrama dibujado por Charles Darwin en El origen de las especies. Un árbol filogenético es un árbol que muestra las relaciones evolutivas entre varias especies u otras entidades que se cree que tienen una… …   Wikipedia Español

  • El Árbol — Saltar a navegación, búsqueda Supermercados El Árbol es un grupo de distribución de origen español y que actualmente ocupa el noveno puesto por superficie de ventas en el país. El grupo cuenta con 370 supermercados y 38 Max Descuento (tipo Cash… …   Wikipedia Español

  • Pando (árbol) — Saltar a navegación, búsqueda Pando (o El Gigante Tembloroso)[1] es una colonia clonal a partir de un álamo temblón masculino (Populus tremuloides) localizado en el estado norteamericano de Utah. A partir de marcadores genéticos se ha determinado …   Wikipedia Español

  • El árbol de la vida (película de 2011) — Para la película de 1957 del mismo nombre, véase El árbol de la vida. The Tree of Life Título El árbol de la vida (película de 2011) Ficha técnica Dirección Terrence Malick …   Wikipedia Español

  • Secuencia de Prüfer — En matemática combinatoria, la secuencia de Prüfer (o código de Prüfer) de un árbol etiquetado es una secuencia única asociada al árbol. La secuencia de un árbol con n vértices tiene longitud n − 2, y puede ser generada por un algoritmo iterativo …   Wikipedia Español

  • Anexo:Glosario de teoría de grafos — Grafo simple no dirigido, con 6 vértices y 7 aristas. A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal correspondiente. Todos los… …   Wikipedia Español

  • Algoritmo de Kruskal — El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”