TEORÍA DE LOS GRAFOS

Un grafo G es un par ordenado G (V,E), donde:V es un conjunto no vacio, cuyos elementos son llamados

vértices.E es un conjunto de pares de elementos de V, que son llamados

arcosEj.:

G1 G2

1

2

3

a

b c

TEORÍA DE LOS GRAFOS

Un arco es (no) orientado o (no) dirigido si (no) hay una dirección asignada a él. Un grafo es (no) orientado si todos sus arcos son (no) orientados

<i,j> denota el arco dirigido de i a j(i,j) denota el arco no dirigido

Ej.:G1 = (V1,E1) V1 = {1,2,3}

E1 = {(1,2),(2,3),(1,3)}

G2 = (v2,E2) V2 = {a,b,c}E2 = {<a,b>,<a,c>}

GRAFOS NO ORIENTADOS: G = (V,E)

1. Los vértices i y j son adyacentes si (i,j) ϵ E, y se dice que (i,j) es incidente sobre i y j. Por lo tanto es adyacente si existe un arco que los conecte.

2. El grado o valencia del vértice i (di) es el número de arcos incidentes sobre i.

Ej.: En G3.- d1 = 3, d2 = 2, d3 = 2, d4 = 1

2

3

4

1

G3 1 y 2 son adyacentes

1 y 3 son adyacentes

(1,4) es incidente sobre 1 y 4

GRAFO COMPLETO

G es completo si tiene n(n-1) 2 arcos (Kn)

Donde Kn = el grafo completo de n vérticesEj.:

SUBGRAFO: Dado un grafo G, el grafo no orientado H = (V1,E1) es un subgrafo de G = (V,E) si V1 ᴄ V, E1 ᴄ E

Ej.: Un subgrafo de K4 es:

1 2

3 4

n = 4Kn = 6

K4

1 2

3

K3

K3 es subgrafo de K4

CAMINO

CAMINO: Un camino del vértice i1 al vértice ik es una secuencia de vértices P = i1 i2 i3 i4……ik, tal que (ij, ij+1) ϵ E, j = 1,2, ….. , k-1

Ej.: En K4, P = 1,2,4 es un camino de 1 a 4.CAMINO SIMPLE: El camino P es simple si ningún vértice se repite, exceptuando posiblemente el primero y el último vértices, y los arcos son diferentes.Ej.: en K4, P = 1,2,1 (no es camino simple) P = 1,2,3,1 (si es simple y es un camino cerrado) P = 1,2,3,4 (es simple)

CICLO

Un ciclo es un camino simple y cerrado (los vértices extremos son idénticos)

Ej. En k4: P = 2,3,1,2 es ciclo P = 2,3,1,4,2 es ciclo

GRAFO CONEXO

Un grafo G = (V,E) es conexo (conectado), si para cada par de vértices distintos i,j, existe un camino de i a j.Ej.:

A D

B

E

F

G

C

A

B

C

D

E

FG8

G9

NO ES CONEXO

NO ES CONEXO

El subgrafo G1 = (V1,E1) del grafo G = (V,E) es una componente conexa, si G1 es un subgrafo conexo maximal, esto es, no existe un subgrafo G2 = (V2,E2) conexo tal que V1 ᴄ V2 y E1 ᴄ E2.

COMPONENTE CONEXO

A

B

C

D

E

FG8

BICONEXIDAD1. v es un punto de articulación para un grafo G si existen vértices

distintos x y w <> v, tal que v está en todo camino de x a w.2. G es biconexo si no tiene puntos de articulación.

3. Una componente biconexa de un grafo G es un subgrafo de G que es biconexo maximal.

A B

C D

G10

3

1 24

6

5

G11

3

1 24

6

52

4

Componentes básicas de G11

ÁRBOLES

Un grafo es acíclico, si no tiene ciclos.

Un árboles un grafo acíclico y conexo

A

B

C

D

A B

C D

GRAFOS ORIENTADOS

• El arco orientado <i,j> es incidente a j, incidente desde i. El vértice i es adyacente a j, y j es adyacente desde i.

in• INVALENCIA: El grado de entrada del vértice i (di ) es el

número de arcos incidentes a i.

