Arboles Como Grafos

ARBOLES COMO GRAFOS
Un árbol es un grafo conexo no dirigido que no contiene circuitos simples.

Un grafo no dirigido es un árbol si y solo si hay un único camino simple entre cualquiera dos de sus vértices.

Un bosque es un grafo no dirigido que no contiene circuitos simples.

Arboles dirigidos – Arboles con raíz

* Un árbol dirigido es un árbol con un vértice distinguido como raíz ytal que cada arista apunta del vértice más cercano a la raíz al más lejano.

Ejemplo:

Este es un árbol dirigido

* Un árbol dirigido es un árbol enraizado si existe exactamente un vértice cuyo grado de entrada sea 0 y los grados de entrada de los otros vértices sea 1. El vértice con grado de entrada 0 es llamado raíz del árbol enraizado.

Ejemplo:
*
Árbol enraizado
* En unárbol enraizado, un vértice cuyo grado de salida sea 0 se llama nodo hoja o nodo terminal, y un vértice cuyo grado de salidas sea diferente de 0 se llama nodo rama o nodo interno.
Ejemplo:
Sea el siguiente árbol dirigido
*
Entonces:
Los nodos a, b, c, f, h son nodos rama y los nodos d, e, g, i, j, k, l son nodos hoja.

* Sea a un nodo rama en un árbol enraizado. Diremos que un vérticeb es un hijo de a si existe una arista de a b. Además se dice que el vértice a es el padre de b. Dos vértices son hermanos si son hijos del mismo vértice. Diremos que un vértice c es un descendiente de a si existe un paseo dirigido de a a c. Además, se dice a es un ancestro c.

Ejemplo:
Sea el siguiente árbol dirigido
*

Entonces:
b, c son hijos de a
d, e, f son hijos de b
g, h sonhijos de c
i, j, k son hijos de f
l es hijo de h | a es padre de b, c
b es padre de d, e, f
c es padre de g, h
f es padre de i, j, k
h es padre de l | b, c son hermanos
d, e, f son hermanos
g, h son hermanos
i, j, k son hermanos
l no tiene hermanos |

Además:
b, ,c, d, e, f, g, h, i, j, k, l son descendientes de a
d, e, f, i, j, k son descendientes de b
i, j, k son descendientesde f
g, h, l son descendientes de c
l es descendiente de h | a es ancestro de b ,c, d, e, f, g, h, i, j, k, l
b es ancestro de d, e, f, i, j, k
f es ancestro de i, j, k
c es ancestro de g, h, l
h es ancestro de l |

* Sea a un nodo rama en un árbol T. Por el subárbol con raíz a entendemos el subgrafo T'= (V', E') de T tal que V' contiene a a y a todas sus descendientes y E'contiene las aristas de todos los paseos dirigidos que surjan de a. Por un subárbol de a entendemos un subárbol que tiene a a como raíz.
Ejemplo:
Sea el siguiente árbol dirigido T

Entonces
i) | ii) |  iii) |

i), ii) y iii) son subárboles de T cuyas raíces son b, f y c respectivamente.

Centro de un Árbol y Excentricidad

El centro de un árbol T esta formado por uno o dos vértices de T.Teorema (Jordan, 1869). El centro de un árbol T es un vértice o una arista.

Algoritmo para obtener el centro de un árbol

Entrada: Un árbol T
Salida: El centro del árbol C(T)
Paso 1. Hacer H=T
Paso 2. Si H= K1 ó K2, entonces C(T)=H.
Paso 3. En caso contrario borrar todas las hojas de H para obtener un árbol H’. Hacer H’=H y volver al paso 2

Sea T un árbol y v un nodo del árbol. Laexcentricidad de v es el largo del mayor camino simple en T que empieza en v. El nodo v es un centro de T si no existe v’ con menor excentricidad que v.

ARBOLES DE EXPANSION

Definición: Sea G un grafo, si un subgrafo de expansión T de G es un árbol,
Entonces a T se le llama un árbol de expansión de G.

Un árbol de expansión o árbol recubridor de un grafo conexo G puede ser también definido comoel mayor conjunto de aristas de G que no contiene ciclos, o como el mínimo conjunto de aristas que conecta todos los vértices.

Ejemplo:

Búsqueda a lo ancho

Búsqueda en profundidad

APLICACIONES
Los spanning trees son útiles en ciertas tareas de los protocolos de Internet.
Asuma que tiene un computador que quiere enviar información a múltiples computadores.
Una solución es...