estructuras de datos y algoritmos -...

Estructuras de Datos y AlgoritmosFacultad de Informatica

Universidad Politecnica de Valencia

Curso 2009/2010

Tema 6:Algoritmos de grafos

FI– UPV: Curso 2009/2010

EDA-6

TEMA 6. Algoritmos de grafos

Conceptos previos

• Representacion de grafos: matriz de adyacencia y listas de adyacencia (tema 4).• Recorridos de grafos en amplitud y en profundidad (tema 4).• Algoritmos voraces (tema 5).

Objetivos

• Algoritmos para la construccion del arbol de expansion de coste mınimo.• Algoritmos para la busqueda del camino mınimo en un grafo.• Algoritmos para calcular el flujo maximo en un grafo.

Contenidos

• Arbol de expansion de coste mınimo: Algoritmos de Kruskal y Prim.• Caminos mas cortos: Algoritmo de Dijkstra.• Flujo maximo: Algoritmo de Ford-Fulkerson/Edmonds-Karp.

Bibliografıa

• Introduction to Algorithms, de Cormen, Leiserson y Rivest (capıtulos 24, 25 y 26)

FI– UPV: Curso 2009/2010 Pagina 6.1

EDA-6

1. ARBOL DE RECUBRIMIENTO DE COSTE MINIMO

Arbol de recubrimiento de un grafo no dirigido G = (V,A): es unarbol libre T = (V ′, A′) tal que V ′ = V y A′ ⊆ A.Problema: Dado un grafo conexo ponderado no dirigido G = (V,A, p),encontrar un arbol de recubrimiento de G, T = (V,A′), tal que la sumade los pesos de las |V | − 1 aristas de T sea mınimo.

924

3

4

66 1

8

5

c

a

d

eb9

24

3

4

66 1

8

5

c

a

d

eb


EDA-6

1. ALGORITMO DE KRUSKALIdea voraz: construir incrementalmente un bosque (de recubrimiento), seleccio-nando en cada paso una arista (u, v) ∈ A tal que:

No se cree ningun ciclo.

Produzca el menor incremento de peso posible.

El resultado del algoritmo es un arbol libre (no enraizado) formado por los mismosvertices del grafo y un subconjunto de |V | − 1 aristas.

1 GrafoPonderado* Kruskal (GrafoPonderado *G) { // Pseudo-codigo2 // El arbol de recubrimiento tiene los mismos vertices que G:3 GrafoPonderado *MST = new GrafoPonderado(G->vertices);4 // Cola de prioridad, las aristas se extraen por menor peso:5 ColaPrioridad Q(G->aristas);6 arista a;7 while (MST->NumAristas() < MST->NumVertices()-1 &&8 Q.extraer(a)) {9 if (a no crea un ciclo en MST)

10 MST->insertarArista(a);11 }12 return MST;13 }


EDA-6

1. ALGORITMO DE KRUSKAL

Problema: ¿Como verificar eficientemente la condicion de “no crear ciclo”?

Solucion: Mantener una coleccion de subconjuntos (disjuntos) con los verticesde cada arbol del bosque: Una arista (u, v) no creara ciclo si u y v estan endistintos subconjuntos → componentes conexas → estructurar el conjuntode aristas seleccionadas como un MFset de vertices.

Problema: ¿Como seleccionar eficientemente la arista de menor peso en cadaiteracion?

Solucion: Manteniendo las aristas en una cola de prioridad (por ejemplo, unMinHeap) organizadas segun su peso.


EDA-6


1 GrafoPonderado* Kruskal (GrafoPonderado *G) { // Pseudo-codigo2 GrafoPonderado *MST = new GrafoPonderado(G->vertices);3 ColaPrioridad Q(G->aristas);4 mfset m(G->NumVertices());5 while (MST->NumAristas() < MST->NumVertices()-1 &&6 Q.extraer((u,v))) {7 if (m.find(u) != m.find(v)) {8 m.merge(u,v);9 MST->insertarArista((u,v));

10 }11 }12 return MST;13 }