out

• EXVALENCIA: El grado de salida del vértice i (di ) es el número de arcos incidentes desde i.

1

3

2

<1,2> es incidente a 2 es incidente desde 1

• G es completo, si tiene n(n-1) arcos K0n

• Un Subgrafo es otro grafo con un subconjunto de vértices del conjunto de vértices.

• Un camino orientado es una secuencia de vértices• Un ciclo orientado es un camino orientado, donde el vértice

inicial es a su vez el vértice final. El ciclo orientado a su vez se conoce como Circuito.

2

1

3

C

E

D

A

B

CDE no es un caminoABCD es un camino simpleABCEA es un ciclo orientado

• Un grafo es fuertemente conexo si para cada par de vértices distintos i ≠ j existe un circuito que los contiene.Ej.:

G20 G21Si es fuertemente conexo No es fuertemente conexo

• Una componente fuertemente conexa es un subgrafo fuertemente conexo maximal. Ej.:

1

2 3

4

4

32

1

1

2 3

4

1

2 3

4

G22 H1 y H2 son comp. fuertemente conexas de G22

H1

H2

• Una secuencia de vértices P = i1, i2, ……, ik, es un semicamino o

cadena en G si <ij, ij+1> ϵ E ó <ij+1, ij> ϵ E, ó ambos están en E.

P = 1,2,3,4 es un semicamino

• Semicamino simple: es un camino en el cual, ningún vértice o arco se repite.

• Semiciclo: es un semicamino simple cerrado

1

4

3

2G23

• Un grafo orientado G = (V,E) es débilmente conexo si para cada par de vértices distintos i ≠ j existe un semicamino en G de i a j.Ej.:

2

4

1

3

H1

H2

G24

G23 sí es débilmente conexoG24 no es débilmente conexo

H1 y H2 son las componentesdébilmente conexas de G24

ÁRBOL ORIENTADO

• Un árbol orientado es un grafo orientado que es débilmente conexo y que no posee semiciclos.Ej.: G23

• ÁRBOL CON RAIZ: Un árbol con raiz o enraizado es un árbol orientado en la que un solo vértice tiene grado de entrada 0 y los otros tienen grado de entrada 1.Ej.:

4

3

1

2Raíz

REPRESENTACIÓN DE GRAFOS

1. MATRIZ DE ADYACENCIA

A = [aij] ; A : n * n

A) CASO NO ORIENTADO.-

1: si existe el arco (i,j) ϵ Eaij =

0: de otro modoEj.:

1 2

3 4

5

0 1 1 0 01 0 1 1 01 1 0 0 10 1 0 0 10 0 1 1 0

A =

En general, A es simétrica, la diagonal principal es nula

1. MATRIZ DE ADYACENCIA

B) CASO ORIENTADO.-

1: si <i,j> ϵ Eaij =

0: de otro modoEj.:

21

34

0 1 0 00 0 1 00 0 0 00 1 0 0

A =

En general, A no es simétrica

C) GRAFO (ORIENTADO O NO) CON PESOS.-

W(i,j) : si (i,j) ϵ Eaij = <i,j> ϵ E

C : de otro modo (C: Constante)Ej.:

1. MATRIZ DE ADYACENCIA

1

3

2

5

4

5

25

10

6

3216

14C 25 C C CC C 10 14 C5 C C C 16C 6 C C CC C C 32 C

A =

C: Valor muy grande si es utilidad (M). Si W es costo, M es pequeño

G26

2. LISTAS ENLAZADAS DE ADYACENCIANIL

Vértice

Ej.: Lista de adyacencia de G25:

2

1

1

2

3NIL

4NIL3

2

5NIL

5NIL

4NIL3

1

2

3

4

5

2. LISTAS ENLAZADAS DE ADYACENCIA

Ej.: Lista de adyacencia de G26:

2

4

5

2

10

NIL

NIL3

NIL

NIL

NIL4

1

2

3

4

5

25

14

16

6

32

1 5

ÁRBOLES PARCIALES MÍNIMOS• Un árbol parcial para un grafo G = (V,E) es un subgrafo que es

