Grafos - definición y recorridos

Algoritmos y Estructuras de Datos
Cursada 2011
Prof. Alejandra Schiavoni
Licenciatura en Sistemas Universidad Nacional de Río Negro

GRAFOS

Algoritmos y Estructuras de Datos

Agenda - Grafos
1. Ejemplos y terminología 2. Representaciones 3. Recorridos 4. Sort topológico

Algoritmos y Estructuras de Datos

3

Agenda - Grafos
1. Ejemplos y terminología 2. Representaciones 3.Recorridos 4. Sort topológico
Algoritmos y Estructuras de Datos 4

Terminología
Grafo→ modelo para representar relaciones entre elementos de un conjunto. Grafo: (V ,E), V es un conjunto de vértices o nodos, con una relación entre ellos; E es un conjunto de pares (u,v), u,v Є V , llamados aristas o arcos. Grafo dirigido: la relación sobre V no es simétrica. Arista ≡ par ordenado (u,v). Grafo nodirigido: la relación sobre V es simétrica. Arista ≡ par no ordenado {u,v}, u,v Є V y u ≠ v

Algoritmos y Estructuras de Datos

5

Terminología
Ejemplo 1

(cont. 1)

Grafo dirigido G(V , E).
V = {1,2,3,4,5,6} E={(1,2),(1,4),(2,5),(3,5),(3,6), (4,2), (5,4),(6,6)}

Grafo no dirigido G(V , E).
V = {1,2,3,4,5} E= {{1,2},{1,5},{2,3},{2,4}, {2,5},{3,4},{4,5}}

Algoritmos y Estructurasde Datos

6

Terminología

(cont. 2)

Camino desde u Є V a v Є V : secuencia v1, v2, ... , vk tal que u=v1, v=v k, y (vi−1,vi) Є E, para i = 2, ... ,k. Ej: camino desde 3 a 2 → .

Longitud de un camino: número de arcos del camino. Ejs: long. del camino desde 3 a 2 → es 3. (a) long. del camino desde 3 a 4 → es 4. (b)
Algoritmos y Estructuras de Datos 7

Terminología

(cont. 3)Camino simple: camino en el que todos sus vértices, excepto, tal vez, el primero y el último, son distintos. P1 es un camino simple desde U a Z. a U c W f Y Ejemplos anteriores: (a) es camino simple , (b) no lo es.
Algoritmos y Estructuras de Datos 8

V d

b e

P1 X g

h i Z j

Terminología

(cont. 4)

Ciclo: camino simple desde v1, v2, ... , vk tal que v1=vk Ej: es un ciclo delongitud 3.

Bucle: ciclo de longitud 1.

Grafo acíclico: grafo sin ciclos.

Algoritmos y Estructuras de Datos

9

Terminología

(cont. 5)

Un grafo es conexo si entre cada dos nodos hay un camino.

Un bosque es un grafo sin ciclos.

Un árbol libre es un bosque conexo.

Un árbol es un árbol libre en el que un nodo se ha designado como raíz.

Algoritmos y Estructuras de Datos10

Terminología

(cont. 6)

v es adyacente a u si existe una arista (u,v) Є E.
en un grafo no dirigido, (u,v) Є E incide en los nodos u, v. en un grafo dirigido, (u,v) Є E incide en v, y parte de u.

En grafos no dirigidos:
•El

grado de un nodo: número de arcos que inciden en él.

En grafos dirigidos:
•existen

el grado de salida (grado_out) y el grado de entrada (grado_in).el grado_out es el número de arcos que parten de él y el grado_in es el número de arcos que inciden en él. •El

grado del vértice será la suma de los grados de entrada y de salida.

Grado de un grafo: máximo grado de sus vértices.
Algoritmos y Estructuras de Datos 11

Terminología

(cont. 7)

Sea G un grafo no dirigido con n vértices y m arcos, entonces

Σv Є G
Siempre:deg(v) = 2*m m≤ (n*(n-1))/2 m≥n-1 m=n-1 m≤n-1

Si G conexo: Si G árbol: Si G bosque:

Algoritmos y Estructuras de Datos

12

Terminología

(cont. 8)

v es alcanzable desde u, si existe un camino de u a v. Un grafo no dirigido es conexo si existe un camino desde cualquier vértice a cualquier otro. Un grafo dirigido con esta propiedad se denomina fuertemente conexo:

Si un grafo dirigidono es fuertemente conexo, pero el grafo subyacente (sin sentido en los arcos) es conexo, el grafo es débilmente conexo.
Algoritmos y Estructuras de Datos 13

Terminología

(cont. 9)

En un grafo no dirigido, una componente conexa es un subgrafo conexo tal que no existe otra componente conexa que lo contenga. Es un subgrafo conexo maximal. Un grafo no dirigido es no conexo si está formado...