Digrafo

Dado el siguiente dígrafo determinar:

a) Lista de trayectorias de longitud (R2)

 b) Tabla de grados de todos los vértices

[pic 1]

a) Lista de trayectorias de longitud (R2)

R2 = {(A, E), (B, C), (E, C), (C, B), (D, C), (C, E), (D, B), (A, D), (E, C), (D, A), (b, d)}

b) Tabla de grados de todos los vértices

4.10 ARBOLES

CONCEPTOS BASICOS

Un árbol impone una estructura jerárquica sobre una colección de objetos. Los árboles genealógicos y organigramas son ejemplos de árboles.

Un árbol es una colección de elementos llamados nodos, uno de los cuales se distingue como raíz,
junto con una relación (de paternidad) que impone una estructura jerárquica sobre los nodos. Un árbol tiene uno y sólo un nodo raíz, y uno o más nodos hojas. En un árbol la raíz es el nodo inicial o base de una estructura de árbol.

 Un nodo es similar a un elemento de una lista, puede ser del tipo que se desee. Se representa por medio de una letra, una cadena de caracteres o un círculo con un número en su interior. Un nodo sin descendientes propios se denomina hoja. Un subárbol de un árbol es un nodo junto con todos sus descendientes. La longitud de camino es el número de nodos del camino menos uno.

Si existe un camino de un nodo a a otro nodo b entonces a es un antecesor de b, y b es un descendiente de a. Cada nodo es a la vez un antecesor y un descendiente de sí mismo. Un antecesor o descendiente de un nodo que no sea él mismo recibe el nombre de antecesor propio o descendiente propio respectivamente.

 La altura de un nodo en un árbol es la longitud del camino más largo de ese nodo a cada hoja. La altura del árbol es la altura de la raíz.

 La profundidad de un nodo es la longitud de camino único desde la raíz a ese nodo.

El nodo padre es aquel nodo que puede o no tener ramificaciones.

 Un nodo hijo es aquel que tiene un nodo padre o nodo antecesor.

Un nodo hermano son todos aquellos nodos que provienen del mismo nodo padre.

 Un nodo hoja es aquel nodo que no tiene ramificaciones.

Un nodo no terminal es aquel que posee por lo menos una ramificación.

 El camino es el conjunto de nodos que tenemos que visitar con el propósito de llegar a un nodo específico.

Nivel de un árbol: cada nodo tiene un nivel dentro del árbol binario. El nodo raíz es el nivel cero y cada uno de los otros nodos tiene el nivel de sus padres más uno.

El grado de un nodo está dado por el número de hijos que tenga dicho nodo. El grado de un nodo hoja es cero.

El peso de un árbol en un nodo determinado es el número de nodos que contiene él mismo, sin contarse el nodo de partida.

Ejemplo:

Dado el siguiente esquema de árbol determinar:

[pic 2]

A. La raíz del árbol es: libro

B. Listar la raíz de los subárboles principales: C1, C2, C3

C. El nodo padre principal es:

D. Listar los nodos hijos de Libro: C1, C2, C3

E. Defina la raíz del tercer subárbol de libro:

F. Longitud de camino desde el nodo C2 al nodo S2.1.2: 2 Desplazamientos

G. Listar los antecesores del nodo S2.1: S2.1., C2, Libro

H. Listar los antecesores propios de Libro: C1, C2, C3

I. Listar las hojas del árbol:

J. Altura del nodo C1:1

K. Altura del nodo C2:2

L. Altura del nodo C3:1

M. Altura del árbol:3

N. Profundidad del nodo C3:1

O. Listar los descendientes propios de S2.1: S2.1.1., S2.1.2.

P. Nivel del árbol:3

Q. Grado del nodo C1:2

R. Peso del Nodo C2:3

S. Nivel del nodo S2.3:2

T. Tipo de árbol:

Dado el siguiente esquema de árbol determinar:

[pic 3]

A. La raíz del árbol es: E

B. Listar los nodos hijos de E: S1, S2, S3

C. Listar las hojas del árbol: T1, T2 T3, T4

D. Listar los ancestros del nodo D2: D2, S2, E

 E. Listar los ancestros propios del nodo D2:S2, E

 F. Listar los descendientes de D2: D2, T1, T2, T3

G. Listar los descendientes propios de D2: T1, T2, T3

H. Altura del nodo S2: 2

 I. Altura del árbol: 3

J. Profundidad del nodo S2: 1

K. Camino del nodo E al T3: E, S2, D2, T3

L. Nivel del nodo T4: 3er Nivel

M. Longitud de camino del nodo E al nodo T3: 3 Desplazamientos

...