Grafos y arboles

Estructuras de Datos y Algoritmos
Facultad de Inform´tica a Universidad Polit´cnica de Valencia e

Curso 2005/2006 Tema 4: Grafos y ´rboles a

FI– UPV: Curso 2005/2006

EDA-4

TEMA 4. Grafos y ´rboles a
Objetivos • Definiciones, representaci´n y recorrido de ´rboles y grafos. o a Contenidos 1 2 3 4 5 6 7 8 Grafos: Definiciones b´sicas a Representaci´n de grafos o ´ Arboles: Definicionesb´sicas a ´ Arboles binarios Representaci´n de ´rboles o a Recorridos de ´rboles binarios a Recorrido de grafos Orden topol´gico en grafos ac´ o ıclicos

Bibliograf´ ıa • Introduction to Algorithms, de Cormen, Leiserson y Rivest (sec. 5.4, 5.5, 11.4 y 23.1) • Estructuras de datos y algoritmos, de Aho, Hopcroft y Ullman (cap´ ıtulos 3, 6 y 7)
FI– UPV: Curso 2005/2006 P´gina 4.1 a

EDA-4

´ 1.GRAFOS: DEFINICIONES BASICAS
Grafo dirigido: es un par G = (V, A) donde V es un conjunto finito de elementos llamados v´rtices y A ⊆ V × V es un conjunto de “pares ordenados” de v´rtices llamados e e aristas. Si (u, v) es una arista de G, se dice que el v´rtice v es adyacente a u. e

0

1

2

3

4

5

FI– UPV: Curso 2005/2006

P´gina 4.2 a

EDA-4

´ 1. GRAFOS: DEFINICIONESBASICAS
Grafo no dirigido: es un par G = (V, A) 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. e Si a = {u, v} es una arista no dirigida, se dice que a une a u y v y que a incide en u y v. Si {u, v} es una arista de G, se dice que el v´rtice v es adyacente a u. La relaci´n es e o sim´trica. e

0

1 2

4

3FI– UPV: Curso 2005/2006

P´gina 4.3 a

EDA-4

´ 1. GRAFOS: DEFINICIONES BASICAS
Grado: para todo v´rtice v, e • grado de entrada es el n´mero de aristas que inciden en v; u • grado de salida es el n´mero de aristas que emergen de v; u • grado es la suma de los grados de entrada y salida de v. El grado de un grafo es el m´ximo grado de sus v´rtices. a e

0

1

2

3

4

5Ejem.: El grado de entrada del v´rtice 1 es 2; el grado de salida es 1; el grado del v´rtice es 3. El grado del e e grafo es 3.

FI– UPV: Curso 2005/2006

P´gina 4.4 a

EDA-4

´ 1. GRAFOS: DEFINICIONES BASICAS
Camino desde un v´rtice u ∈ V a un v´rtice v ∈ V : es una secuencia v0, v1, . . . , vk de e e v´rtices de G = (V, A) tal que v0 = u, vk = v, (vi, vi+1) ∈ A, 0 ≤ i < k. e La longitudde un camino v0, v1, . . . , vk es el n´mero de aristas que lo forman. u Camino simple: es un camino v0, v1, . . . , vk en el que todos sus v´rtices son distintos, e excepto quiz´s el primero y el ultimo. a ´ Ciclo: es un camino simple v0, v1, . . . , vk tal que v0 = vk y el camino contiene al menos una arista. Un bucle es un ciclo de longitud 1.

0

1

2

3

4

5

Ejem.: El camino 0,3, 1, 4 es simple y tiene longitud 3. El camino 0, 1, 4, 3, 1 no es simple. Ejem.: El camino 1, 4, 3, 1 es un ciclo de longitud 3. El ciclo 5, 5 es un bucle.

Grafo ac´ ıclico: es un grafo sin ciclos.
FI– UPV: Curso 2005/2006 P´gina 4.5 a

EDA-4

´ 1. GRAFOS: DEFINICIONES BASICAS
Subgrafo: G = (V , A ) es un subgrafo de G = (V, A) si V ⊆ V ∧ A ⊆ A. Subgrafo inducido: Dado V ⊆ V , elsubgrafo de G inducido por V es G = (V , A ) tal que A = {(u, v) ∈ A | u, v ∈ V }.
0 1 2

3

4

5

0

1

0

1

3

4

3

4

Subgrafo

Subgrafo inducido por V = {0, 1, 3, 4}

FI– UPV: Curso 2005/2006

P´gina 4.6 a

EDA-4

´ 1. GRAFOS: DEFINICIONES BASICAS
V´rtice alcanzable desde un v´rtice u: es cualquier v´rtice v para el que existe un e e e camino de u a v. Lascomponentes conexas en un grafo no dirigido son las clases de equivalencia de v´rtices seg´n la relaci´n “ser alcanzable”. e u o • Un grafo no dirigido es conexo si ∀u, v ∈ V , v es alcanzable desde u. Es decir, si tiene una unica componente conexa. ´ Las componentes fuertemente conexas en un grafo dirigido son las clases de equivalencia de v´rtices seg´n la relaci´n “ser mutuamente alcanzable”....