ARBOLES
Un grafo T se denomina árbol si T es conexo y T no tiene ciclos. Ejemplos:
a) b)
Figura 8-17
El árbol que consta de un solo vértice sin aristas se denomina árbol degenerado.
Teorema
Sea G un grafo con n> 1 vértices. Entonces las siguientes afirmaciones son equivalentes:
i) G es un árbol.
ii) G es libre de ciclos y tiene n-1 aristas.
iii) G es conexo y tiene n-1 aristas.
Este teorema también indica que un árbol finito con n vértices debe tener n-1 aristas por
ejemplo ,observe la figura ( 8-17).
En a) tiene 9 vértices y 8 aristas.
b) tiene 13 vértices y 12 aristas.
“ Todo árbol tiene al menos dos vértices de grado 1, llamados hojas.”
“ Los vértices de grado > 1 se llaman vértices internos.”
“ La suma de los grados de un árbol con n vértices es: 2n-2 .”
Arboles de Expansión.
Un subgrafo T de un grafo conexo G se denomina árbol de expansión de G si T es un árbol y
T incluye a todos los vértices de G. En la figura 8-18 se muestra un grafo conexo G y árboles
de expansión T1,T2 y T3 de G.
Figura 8-18
Arboles de expansión mínima.
Suponga que G es un grafo ponderado conexo . Es decir a cada arista de G se asigna un
número no negativo denominado peso de la arista .Entonces a cualquier árbol de expansión
T de G se asigna un peso total que resulta de sumar los pesos de las aristas en T. Un árbol
de expansión mínima de G es un árbol de expansión cuyo peso total es el más pequeño
posible.
**Algoritmos para encontrar un árbol de expansión mínima T de un grafo ponderado conexo
G, donde G tiene n vértices .( En cuyo caso T debe tener n-1 aristas ).
Algoritmo 1
La entrada es un grafo ponderado conexo G con n vértices .
[Link] aristas de G se disponen en orden decreciente de peso .
Paso2. Se procede secuencialmente parta eliminar cada arista que no haga inconexo al
grafo, hasta que queden n-1 aristas.
[Link].
Algoritmo 2
La entrada es un grafo ponderado conexo G con n vértices.
Paso1 Las aristas de G se disponen en orden creciente de peso .
Paso2. Se empieza sólo con los vértices de G y en forma secuencial se agrega cada arista que
no origine un ciclo hasta que se hayan agregado n-1 aristas.
Paso3. Salir.
EJEMPLO: Encontrar un árbol de expansión mínima del grafo ponderado Q en la figura (8-
20)
Figura 8.20
SOLUCION
Se puede aplicar cualquiera de los dos algoritmos; en este caso aplicamos el (1).
Primero se ordenan las aristas en orden decreciente de peso y luego en forma consecutiva
se eliminan las aristas sin hacer inconexo a Q hasta que queden cinco aristas. (como se
muestra a continuación).
Aristas BC AF AC BE CE BF AE DF BD
Peso 8 7 7 7 6 5 4 4 3
Eliminar si si si no no si
Así el árbol de expansión mínima de Q que se obtiene contiene las aristas: BE,CE,AE,DF,BD.
Por lo tanto el peso de expansión es 6+4+7+3+4=24 finalmente las aristas quedaron así:
al eliminar BC al eliminar AF
al eliminar AC al eliminar BF
por lo tanto el peso del árbol de expansión es 6 + 4 + 7 + 3 +4 = 24 .
Grafos Planos
Un grafo o un multígrafo es plano cuando puede trazarse en el plano de modo que sus
aristas no se crucen ó se corten entre sí . Aunque grafo completo K4 con cuatro vértices suele
representarse con aristas cruzadas como se muestra en la figura (8.21 a).En la figura (8.21b)
vemos como se representa sus aristas sin cruzar ,k4 es plano.
a) b)
Figura 8.21
Mapas y Regiones
Una representación plana particular de un multígrafo plano finito se denomina mapa. Se
dice que el mapa es conexo si el multígrafo subyacente es conexo. Un mapa dado divide el
plano en varios regiones. Por ejemplo, el mapa en la figura (8.22).
Figura 8.22
4 de las regiones están acotadas y la 5º región, fuera del diagrama no está acotada. Se
nota que la frontera de cada región de un mapa consta de aristas. Algunas veces las aristas
forman un ciclo otras no. Por ejemplo en la fig.8.22, las fronteras de todas las regiones son
ciclos excepto para r3. Si se realiza un movimiento en el sentido contrario al movimiento.
De las manecillas del reloj alrededor de r3 empezando por ejemplo en el vértice C, entonces
se obtiene el camino cerrado: (C,D,E,F,E,C ).
Dónde la arista {E,F} ocurre dos veces. Por el grado de una región r ,que se escribe grd(r), se
entiende la longitud del ciclo o camino cerrado que rodea r. Cada arista delimita dos
regiones o está contenida en una región y ocurre dos veces en cualquier recorrido a lo largo
de la frontera de la región.
Teorema
La suma de los grados de las regiones de un mapa, es igual al doble del número de aristas.
Los grados de las regiones en la figura 8.22 son : Grd(r1)=3, grd(r2)=3, grd(r3)=5, grd(r4 )=4,
grd(r5) =3. La suma de los grados es 18 y como era de esperar es el doble del número de
aristas.
Fórmula de Euler:
Euler proporcionó la relación de el número V de vértices, el número E de aristas y el
número R de regiones de cualquier mapa conexo. Específicamente:
V – E + R = 2 de la figura 8.22 se tiene que : V= 6, E = 9 y R=5 por lo tanto sustituyendo e la
fórmula de euler se tiene, 6 -9 +5 = 2 . Se recalca que el grafo subyacente de un mapa debe
ser conexo para que se cumpla la fórmula de Euler.