grafos

Algoritmos y Estructuras de Datos III
Facultad de Inform´tica, Grupo 2B
a
Universidad Polit´cnica de Valencia
e

Tema 2:
´
Grafos y Arboles
Enrique Vidal Ruiz
evidal@iti.upv.es
Octubre, 2000

E. Vidal – UPV

´
AD3-Grafos-Arboles-2

Octubre, 2000

´
Grafos y Arboles: ´
Indice
1. Definiciones
´
2. Arboles
3. Represemtaci´n de grafos y ´rboles
o
a
4. Recorridos b´sicosde ´rboles
a
a

Bibliograf´
ıa:
• Cormen Leiserson y Rivest: “Introduction to Algorithms”, MIT press, 1990.
• Aho, Hopcroft y Ullman: “The Design and Analysis of Computer Algorithms”,
Addison–Wesley, 1974.

E. Vidal – UPV

P´gina 2.1
a

´
AD3-Grafos-Arboles-2

Octubre, 2000

Grafos: Definiciones
• Grafo Dirigido:
Es un par G = (V, A) donde V es un conjunto finito de elementosllamados
v´rtices y A ⊆ V × V es un conjunto finito de pares ordenados de v´rtices
e
e
llamados aristas. Si a = (u, v) es una arista de G, se dice que a entra o
incide en v y que a sale o emerge de u.
• Grafo no Dirigido:
Es un par G = (A, V ) donde V es un conjunto finito de v´rtices y
e
A ⊆ {{u, v} | u, v ∈ V ∧ v = u} es un conjunto de “pares no ordenados” de
v´rtices.
eEquivalentemente, G es un Grafo no Dirigido si G es un Grafo Dirigido y
∀u, v ∈ V, (u, v) ∈ A ⇔ (v, u) ∈ A. Si a = ({u, v} es un arco no dirigido,
se dice que a une a u y v y que a incide en u y en v. En lo que sigue nos
referiremos siempre a Grafos Dirigidos, a menos que se indique lo contrario.

E. Vidal – UPV

P´gina 2.2
a

´
AD3-Grafos-Arboles-2

Octubre, 2000

Grafos: Definiciones (cont.)
•Grado: Para todo v´rtice v, Grado de Entrada es el n´mero de aristas que inciden
e
u
en v; Grado de Salida es el n´mero de aristas que emergen de v; Grado es la
u
suma de los grados de entrada y salida de v. Grado de un Grafo es el m´ximo
a
grado de sus v´rtices.
e
• Camino desde un v´rtice u ∈ V a un v´rtice v ∈ V : es una secuencia
e
e
< v0, v1, . . . , vk > de v´rtices de G = (V, A)tal que v0 ≡ u, vk ≡ v, (vi, vi+1) ∈ A,
e
0 ≤ i < k. La Longitud de un Camino < v0, v1, . . . , vk > es el n´mero (k) de
u
aristas que lo forman.
• Camino Simple: es un camino en el que todos sus v´rtices son distintos.
e
• Ciclo: es un camino simple < v0, v1, . . . , vk > tal que v0 = vk .
• Grafo Ac´
ıclico: es un grafo sin ciclos.
• Subgrafo: G = (V , A ) es un Subgrafo de G = (V, A)si V ⊆ V ∧ A ⊆ A.
• Subgrafo Inducido:
por V ⊆ V es un subgrafo G = (V , A ) tal que A = {(u, v) ∈ A | u, v ∈ V }.
E. Vidal – UPV

P´gina 2.3
a

´
AD3-Grafos-Arboles-2

Octubre, 2000

Grafos: Definiciones (cont.)
• V´rtice Alcanzable desde un v´rtice u: es cualquier v´rtice v para el que existe
e
e
e
un camino de u a v.
• Grafo (Fu´rtemente) Conexo: Es un grafo (Dirigido) G =(V, A) en el que
e
∀u, v ∈ V , v es alcanzable desde u.
• Componentes (Fu´rtemente) Conexas de un Grafo (Dirigido): Son las clases
e
de equivalencia de v´rtices seg´n la relaci´n “ser m´tuamnete alcanzable”.
e
u
o
u
• Grafo Completo: es un grafo G = (V, A) en el que ∀u, v ∈ V, u = v, (u, v) ∈ A
• Grafos Isomorfos: Dos grafos G = (V, A), G = (V , A ) son isomorfos si existe una
biyecci´nf : V → V tal que (u, v) ∈ A ⇔ (f (u), f (v)) ∈ A
o
• Grafo Etiquetado: Es un grafo G = (V, A) acompa˜ado de una funci´n f : A → E,
n
o
donde E es un conjunto cuyas componentes se denominan etiquetas.
• Grafo Ponderado: Es un grafo etiquetado con n´meros reales (E ≡ )
u
E. Vidal – UPV

P´gina 2.4
a

´
AD3-Grafos-Arboles-2

Octubre, 2000

´
Arboles
• Bosque: Es un grafo nodirigido ac´
ıclico.
• Arbol Libre: Es un grafo no dirigido ac´
ıclico conexo.
Teorema 1.
Si G es un grafo con M > 2 v´rtices, entonces los
e
siguientes predicados son equivalentes:
1. G es un ´rbol libre
a
2. G es conexo y tiene M − 1 aristas
3. Cualquier par de v´rtices est´n conectados por un unico camino
e
a
´
4. Si se a˜ade una arista a G se crea un ciclo
n
• Arbol de...