Arboles Matematicas

Un problema importante que está asociado a una red representada por un grafo consiste en obtener un árbol

de expansión para el grafo. Este árbol de expansión debe contener todos los vértices del grafo y algunas de sus

aristas, para asegurar su conectividad.

Definición: Un Árbol de Expansión de un grafo conexo no dirigido G = (N, A) es un árbol libre con el conjunto

de vértices N que es un subgrafo de G; esto es, un árbol de expansión es conexo, acíclico y tiene a todo N como

vértices y aparte de A como conjunto de aristas.

Teorema: Un grafo G tiene un árbol de expansión si y sólo si G es conexo.

Hay muchos enfoques para generar un árbol de expansión correspondiente a un grafo dado. Un enfoque

consiste en eliminar las aristas que pertenezcan a circuitos uno tras otro hasta que no queden circuitos en el

grafo. Si solo se eliminan aristas de circuitos, entonces el grafo seguirá siendo conexo, y esto es esencial para

la generación de un árbol de expansión.

Un ejemplo de este enfoque se ilustra en la Figura, En este caso se decide eliminar los pares de aristas

siguientes: {2, 5}, {2, 6}, {3, 6}, {3, 7}, {4, 7}, {6, 7}. Obsérvese que se podrían generar muchos árboles de

expansión a partir del grafo dado.

Ejemplo de obtención de un árbol de expansión a partir de un grafo.

Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología

1

...