EDA-6


El coste es O(|A| log |A|)

construir MFsets de talla |V | O(|V |)

construir MinHeap +O(|A|)

O(|A|) borrados en MinHeap+O(|A| log |A|)

O(|A|) operaciones MFset +O(|A|)

En general, el coste es bastante inferior a la cota O(|A| log |A|):

Si m es el numero de iteraciones del bucle while, tıpicamente m ≈ |V | y si|V | � |A| ≤ |V |2, en la practica, el coste esta mas cercano a

|A|+ |V | log |V |


EDA-6

1. ALGORITMO DE KRUSKAL: UN EJEMPLO

Inicializacion

a

b e

c d

8 9

4 2

56

6

4

1

3

a b c d e

(c,e) 1

(e,d) 3

(c,d) 4(a,d) 2

(c,a) 4 (b,d) 6 (b,e) 5

(a,e) 9 (b,c) 6 (b,a) 8


EDA-6


NumAristas = 1

a

b e

c d

8 9

4 2

56

6

4

1

3

a b c d

e(c,e) 1

(e,d) 3 (c,d) 4

(a,d) 2

(c,a) 4 (b,d) 6 (b,e) 5

(a,e) 9

(b,c) 6

(b,a) 8

e

c

1


EDA-6


NumAristas = 2

a

b e

c d

8 9

4 2

56

6

4

1

3

a b c

d e

(e,d) 3

(c,d) 4

(a,d) 2

(c,a) 4

(b,d) 6 (b,e) 5

(a,e) 9

(b,c) 6 (b,a) 8

e

c

1

a

d

2


EDA-6


NumAristas = 3

a

b e

c d

8 9

4 2

56

6

4

1

3

a b

cd

e

(e,d) 3

(c,d) 4

(c,a) 4

(b,d) 6 (b,e) 5(a,e) 9

(b,c) 6

(b,a) 8

e

c

1

a

d

2

3


EDA-6


NumAristas = 3

a

b e

c d

8 9

4 2

56

6

4

1

3

a b

cd

e

(c,d) 4

(c,a) 4

(b,d) 6

(b,e) 5

(a,e) 9

(b,c) 6

(b,a) 8

e

c

1

a

d

2

3


EDA-6


NumAristas = 3

a

b e

c d

8 9

4 2

56

6

4

1

3

a b

cd

e

(c,d) 4

(b,d) 6

(b,e) 5

(a,e) 9

(b,c) 6

(b,a) 8

e

c

1

a

d

2

3


EDA-6


NumAristas = 4

a

b e

c d

8 9

4 2

56

6

4

1

3

a

bcd e

(b,d) 6

(b,e) 5

(a,e) 9

(b,c) 6

(b,a) 8

e

c

1

a

d

2

3

b4


EDA-6

2. ALGORITMO DE PRIM

Idea voraz: Empezando por cualquier vertice, construir incrementalmente un arbol derecubrimiento, seleccionando en cada paso una arista (u, v) del grafo tal que:

Si se anade (u, v) al conjunto de aristas del arbol de recubrimiento obtenido hasta elmomento no se cree ningun ciclo.

Produzca el menor incremento de peso posible.

1 GrafoPonderado* Prim (GrafoPonderado *G) {2 GrafoPonderado *MST = new Arbol(G->vertices);3 ConjuntoVertices S;4 S.insertar(vertice arbitrario de G);5 int NumVertices = 1;6 while ( NumVertices != G->vertices ) {7 arista a= argmin { peso(u,v) | u en S, v en V-S };8 S.insertar(v); NumVertices++;9 MST->insertarArista(a);

10 }11 return MST;12 }


EDA-6


Problema: El coste cubico del algoritmo basico de Prim esta dominado por el costecuadratico de la operacion de seleccion (argmin), que debe considerar todos los pares devertices de S (ya seleccionados) y vertices del grafo no incluidos en S.

