Arboles y grafos

definición de árbol y grafos

1. ELO-320 1
Definiciones: conjuntos, grafos, y
árboles
Agustín J. González
ELO 320: Estructura de Datos y
Algoritmos. 2004

2. ELO-320 2
Conjuntos (sets) y Grafos (graphs)
Un Conjunto es una colección de objetos distintos.
No hay diferencia con lo ya aprendido en teoría de conjuntos en
matemáticas.
Grafos: los hay de dos “sabores” grafos dirigidos y grafos no dirigidos.
Un Grafo Dirigido (o digrafo) G es un par (V,E), donde V es un conjunto
finito y E es una relación binaria sobre V. Es decir, E es una subconjunto
del producto cartesiano VxV.
V es llamado el conjunto de vértices de G, y cada elemento es llamado
vértice o nodo.
E es llamado el conjunto de arcos de G, y cada elemento es llamado arco.
En un grafo dirigido es posible tener arcos apuntando al mismo nodo de
salida (u,v), con u=v.
Un Grafo No Dirigido G =(V,E) de arcos E consiste de pares no
ordenados. Es decir, un arco es un conjunto {u, v}. Se acostumbra anotar
(u,v) en lugar de {u,v}; (u,v) y (v,u) son considerados el mismo arco.
No hay arcos al mismo nodo en un grafo no dirigido. u¹ v.

3. ELO-320 3
Ejemplos de Grafos
Grafo dirigido G=(V,E),
V={1,2,3,4,5,6} E={(1,2),
(2,2),(2,4),(2,5),
(4,1),(4,5),(5,4),(6,3)}
1
2
4
5
6
3
1
2
4
5
6
3
•Grafo no dirigido G=(V,E),
V={1,2,3,4,5,6} E={(1,2),
(1,5),(2,5),(3,6)}

4. ELO-320 4
Otras Definiciones En Grafos
Camino de largo k desde un vértice u a otro u’ es la
secuencia <vo,v1,..,vk> de vértices tal que u=vo,
u’=vk, y (vi-1,vi) pertenece a e para i=1,2,..k.
Camino simple si todos los vértices son distintos en
el camino.
Ciclo en grafo dirigido: es un camino <vo,v1, ,vk>
donde vo=vk y el camino contiene al menos un arco.
Ciclo en grafo no dirigido: es un camino de largo tres
o más que conecta un vértice con el mismo.
Un ciclo es simple si v1, v2, .., vk son distintos.
Grafo acíclico es aquél que no tiene ciclos.

5. ELO-320 5
Caminos y ciclos
Camino simple: {4,1,2,5}
Camino: {4,1,2,2,5}
Ciclo simple: {5,4,1,2,5}
Ciclo: {2,5,1,2}
Además este ciclo es
simple.
Ciclo: {5,1,2,5,1,2,1,2,5}
1
2
4
5
6
3
1
2
4
5
6
3

6. ELO-320 6
Definiciones en grafos (Cont)
Un Grafo no dirigido es conexo si cada par de vértices están
conectados por un camino.
Las componentes conexas de un grafo son las clases de
equivalencia bajo la relación “es alcanzable”. En otras palabras,
son los conjuntos de vértices alcanzables entre sí.
Un grafo dirigido es fuertemente conexo si cada par de nodos es
alcanzable de uno al otro.
Las componentes fuertemente conexas de un grafo dirigido son
los conjuntos de vértices mutuamente alcanzables.
Foresta: grafo no dirigido y acíclico
Árbol libre: grafo no dirigido, acíclico, y conexo.
“Dag”: grafo acíclico dirigido (Directed acyclic graph)

7. ELO-320 7
Conexos Y Componentes Conexas
Es dirigido y no
fuertemente conexo.
Las componentes conexas
son: {{1,2,5,4}, {3},{6}}
Es no dirigido y no
conexo.
Las componentes
conexas son: {{4}, {1,2,5},
{3,6}}
1
2
4
5
6
3
1
2
4
5
6
3

8. ELO-320 8
Divertimento
¿Cómo alinear 10 soldados en 5 filas, líneas
o columnas de 4 hombres cada una?

9. ELO-320 9
Árboles
Árbol libre: es un grafo no dirigido acíclico conexo.
Foresta: es menos restrictivo, es un grafo no dirigido
acíclico. Es decir, da la posibilidad que sea no-conexo.
Árbol con raíz: es un árbol libre en el cual un vértice se
distingue del resto. Este vértice es la raíz.
Nodo: es el término usado para referirse a un vértice de un
árbol con raíz.
Árbol libre Foresta
Ni árbol ni foresta, sólo un grafo

10. ELO-320 10
Árboles: más conceptos
Ancestro: cualquier nodo en el camino a la raíz de un nodo y
es un ancestro de y.
Descendiente : si x es un ancestro de y, y es un descendiente
de x.
Si y es un descendiente de x con x¹y, y es un descendiente
propio de x
Análogamente podemos definir un ancestro propio.
Si (x,y) es el último arco en el camino desde la raíz hacia y,
entonces x es el padre de y e y es el hijo de x. La raíz es el
único nodo sin padre.
Si dos nodos tienen el mismo padre son hermanos
Un nodo sin hijos es un nodo externo u hoja.
Los nodos no hojas son nodos internos.

11. ELO-320 11
Altura de un árbol
El largo de un camino es igual al número de arcos del camino.
El largo del camino desde la raíz a un nodo x es la profundidad
de x.
La profundidad más grande de cualquier nodo del árbol T es la
altura de T.
=> La altura de un árbol es el largo del mayor camino de la raíz
a una hoja.
Profundidad 0
Profundidad 3
Profundidad 4
Profundidad 5
Profundidad 2
Profundidad 1
Altura 5

12. ELO-320 12
Árboles binarios
Árbol binario: Un árbol binario T es una estructura
definida sobre un conjunto finito de nodos que
cumple:
no contiene nodos (árbol vacío o nulo).
Está compuesta de tres conjuntos disjuntos: un nodo raíz,
un árbol binario llamado sub-árbol izquierdo, y un árbol
binario llamado sub-árbol derecho.
Hijo izquierdo / hijo derecho: la raíz del sub-árbol
izquierdo / derecho
¿Cuántos nodos posee como máximo un árbol
binario de altura h?