ÁRBOL DE EXPANSIÓN MINIMA

En teoría de grafos, un árbol de expansión, árbol generador o árbol recubridor  de un grafo conexo, no dirigido G es un árbolcompuesto 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.

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  (uno a uno) entre ciclos fundamentales y aristas ausentes del árbol de expansión. Para un grafo biyectiva 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. 

En teoría de grafos, un árbol de expansión, árbol generador o árbol recubridor  de un grafo conexo, no dirigido G es un árbolcompuesto 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.