Solucion: Esta operacion puede implementarse con un coste lineal mediante la idea dePrim:

Mantener para cada vertice no seleccionado v ∈ V −S el identificadorde un vertice ya seleccionado u ∈ S mas “proximo” a el; es decir,

∀v ∈ V − S, P [v] = u = argminx∈S

p(x, v)

Estos identificadores se pueden mantener en un vector P . Como en cada iteracion solo seanade un nuevo vertice a S, P puede actualizarse en |V − S| = O(|V |) pasos.


EDA-6


1 GrafoPonderado* Prim (GrafoPonderado *G) {2 GrafoPonderado *MST = new Arbol(G->vertices);3 VectVertBool S; VectVertVert P; VectVertFloat D;4 u = vertice arbitrario de G;5 for (k = 0; k < G->vertices; k++) {6 S[k] = false; P[k] = u; D[k] = peso(k,u);7 }8 S[u] = true; int NumVertices = 1;9 while ( NumVertices != G->vertices ) {

10 for (k=0, minp = infinito; k < G->vertices; k++)11 if (!S[k] && minp > D[k]) { minp=D[k]; v=k; }12 S[v] = true; NumVertices++;13 MST->insertarArista((v,P[v]));14 for (k=0; k < G->vertices; k++)15 if (!S[k] && D[k] > peso(k,v)) {16 P[k]=v;17 D[k]=peso(k,v);18 }19 }20 return MST;21 }


EDA-6

2. ALGORITMO DE PRIM: UN EJEMPLO

a

b e

c d

8 9

4 2

56

6

4

1

3

a

b e

c d

9

4

1

3

a b c d eP e e e e 0


EDA-6


a

b e

c d

8 9

4 2

56

6

4

1

3

a

b e

c d

45

1

3

a b c d eP c e 0 e 0


EDA-6


a

b e

c d

8 9

4 2

56

6

4

1

3

a

b e

c d

2

51

3

a b c d eP d e 0 0 0


EDA-6


a

b e

c d

8 9

4 2

56

6

4

1

3

a

b e

c d

2

51

3

a b c d eP 0 e 0 0 0


EDA-6


a

b e

c d

8 9

4 2

56

6

4

1

3

a

b e

c d

2

51

3

a b c d eP 0 0 0 0 0


EDA-6


Coste O(|V |2).

Si se utiliza un MinHeap para guardar la informacion de los vectores P y D, podemosobtener el mınimo de D y eliminarlo del conjunto en O(log |V |)

• Es necesario utilizar un MinHeap doblemente indexado para poder modificar losvalores asociados a determinados vertices.• El numero de modificaciones en cada paso sera el grado del vertice que anadimos

al arbol. El coste de cada modificacion es O(log |V |) y el numero total demodificaciones a lo largo del algoritmo es O(|A|).• Esta version tiene, pues, un coste O(|A| log |V |), que es ventajoso para grafos

dispersos pero no para grafos densos.


EDA-6

2. COMPARACION ENTRE PRIM Y KRUSKAL

Algoritmo de Prim:

• Version sencilla de coste O(|V |2): Grafos densos• Listas de adyacencias y Heap O(|A| log |V |)

Algoritmo de Kruskal:

• Con MFset: O(|A| log |A|) = O(|A| log |V |)

PRIM PRIM+Heap KRUSKAL

O(|V |2) O(|A| log |V |) O(|A| log |A|)

Grafo Denso (|A| ≈ |V |2) O(|V |2) O(|V |2 log |V |) O(|V |2 log |V |)

Grafo Disperso (|A| ≈ |V |) O(|V |2) O(|V | log |V |) O(|V | log |V |)


EDA-6

3. CAMINOS DE MINIMO PESO EN GRAFOS DIRIGIDOS

Dado un grafo G = (V,A) dirigi-do y ponderado por una funcionp : A → R≥0, se define el peso de uncamino v0, v1, . . . , vk como la suma delos pesos de sus aristas:

