arboles y redes
Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices.
Sea G =(V,A) un grafo no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos.
Un árbol con raíz, es un árbol que tiene un vértice particular designado como raíz.
Ejemplo de árbol:
En la figura anterior G1 corresponde a lo que llamamos mediante la definición ARBOL, en el caso de G2, éste no corresponde debido a que contiene un ciclo.
Ejemplo de árbol raíz:
Para apoyar el entendimiento de las definiciones entregadas agregaremos algunos teoremas.
Teorema:
Si a, b son vértices de un árbol R (V,A), entonces hay un camino único que conecta estos vértices.
Teorema:
En cualquier árbol R= (V,A), |V| = |A| + 1.
Teorema:
Para cualquier árbol R = (V,A), si |A| >= 2, entonces R tiene al menos dos vértices colgantes.
Teorema:
Sea G un grafo simple con v vértices, entonces se puede decir:
G es un árbol.
G es conexo y no contiene circuitos.
G es conexo y tiene (n-1) lados.
G no contiene circuitos y tiene (n-1) lados.
Arboles con Raíz
Sea G un grafo dirigido, se denomina “árbol dirigido” si el grafo no dirigido asociado con G es un árbol. Cuando G es un árbol dirigido, se denomina “árbol con raíz” si hay un único vértice r, la raíz.
Sea G un grafo con raíz V0. Supóngase que x, y, z son vértices en G y que (v0, v1, ..., vn), es un camino en G.
V(n-1) es el padre de v(n).
V0, v1, ..., v(n-1) son los antepasados de v(n).
V(n) es el hijo de v(n-1).
Si x es un antepasado de y, entonces y es un descendiente de x.
El subgrafo de G que consiste en x y todos sus descendientes, con x como raíz, es el subarbol de G que tiene a x como raíz.