árbol y contiene a todos los vértices de G.Sea G = (V,E,W) un grafo con pesos, el peso de un subgrafo es la suma de los pesos de los arcos del subgrafo.Un árbol parcial mínimo es un árbol parcial de peso mínimo o de costo mínimo.Ej.:

1

32

1

32

2

2

1

32

2 2

11

1

Sus árbolesParcialesMínimos: El árbol parcial

Mínimo no esúnico

ALGORITMO DIJKSTRA / PRIM1. Vértice de árbol: es un vértice que ya está en el árbol que se ha construido

hasta ese momento.2. Vértice vecino: es un vértice que no es del árbol, pero que es adyacente a

uno.3. Vértice no visto: es un vértice que no es del árbol y tampoco es vecino.

Un arco candidato del vértice vecino “y”, es el arco (x,y) con x vértice del árbol que es de peso mínimo.El algoritmo sería:

Seleccionar un vértice vecinoMientras hay vértices vecinos hacer:

Seleccionar un arco de peso mínimo entre un vértice de árbol y un vértice vecino.Añadir tal arco y vértice vecino al árbol

Fin Mientras

ALGORITMO DIJKSTRA / PRIM

Ej.: A B

F

I

G

H

C

7

2

3

5

4

6

21

4

3

A

B

G

F

2

37

Árbol Vecinos

A

B

G

F

3

72

C4

A

B

G

F

3

72

C4

I

H

1

3

A

B

G

F

3 5

2 C4

I

H

13

A

B

G F

3

5

2

C2

I

H

1

3

WT = 16

ALGORITMO VORAZ

• Un algoritmo voraz es un algoritmo para problemas de

optimización en la que se hacen elecciones óptimas

localmente en cada paso.

• El resultado final no es necesariamente óptimo.

• El algoritmo de Dijkstra / Prim es voraz.

• La solución del algoritmo de Dijkstra / Prim sí es óptima.

ÁRBOLES PARCIALES DE COSTO MÍNIMO

1. ALGORITMO DE DIJKSTRA / PRIM

Seleccionar un vértice vecino

Mientras hay vértices vecinos hacer:

Seleccionar un arco de peso mínimo entre un vértice de árbol y

un vértice vecino.

Añadir tal arco y vértice vecino al árbol

Fin Mientras

ÁRBOLES PARCIALES DE COSTO MÍNIMO

2. ALGORITMO DE KRUSKALProcedimiento Kruskal (G,T,n){G = (V,E), N = |V|}ET = 0 ; E´ = E ; i = 0

Mientras E´≠ 0 AND i ≠ n-1 hacerSea (u,w) un arco de costo mínimo de E´E´ = E´- {(u,w)}Si (u,w) no crea un ciclo en T entonces ET = ET U {(u,w)}

i = i + 1Fin Si

Fin MientrasFin Procedimiento Kruskal

ALGORITMO KRUSKAL

Ej.:A B

F

I

G

H

C

7

2

3

5

4

6

21

4

3

ARCOIGHCABAGGHBCIHFIGBFA

COSTO1223344567

A B

F

I

G

H

C

7

2

3

5

4

6

21

4

3

XX

XX

WT = 16 (1+2+2+3+3+5)

El algoritmo Kruskal es vorazLa solución que proporciona sí es óptima

PROBLEMA DE CAMINOS MÁS CORTOS

Sea G = (V,E,W) grafo orientado o no con pesos.Sea P = u1, u2, …., uk un camino de u1 al uk. El peso o longitud de P se define: k-1

W(P) = Ʃ W (ui, ui+1) i=1

PROBLEMA:Sea G = (V,E,W) un grafo con pesos, y sean v, w ϵ V. Hallar un camino más corto de v a w.

SOLUCIÓN:Utilizando el siguiente algoritmo de Dijkstra: Sea z un vértice vecino, tal que z es adyacente a por lo menos un vértice del árbol Vk, entonces existe un camino más corto de v a vk.

Sea P = v, v1, v2, …, vk un camino=> P´= v, v1, v2, …, vk, Z es un camino de v a z

dist (v,z) = d (v,vk) + w(vkz) distancia distancia temporal permanente