p(v0, v1, . . . , vk) =k∑

i=1

p(vi−1, vi) 5

2

10

2 3 6

7

49

1

s

u v

yx

Problema: Se quiere calcular el camino de mınimo peso (camino mas corto) ysu peso asociado desde un vertice origen s a un vertice destino t.


EDA-6

3. CAMINOS DE MINIMO PESOConsideraciones

Si el grafo es no dirigido, podemos obtener un grafo dirigido sin mas queduplicar cada arista {u, v} en cada direccion: (u, v) y (v, u) ambas con elmismo peso. Por tanto, reducimos el problema al caso de grafos dirigidos.

Si no hay una arista entre dos vertices, podemos asumir que es “equivalente”a que exista una arista con peso infinito.

Es posible que no exista el camino de menor coste entre dos vertices s y t sipodemos llegar de s a t por un camino que incluya un ciclo de peso negativo.En tal caso, dando suficientes vueltas al ciclo podemos obtener caminos depeso arbitrariamente bajo.


EDA-6

3. CAMINOS DE MINIMO PESOAlgoritmos

Si todos los arcos tienen el mismo peso y este es positivo, el algoritmo debusqueda primero en anchura (BFS, visto en tema 4) desde s nos proporcionalos costes de s a todos los demas vertices.

En el caso de grafos acıclicos, podemos utilizar tecnicas de programaciondinamica (se vera en la asignatura “Algorıtmica”).

En el caso de grafos con ciclos y pesos positivos, podemos utilizar el algoritmode Dijkstra, que veremos a continuacion.


EDA-6

3. CAMINOS DE MINIMO PESOAlgoritmos

Para grafos con ciclos y pesos negativos, es posible utilizar el algoritmo deBellman-Ford, que ademas puede detectar la presencia de ciclos de pesonegativo en el camino de s a t.

Para calcular el coste de todos los caminos entre todos los pares de verticesdel grafo, podemos iterar con uno de los algoritmos previos o bien utilizar elalgoritmo de Floyd-Warshall.

Existen otros algoritmos. Por ejemplo, cuando es facil obtener una cotaoptimista ajustada de la distancia (como la distancia euclıdea entre ciudades,etc.) es posible utilizar tecnicas de ramificacion y poda.


EDA-6

3. ALGORITMO DE BELLMAN-FORD

Queremos calcular la distancia desde s.Mantenemos en un vector D una cota superior D[u] de la distancia de s a u.Utilizamos las aristas para mejorar la cota:

1 if (D[v] > D[u]+coste(u,v)) D[v] = D[u]+coste(u,v);

El algoritmo de Bellman-Ford es como sigue:

1 Inicializar vector D con D[v]=infinito excepto D[s]=0;2 Iterar |V|-1 veces:3 Para cada arista (u,v) del grafo:4 Si (D[v] > D[u]+coste(u,v))5 D[v] = D[u]+coste(u,v);6 FinPara7 FinIterar8 Para cada arista (u,v) del grafo:9 Si (D[v] > D[u]+coste(u,v)) BUCLE NEGATIVO, PARAR

10 FinPara11 Devolver D[t]

En el caso general (pesos negativos) es necesario procesar las aristas mas deuna vez.


EDA-6

3. ALGORITMO DE DIJKSTRA

Requiere pesos positivos. Consigue procesar los vertices y aristas una sola vez.Utiliza el mismo vector de cotas superiores de la distancia desde s que Bellman-Ford. La diferencia estriba en que se puede garantizar un orden de seleccionde vertices de modo que cada vertice seleccionado tiene en D la verdaderadistancia, no solo una cota.Es decir, este algoritmo mantiene un conjunto de vertices S cuyo peso del caminomas corto desde el origen s ya es conocido. El algoritmo va seleccionando elvertice u ∈ V − S con la mejor estimacion del camino mınimo, lo inserta enS y utiliza las aristas que salen de u para actualizar la cota de los vertices deV − S.Idea voraz: empezando en el vertice origen s, construir incrementalmentecaminos a los demas vertices seleccionando en cada paso un vertice v noseleccionado anteriormente tal que:

