Arboles

ARBOLES

Definición:
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 esconexo y no contiene ciclos.
Teorema
1. En un árbol es un grafo de dos vértices cualesquiera que están unidos por un único camino.
2. Un grafo G es conexo si y sólo si tieneun árbol generador.
3. Si G es un árbol, entonces el número de aristas es igual al número de vértices menos uno.
Ejemplo:


Vértice Hijo: Cualquiera de los vértices apuntadospor uno de los vértices del árbol. En el ejemplo anterior V5, V6 son hijos de V4.
Vértice Padre: Vértice que contiene un puntero al vértice actual. En el ejemplo, el vérticeV1 es padre de V4 y V5.
Los árboles con los que trabajaremos tienen otra característica importante: cada nodo sólo puede
ser apuntado por otro nodo, es decir, cada nodo sólotendrá un padre. Esto hace que estos
árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles.
En cuanto a la posición dentro delárbol:
• Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el
ejemplo, ese nodo es el 'A'.
• Nodo hoja: nodo que no tiene hijos. Enel ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.
• Nodo rama: son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el
ejemplo: 'B','C', 'D', 'E', 'G' y 'J'.
Ejemplo de aplicación de árboles













Arboles:
Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices.
SeaG =(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.