El algoritmo:x = vMientras x ≠ w hacer Seleccionar un arco candidato xy tal que dist (v,y) = d (v,x) + w(xy) es mínimo entre todos los vértices vecinos añadir y, (x,y) al árbol d (v,y) = d(v,x) + w(xy) x = yFin Mientras

Ejemplo:

2A B

F

I

G

H

C

9 5

1

4

6

52

4

5

Hallar un camino más corto de A a F

A

B

F

G

2

95

Árbol Vecinos

dist (A,B) = 2

dist (A,F) = 9

dist (A,G) = 5

A

B

F

G

9

52

C4

6

dist (A,F) = 9

dist (A,G) = 5

dist (A,C) = 6

Vecinos

Iteración 1:

Iteración 2:

SOLUCIÓN:

A

G

B

I

2

25

H5

C

F

4

9

dist (A,C) = 6

dist (A,F) = 9

dist (A,I) = 7

dist (A,H) = 10

Iteración 3:

A

G

BI2

2

5 H5

C

F49 dist (A,F) = 9

dist (A,I) = 7

dist (A,H) = 10

A

G

B

F2

1

5H5

C

I

4

2

dist (A,F) = 8

dist (A,H) = 10

Iteración 4:

Iteración 5:

Hallar los caminos más cortos entre todos los pares de vértices i, j, tal que i ≠ j, utilizando el algoritmo de Warshall.

Ck(i,j) = longitud de un camino más corto de i a j que no pasa por vértices intermedios con índices mayor que k

∞ i = jC0(i,j) = ∞ (i,j) ϵ E (<i,j> ϵ E)

W(i,j) (i,j) ϵ E (<i,j> ϵ E)

Supongamos que ya se generó Ck-1, para generar Ck se consideran dos casos:1. El camino más corto de i a j que no pasa por ningún vértice intermedio mayor a k, tampoco pasa por k, entonces su costo es Ck-1(i,j)2. El camino más corto de i a j que no pasa por ningún vértice intermedio mayor a k, sí pasa por k, entonces su costo es Ck-1(i,k) + Ck-1(k,j)

Entonces:Ck(i,j) = min (Ck-1(i,j), Ck-1(i,k) + Ck-1(k,j) k >= 1

ALGORITMO DE WARSHALL:FOR K = 1, N FOR I = 1, N FOR J = 1, N

C (i,j) = min {C(i,j), C(i,k) + C(k,j)} END

ENDEND

V1

V3

V2

6

2

4

11

3

∞ 4 116 ∞ 23 ∞ ∞

∞ 4 116 10 23 7 14

10 4 6 6 10 2 3 7 9

9 4 65 9 23 7 9

C0 =

C2 =

C1 =

C3 =

RECORRIDO DE GRAFOSRecorrer significa visitar cada vértice del grafoEsto implica examinar, visitar o procesar todos los vértices y arcos del grafo

A. BÚSQUEDA PRIMERO A LO ANCHOSe realiza una búsqueda por niveles. Se visitan los vértices que están máscerca al vértice de partida, luego, los vértices que estén a continuacióndel vértice de partida, y así, sucesivamente.Los vértices son visitados en el orden de su distancia del vértice de partida.

Procedure BFS (v) [Breadth First Search){Q es una cola inicializada en 0}Visitar, marcar vInsertar v en QMientras Q ≠ 0 hacer

x = valor en el frente de la cola eliminar x de Q Para cada vértice w adyacente a x no marcado hacer

visitar y marcar winsertar w en Q

Fin ParaFin Mientras

A B

F

I

G

H

C

BFS (A)

Q : A F B I G C H

X = A F B I G C H

(H: Vértice más alejado del origen A)

B. BÚSQUEDA PRIMERO EN PROFUNDIDAD

PROCEDURE DFS (v) [Depth First Search] Visitar y marcar v Mientras hay un vértice w no marcado adyacente a v hacer

DFS (w) Fin Mientras

C GNILB

F BNILA

A B

F

I

G

H

C

DFS (A) v, mA DFS (B) v, mB DFS (C)

v, mC DFS (H) v, mH

DFS (I) v, mI DFS (G) v,mG FinFin

FinFin

Fin DFS (F) v, mF