Exista algun vertice u ∈ V ya seleccionado previamente tal que (u, v) ∈ A.

Al anadir (u, v) al camino que terminaba en u se produzca el menorincremento de peso posible.


EDA-6

3. ALGORITMO DE DIJKSTRA

1 int Dijkstra(GrafoDirigidoPonderado *G, int s, int t) {2 vectorVerticeFloat Distancia; vectorVerticeBoolean Fijados;3 for (int u = 0; u < G->vertices; u++) {4 Distancia[u] = infinito;5 Fijados[u] = false;6 }7 Distancia[s] = 0;8 while (not Fijados[t]) {9 min = infinito;

10 for (int u=0; u < G->vertices; u++)11 if (!Fijados[u] && Distancia[u] < min) {12 min=Distancia[u]; v=u;13 }14 Fijados[v] = true;15 for ((v,w) arista de G)16 if (!Fijados[w] && Distancia[w] > Distancia[v] + peso(v,w))17 Distancia[w] = Distancia[v] + peso(v,w);18 }19 return Distancia[t];20 }


EDA-6

3. ALGORITMO DE DIJKSTRA: UN EJEMPLO

5

2

10

2 3 6

7

49

1

s

u v

yx

Iteracion u Fijados Por fijar D[s] D[u] D[v] D[x] D[y]0 - ∅ {s, u, v, x, y} 0 ∞ ∞ ∞ ∞


EDA-6


5

2

10

2 3 6

7

49

1

s

u v

yx

Iteracion u Fijados Por fijar D[s] D[u] D[v] D[x] D[y]0 - ∅ {s, u, v, x, y} 0 ∞ ∞ ∞ ∞1 s {s} {u, v, x, y} 0 10 ∞ 5 ∞


EDA-6


5

2a

10

2 3 6

7

49

1

s

u v

yx

Iteracion u Fijados Por fijar D[s] D[u] D[v] D[x] D[y]0 - ∅ {s, u, v, x, y} 0 ∞ ∞ ∞ ∞1 s {s} {u, v, x, y} 0 10 ∞ 5 ∞2 x {s, x} {u, v, y} 0 8 14 5 7


EDA-6


5

2a

10

2 3 6

7

49

1

s

u v

yx

Iteracion u Fijados Por fijar D[s] D[u] D[v] D[x] D[y]0 - ∅ {s, u, v, x, y} 0 ∞ ∞ ∞ ∞1 s {s} {u, v, x, y} 0 10 ∞ 5 ∞2 x {s, x} {u, v, y} 0 8 14 5 73 y {s, x, y} {u, v} 0 8 13 5 7


EDA-6


5

2a

10

2 3 6

7

49

1

s

u v

yx

Iteracion u Fijados Por fijar D[s] D[u] D[v] D[x] D[y]0 - ∅ {s, u, v, x, y} 0 ∞ ∞ ∞ ∞1 s {s} {u, v, x, y} 0 10 ∞ 5 ∞2 x {s, x} {u, v, y} 0 8 14 5 73 y {s, x, y} {u, v} 0 8 13 5 74 u {s, x, y, u} {v} 0 8 9 5 7


EDA-6


5

2a

10

2 3 6

7

49

1

s

u v

yx

Iteracion u Fijados Por fijar D[s] D[u] D[v] D[x] D[y]0 - ∅ {s, u, v, x, y} 0 ∞ ∞ ∞ ∞1 s {s} {u, v, x, y} 0 10 ∞ 5 ∞2 x {s, x} {u, v, y} 0 8 14 5 73 y {s, x, y} {u, v} 0 8 13 5 74 u {s, x, y, u} {v} 0 8 9 5 75 v {s, x, y, u, v} ∅ 0 8 9 5 7


EDA-6


5

2

10

2 3 6

7

49

1

s

