Arboles

Arboles
Estructura de árbol
En la teoría de los grafos un árbol es un grafo no dirigido, conexo y sin ciclos.
Donde al ser conexo une todos los nodos por ejemplo:
A
B
D
C
E

Además para ser un árbol no debe de tener ciclos, el siguiente grafo no es un árbol ya que incluye el ciclo A-B-C:
A
B
D
C
E

Así pues si a un árbol se le agrega una arista crea un ciclo y si se le quitadeja de ser conexo.
A
B
D
C
E
A
B
D
C
E
A
B
D
C
E

Arbol
Grafo con
ciclos
Grafo no
conexo

Partes del árbol:
La raíz, es el nodo que se ha denominado de tal manera y las aristas se alejan de él.
En el ejemplo A seria el nodo raíz.
A
B
D
C
E
F
G

Un nodo es padre de otro cuando esta unido mediante una arista y este se encuentra mas cerca de la raíz, en el ejemploanterior C es padre de F y G, así como B es padre de E y D.
Bajo esta misma relación pero a la inversa un nodo es hijo de otro cuando esta unido a él mediante una arista y se encuentra más alejado de la raíz.
Dos nodos son hermanos cuando tiene el mismo padre, en el ejemplo F y G son hermanos.
Los ancestros de un nodo son aquellos que lo unen a la raíz, en el ejemplo A y C son ancestros de F.Los nodos descendientes son todos aquellos que lo tienen como antecesor, en el ejemplo F y G son descendientes de C.
Los nodos sin hijos son llamados Hoja - en el ejemplo F, G, D, E - y los nodos con hijos son llamados nodos internos –en el ejemplo A, B, C-.
El nivel de un nodo es el numero de vértices necesarios para llegar a la raíz, la raíz siempre será de nivel 0; en el ejemplo A tiene nivel0, C y B tienen nivel 1, y F, G E,D tienen nivel 2.
La altura de un árbol es igual al nivel más alto que tenga un nodo, el ejemplo es un árbol de altura 2.

Arboles M-arios:
Un árbol es llamado M-ario cuando cada nodo interno tiene máximo M hijos, Ejemplo M=2
A
B
D
C
F
G

El árbol anterior es binario al tener máximo 2 hijos por cada nodo interno.
Cuando un árbol tiene exactamente Mhijos en cada nodo interno es llamado árbol M-ario Completo. Ejemplo árbol binario completo
A
B
D
C
E
F
G

Propiedades de los Arboles.
1. Los arboles tienen n-1 aristas, siendo n el numero de nodos, podemos ver en el ejemplo un árbol con 6 nodos y 6-1=5 (n-1) aristas.
A
B
D
C
F
G

2. Un árbol m-ario completo con i nodos internos contiene n = m ∗ i + 1 nodos. Podemos observaren el siguiente árbol binario completo con 3 nodos internos como tiene (2*3)+1=7 nodos
A
B
D
C
E
F
G

3. Un árbol m-ario completo con n nodos tiene:
* i = (n − 1)/m vértices internos
* l= ((m-1)n+1)/m hojas
En el ejemplo con un árbol binario con 7 nodos podemos observar como:
* i= (7-1)/2=3 nodos internos.
* l= ((2-1)7+1)/2=4 hojas.
A
B
D
C
E
F
G

4. Unárbol m-ario de altura h tiene máximo mh hojas.
En el ejemplo de un árbol binario de altura 2 podemos observar como 22=4 hojas.
A
B
D
C
E
F
G

Árboles generadores.
Un árbol generador es un sub-grafo de un grafo simple y contiene todos sus nodos.
Por ejemplo:
A
B
D
C
E
F

Un árbol generador debe ser un grafo que incluya todos los nodos del grafo anterior sin crear un ciclo, deesta manera el siguiente seria un árbol generador.

A
B
D
C
E
F

Árbol generador mínimo.
Cuando se tiene un grafo ponderado, un árbol generador mínimo es el que la suma de la ponderación sus aristas es la menor de cualquier otro árbol generador.
Algoritmo de Prim:
El algoritmo de Prim nos permite desde un nodo aleatorio encontrar el árbol generador mínimo. Para ejemplificarlo usaremosel siguiente ejemplo:
1
2
5
4
3
10
80
55
120
200
30
50
95
105
155

Nos situamos en cualquier nodo, en este caso nos situaremos en el nodo 1.
1
2
5
4
3
10
80
55
120
200
30
50
95
105
155

Evaluamos los posibles caminos:
1-2 | 10 |
1-3 | 30 |
1-4 | 50 |
1-5 | 80 |

Seleccionamos el de menor peso, en este caso 1-2, y nos situamos en el siguiente nodo.
1...