Arboles

ÁRBOLES

Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices. Se define como un tipo de grafo que no contieneciclos, es decir es un grafo también acíclico, pero a su vez es conexo.
Ejemplos:
B
B
A
A

C
C

D
D

F
F
E
E

G
G


J
J
H
H

LL

K
K
I
I

ÁRBOLES LIBRES
Son aquellos en donde no se define un vértice raíz.
H
H
D
D
C
C
B
B
A
A

F
F

I
I
E
E

G
GÁRBOLES CON RAÍZ
Son aquellos en donde está definido o identificado el vértice raíz.
E
E
F
F
G
G
I
I
H
H
C
C
D
D
B
B
A
AEJEMPLO PRÁCTICO 1
Dado el siguiente árbol.
F
F
E
E
A
A

J
J
K
K
I
I
H
H
G
G
C
C
B
B
D
D

Determinar el nively al altura del árbol.

G
G
Nivel 0
H
H
K
K
J
J
I
I
F
F
E
E
B
B
A
A

Nivel 1D
D

Nivel 2C
C

Nivel 3

Vértice | Nivel|
G | 0 |
E,D,H | 1 |
F,A,B,C,I,J | 2 |
K | 3 |

Altura = 3

EJERCICIO PROPUESTO
Dado el siguiente árbol. Determinar el Nivel y laAltura.
Considere como vértice raíz B.

G
G
D
D
A
A


H
H
I
I
E
E
B
B

J
J
F
F
C
CSUBÁRBOL

A
A
ENCONTRAR EL SUB-ÁRBOL
D
D
M
M


F
F

E
E
C
C
B
B

G
G
H
H

I
I

J
J

L
L

K
K

VT =
VI =
*Sub-árbol con raíz en E.
D
D

F
F

E
E

K
K
L
L
J
J
H
H
I
I
G
G

* Sub-árbol con raíz en H.
H
H

L
L
J
J
I
I
K
K