u v

yx

Iteracion u Fijados Por fijar D[s] D[u] D[v] D[x] D[y]0 - ∅ {s, u, v, x, y} 0 ∞ ∞ ∞ ∞1 s {s} {u, v, x, y} 0 10 ∞ 5 ∞2 x {s, x} {u, v, y} 0 8 14 5 73 y {s, x, y} {u, v} 0 8 13 5 74 u {s, x, y, u} {v} 0 8 9 5 75 v {s, x, y, u, v} ∅ 0 8 9 5 7


EDA-6

3. ALGORITMO DE DIJKSTRACorreccion del algoritmo de Dijkstra

Es inmediato ver que D[v] ≥ d(s, v) en todo momento. Basta con ver que sealcanza la igualdad en cada vertice que es “fijado”. El caso inicial s es sencillo.Para el resto de casos, sea u el vertice a fijar. Por reduccion al absurdo sobreel criterio de eleccion del vertice, se demuestra que el camino de s a u utilizaunicamente vertices fijados. Es decir, no puede haber ningun camino mas cortohasta u que pase por vertices (ejemplo y) que no estan fijados, pues en tal caso seeligirıa y antes que u:

u

x ys up1 p2

Sp2

p1

s

x

y

Esta demostracion requiere que todos los pesos de las aristas sean positivos. Portanto, D[u] es la distancia del camino mas corto desde el origen s al vertice u.


EDA-6

3. ALGORITMO DE DIJKSTRA: COSTE

G implementado como una lista de adyacencia

Existen |V | operaciones de extraccion del mınimo en el vector, con un coste O(|V |).

Cada vertice v ∈ V se fija exactamente una vez, de forma que cada arista en la lista deadyacencia se examina una unica vez. Debido a que el numero total de aristas en G es|A|, existen |A| iteraciones de este bucle, y cada iteracion tiene un coste O(1).

Por tanto, el coste total del algoritmo es O(|V |2 + |A|) = O(|V |2).


EDA-6

3. ALGORITMO DE DIJKSTRA CON UN HEAP: COSTE

G implementado como una lista de adyacencia...

...y utilizando un MinHeap doblemente indexado H ordenado segun D

e indexado por los vertices

(algoritmo de Dijkstra modificado):

Existen |V | operaciones de extraccion del mınimo en un Heap, con un coste O(log |V |).Hay que anadir el tiempo de construir el Heap, O(|V |).

En cada iteracion del bucle que recorre las aristas, si D[v] > D[u] + peso(u, v), sedebera modificar D[v] y, por tanto, modificar el Heap, con un coste O(log |V |). El numerode veces que se ejecuta el bucle es O(|A|).

Por tanto, el tiempo total del algoritmo sera O((|V |+ |A|) log |V |) = O(|A| log |V |).


EDA-6

3. OBTENCION DEL VALOR Y DEL CAMINO MAS CORTO

