LOS SISTEMAS DE ARBOLES Y SU CLASIFICACION

a) Todo árbol que no es vacío, tiene un único nodo raíz.

b) Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. en este caso es común utilizar la expresión X es hijo de Y.

c) Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. en es caso es común utilizar la expresión X es padre de Y.

d) Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos.

e) Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja.

f) Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.

g) Grado es el número de descendientes directos de un determinado nodo. Grado del árbol es el máximo grado de todos los nodos del árbol, es decir, el grado más alto entre todos los nodos.

h) Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.

i) Altura del árbol es el máximo número de niveles de todos los nodos del árbol.

CONCEPTOS

1. A es la raíz del árbol.

2. B es hijo de A.

C es hijo de A.

E es hijo de B.

D es hijo de B.

L es hijo de H.

3. A es padre de B.

B es padre de D.

D es padre de I.

C es padre de G.

H es padre de L.

4. B y C son hermanos.

D, E y F son hermanos.

G y H son hermanos.

J y K son hermanos.

5. I, E, J, K, G y L son nodos terminales u hojas.

6. B, D, F, C y H son nodos interiores.

7. El grado del nodo A es 2.

El grado del nodo B es 3.

El grado del nodo C es 2.

El grado del nodo D es 1.

El grado del nodo E es 0.

El grado del árbol es 3.

8. El nivel del nodo A es 1.

El nivel del nodo B es 2.

El nivel del nodo D es 3.

El nivel del nodo C es 2.

El nivel del nodo L es 4.

9. La altura del árbol es 4.

CONCEPTO

- Los árboles forman una de las subclases de gráficas que más se utilizan. La ciencia de la computación hace uso de los árboles ampliamente, especialmente para organizar y relacionar datos en una base de datos. Los árboles surgen en problemas teóricos como el tiempo óptimo para ordenar.

PROPIEDADES

Un grafo no dirigido G se dice que es un árbol si es conexo y acíclico

Hay un único camino entre un par de vértices

ÁRBOLES DIRIGIDOS CON RAIZ (ARBORESCENCIAS)

CONCEPTO

Sea G un grafo dirigido G =(V,E)
Se dice que G es un árbol con raíz V_0 si es un grafo acíclico tal que todos los vértices a excepción de V_0tienen grado de tiene uno y V_0 grado de entrada cero.

PROPIEDADES

- Sea G= (V,E) un grafo dirigido con raíz V_0
- Sea G=(V,E) grafo subyacente de G
Se verifica que:

1.- existe un camino y solo uno desde V_0 a cada uno de los demás vértices.

2. - IEI=IVI-1

3. - G es aciclico

4. – G es conexo

5. – G es árbol

RELACIONES

- Cuando una relación es al mismo tiempo reflexiva, simétrica y transitiva se dice que es una relación de equivalencia.
- Cuando una relación es simultáneamente reflexiva, anti-simétrica y transitiva se le llama un orden parcial.

EJEMPLOS DE RELACIONES

 La relación de adyacencia entre los vértices de una gráfica 𝐺 definida por las aristas en 𝐴(𝐺) es una relación simétrica y no reflexiva.

 La relación “estar conectado con” sobre el conjunto de vértices de una gráfica 𝐺 es una relación de equivalencia.

 En un árbol 𝑇 con raíz 𝑟, la relación 𝑅 definida como (𝑢, 𝑣) ∈ 𝑅 si 𝑢 ∈ 𝑟𝑇𝑣 es un orden parcial.

VIDEO SUGERIDO:Árboles dirigidos con raíz | 13/42 | UPV

ÁRBOL GENERADOR DE MÍNIMO COSTE - ÁRBOL DE PESO MÍNIMO

ALGORITMO DE KRUSKAL

- Sea G no dirigido ponderado

- El algoritmo de kruskal proporciona un árbol generador de mínimo coste

- Si los pesos son distintos 2 a 2 el árbol generador de mínimo coste es único.

CARACTERISTICAS

- Sea G un grafo no dirigido conexo ponderado G=(V,E).

- Se llama árbol generador de G a todo subgrafo generador que sea conexo y aciclico.

- Se llama árbol generador de mínimo coste de G a todo árbol generador de G cuyo coste sea menor o igual que el de cualquier otro árbol generador de G.

- El árbol generador de mínimo coste de un grafo dado G no tiene por que ser único.

CUESTION

- Si los pesos son distintos el árbol generador es único.

- El que los pesos se repitan no obliga a que existan arboles generadores del mínimo coste distintos(puede ser único o puede no ser único).

VÍDEO SUGERIDO:Árboles | 12/42 | UPV

Tiene ciclos

Tiene 2 o mas componentes conexos