Árboles de Expansión

ÁRBOLES DE EXPANSIÓN
En esta sección consideraremos el problema de determinar una subgráfica T de una gráfica G de modo que T sea un árbol con todos los vértices de G; es decir, un árbol deexpansión. Veremos que los modos para determinar árboles de expansión se pueden aplicar también a otros problemas.


Un árbol T es un árbol de expansión de una gráfica G Si T es una subgráfica de G quecontiene a todos los vértices de G.


(Ejemplos de árboles de expansión de la misma gráfica, representadas en las líneas puntadas)

Suponga que una grafica G tiene un árbol de expansión T. Sean a yb vértices de G. Como a y b son también vértices de T y T es un árbol, existe un camino P de a a b. Sin embargo, P también sirve como un camino de a a b en G; así, G es conexa. El reciproco también esverdadero.


Una grafica G tiene un árbol de expansión si y sólo si G es conexa.


Si G tiene un árbol de expansión, entonces G es conexa. Supongamos que G es conexa. Si G es acíclica, G es unárbol.
Supongamos que G contiene un ciclo. Eliminamos una arista (pero no los vértices) de este ciclo. La gráfica producida sigue siendo conexa. Si es acíclica, nos detenemos. Si contiene un ciclo,eliminamos una arista de este ciclo. Continuamos de esta manera hasta obtener una subgráfica acíclica, conexa. Como T contiene a todos los vértices de G, T es un árbol de expansión de G.

Utilizaremosun método llamado búsqueda a lo ancho. La idea de la búsqueda a lo ancho es procesar todos los vértices de un nivel dado antes de pasar al siguiente nivel superior.
Primero, elegimos un orden,digamos abcdefgh, de los vértices de G. Elegimos el primer vértice a y lo etiquetamos como la raíz. Sea T la gráfica formada por el único vértice a, sin aristas. Agregamos a T todas las aristas (a, x) ylos vértices sobre los cuales son incidentes, desde x = b hasta h, que no produzcan un ciclo al agregarse a T. Así, agregamos a T las aristas (a, b), (a, c) y (a, g). (Podemos usar cualesquiera de...