1 void Dijkstra(GrafoDirigidoPonderado *G, int s, int t,2 float *Distancia, int *Predecesor) {3 vectorBoolean Fijados;4 for (int u = 0; u < G->vertices; u++) {5 Distancia[u]=infinito; Fijados[u]=false; Predecesor[u]=s;6 }7 Distancia[s] = 0;8 while (not Fijados[t]) { // para calcular dist. Aonicamente a t9 min = infinito;

10 for (int u=0; u < G->vertices; u++)11 if (!Fijados[u] && Distancia[u] < min) {12 min=Distancia[u]; v=u;13 }14 Fijados[v] = true;15 for ((v,w) arista de G)16 if (!Fijados[w] && Distancia[w] > Distancia[v] + peso(v,w)) {17 Distancia[w]=Distancia[v]+peso(v,w); Predecesor[w]=v;18 }19 }20 // devolvemos por ref. Distancia y Predecesor (para recuperar camino)21 }


EDA-6

3. ALGORITMO DE DIJKSTRA: TODOS LOS CAMINOS MıNIMOS

Dado un grafo dirigido G = (V,A) (V es el conjunto de nodos y A es el conjunto dearcos) ponderado por p : V ×V → R≥0, escribir un algoritmo que calcule los costes delos caminos mınimos entre cualquier par de nodos del grafo haciendo uso unicamentede algoritmos vistos en clase.


EDA-6

3. ALGORITMO DE DIJKSTRA: TODOS LOS CAMINOS MıNIMOS

Dado un grafo dirigido G = (V,A) (V es el conjunto de nodos y A es el conjunto dearcos) ponderado por p : V ×V → R≥0, escribir un algoritmo que calcule los costes delos caminos mınimos entre cualquier par de nodos del grafo haciendo uso unicamentede algoritmos vistos en clase.

1 void TodosCaminosCortos (GrafoPonderado *G, MatrizDistancias &M) {2 for (u = 0; u < G->vertices; u++)3 M[u] = Dijkstra(G, u); // calcula la distancia4 // de u a todos los demas5 }

Si el coste del algoritmo de Dijsktra es O(|V |2), entonces el coste temporal de estealgoritmo es O(|V |3) y el coste espacial es O(|V |2).Para grafos dispersos, se puede obtener una implementacion mas cuidada para elalgoritmo de Dijsktra de O((|V | + |A|) log |V |), por tanto el algoritmo propuestosera O(|V |(|V |+ |A|) log |V |).


EDA-6

4. FLUJO MAXIMO EN UN GRAFO

Una red de flujo G = (V,E) es un grafo dirigido en el cual cada arista(u, v) ∈ E tiene asociada una capacidad maxima c(u, v) ≥ 0.

Si una arista no pertenece a la red de flujo, entonces se supone que sucapacidad maxima es 0.

Una red de flujo tiene dos nodos especiales denominados fuente y sumidero.

Un flujo en una red de flujo es un conjunto de pesos no negativos de aristasque satisfacen las condiciones:

• Ningun peso es mayor que la capacidad de la arista• El flujo total que entra en un nodo es igual al flujo total que sale del nodo

(excepto para los nodos fuente y sumidero).


EDA-6

4. FLUJO MAXIMO EN UN GRAFO

Sea G = (V,E) una red de flujo con una fuente s y un sumidero t. Un flujo enG es un funcion f : V × V → R que cumple tres propiedades:

Restriccion de capacidad: ∀u, v ∈ V, f(u, v) ≤ c(u, v)

Simetrıa inversa: ∀u, v ∈ V, f(u, v) = −f(v, u)

Conservacion de flujo: para todo u ∈ V − {s, t},∑

v∈V f(u, v) = 0.

El valor f(u, v) se denomina flujo del nodo u al nodo v. El valor de un flujof (denotado como |f |) se define como: |f | =

∑v∈V f(s, v), es decir, el flujo

total que sale de la fuente.

Dada una red de flujo G con una fuente s y un sumidero t, el problemadel flujo maximo consiste en encontrar un flujo de valor maximo.


EDA-6

4. FLUJO MAXIMO EN UN GRAFOAplicaciones

El problema del flujo maximo no solo es importante desde un punto devista teorico, sino que tiene aplicaciones practicas en multitud de problemasde planificacion, asignacion de recursos, sirve de modelo para una variedad deproblemas de programacion lineal, acoplamiento en grafos bipartidos, problemasde conectividad, etc.Este problema esta estrechamente relacionado con encontrar la “cortaduramınima” entre s y t en el grafo.


EDA-6

4. FLUJO MAXIMO EN UN GRAFOCortadura mınima entre s y t

Una cortadura entre s y t en el grafo G=(V,A) es una particion (X, Y ) delos vertices del grafo (X ∪ Y = V,X ∩ Y = ∅), tal que s ∈ X y t ∈ Y .

La capacidad de una cortadura se define:

cap(X, Y ) =∑

u∈X,v∈Y

c(u, v)

El flujo de s a t en G puede calcularse considerando unicamente las aristasque van de un vertice de X a otro de Y .

Consecuentemente, para cualquier flujo f y cualquier cortadura (X, Y ) secumple |f | ≤ cap(X, Y ).

El teorema “flujo maximo cortadura mınima” establece que esa desigualdadse alcanza para el flujo maximo. Es decir, f es un flujo maximo si y solosi |f | = cap(X, Y ) para una cortadura (X, Y ) del grafo, y en tal caso esacortadura tiene capacidad mınima.


EDA-6

4. FLUJO MAXIMO EN UN GRAFOAlgoritmos

Los algoritmos para encontrar el flujo maximo pueden dividirse en dos familiasen funcion de si mantienen o no la restriccion de conservacion de flujo:

Caminos de aumento Se basan en mantener un flujo valido en todo momento.Aumentan el flujo de s a t de manera iterativa. Partiendo de un “flujo posible”arbitrario (por ejemplo, flujo nulo) se busca un camino de s a t en un graforesidual que permita aumentar el flujo. Bajo ciertas condiciones se garantizala terminacion del algoritmo.

Enviar preflujo Se relajan las condiciones a cumplir durante el transcurso delalgoritmo. Concretamente, se permite que el flujo neto en los vertices puedaser positivo, si bien al finalizar el algoritmo el flujo debe cumplir la condicionde conservacion de flujo. Se basan en enviar el exceso de flujo hacia elsumidero asociando a cada vertice una “altura” para controlar la direccionde envıo del exceso de flujo.


EDA-6

4. FLUJO MAXIMO EN UN GRAFOAlgoritmo de Ford-Fulkerson

El algoritmo de Ford-Fulkerson, que data de 1962, es el primer algoritmopropuesto para resolver el problema del flujo maximo. Se basa en el conceptode grafo residual.Dado un flujo f en un grafo G = (V,A), se define el grafo residual Gf comoaquel grafo con los mismos vertices que G, arcos (u, v) tal que (u, v) ∈ Ao (v, u) ∈ A y capacidades cf(u, v) = c(u, v)− f(u, v). Es decir, por cada arcodel grafo G aparecen dos arcos en sentidos opuestos en el grafo residual.Un camino aumentado es un camino de s a t en el grafo residual Gf que pasepor arcos con capacidad residual cf no nula.


EDA-6


1 inicializar flujo f=0;2 construir grafo residual Gf asociado a f=0;3 maxflow = 0;4 while (existe camino de aumento de s a t en Gf) {5 delta = menor capacidad del camino de aumento;6 maxflow += delta;7 para cada arista (u,v) del camino de aumento hacer {8 c_f(u,v) -= delta;9 c_f(v,u) += delta;

10 }11 }12 return maxflow;


EDA-6


Se demuestra que si el algoritmo termina (si no existe ningun camino deaumento), el flujo devuelto es maximo.El coste del algoritmo depende del coste de cada iteracion (buscar un caminode aumento y recorrerlo para actualizar el grafo residual) y del numero deiteraciones.Si las capacidades son todas valores enteros, el algoritmo terminara y ademas,por la propiedad de integridad, el flujo maximo sera un valor entero. Sin masinformacion sobre los caminos utilizados, el numero de pasos puede ser tanalto como la capacidad maxima de las aristas, con lo que el coste serıa nopolinomico con la talla del grafo.


EDA-6

4. FLUJO MAXIMO EN UN GRAFOAlgoritmo de Edmonds-Karp

Edmonds y karp demostraron que si en el algoritmo de Ford-Fulkerson se utilizael camino de aumento mas corto en cada iteracion, el algoritmo consiguemejores cotas asintoticas: se vuelve polinomico con coste O(|V | · |A|2).El algoritmo de Edmonds-Karp es tan simple como utilizar busqueda primeroen anchura (BFS) para buscar el camino de aumento en el algoritmo deFord-Fulkerson.


estructuras de datos y algoritmos -...

Documents