notas de discreta 2

8/18/2019 Notas de Discreta 2

1/111

Resumen de Discreta II

Maximiliano Illbele

16 de agosto de 2012

Índice

1. Coloreo y repaso de grafos 4

1.0.1. BFS-DFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.1. Coloreo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.1.1. Número Cromático . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.1.2. Algoritmo “Greedy” para coloreo . . . . . . . . . . . . . . . . . . . 71.1.3. Propiedades de Greedy . . . . . . . . . . . . . . . . . . . . . . . . . 81.1.4. Heurísticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2. Flujos en networks 122.1. Algoritmo de Greedy para hallar Flujo . . . . . . . . . . . . . . . . . . . . 14

2.1.1. Ejemplos de Greedy . . . . . . . . . . . . . . . . . . . . . . . . . . 142.1.2. Complejidad de Greedy . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2. Algoritmo de Ford y Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . 152.2.1. Lema del Camino Aumentante . . . . . . . . . . . . . . . . . . . . . 16

2.3. Teorema: Max-Flow Min-Cut . . . . . . . . . . . . . . . . . . . . . . . . . 202.3.1. Complejidad de Ford Fulkerson . . . . . . . . . . . . . . . . . . . . 21

2.4. Algoritmo de Edmonds Karp . . . . . . . . . . . . . . . . . . . . . . . . . . 232.4.1. Complejidad de Edmonds-Karp . . . . . . . . . . . . . . . . . . . . 242.4.2. Ejemplo de Edmonds Karp . . . . . . . . . . . . . . . . . . . . . . . 272.4.3. Pseudo-Código de Edmonds Karp . . . . . . . . . . . . . . . . . . . 28

2.5. Algoritmos Tipo Dinic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.5.1. Esquema general Tipo Dinic . . . . . . . . . . . . . . . . . . . . . . 30

2.5.2. Ejemplo de Dinic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.5.3. Pseudo Código algoritmos Tipo Dinic . . . . . . . . . . . . . . . . . 332.5.4. Complejidad de Dinic . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.6. Algoritmo Wave de Tarjan . . . . . . . . . . . . . . . . . . . . . . . . . . . 362.6.1. Pseudo Código de Wave . . . . . . . . . . . . . . . . . . . . . . . . 362.6.2. Complejidad de Wave . . . . . . . . . . . . . . . . . . . . . . . . . . 382.6.3. Ejemplos de Wave . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

1


2/111

3. MST 413.1. Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.1.1. Pseudo Código de Kruskal . . . . . . . . . . . . . . . . . . . . . . . 433.1.2. Teorema: Kruskal devuelve un MST . . . . . . . . . . . . . . . . . . 433.1.3. Complejidad de Kruskal . . . . . . . . . . . . . . . . . . . . . . . . 443.1.4. Kruskal Delete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.1.5. Complejidad Kruskal Delete . . . . . . . . . . . . . . . . . . . . . . 443.1.6. Ejemplo de Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.2. PRIM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463.2.1. Pseudo Código de Prim . . . . . . . . . . . . . . . . . . . . . . . . 463.2.2. Correctitud de Prim . . . . . . . . . . . . . . . . . . . . . . . . . . 463.2.3. Ejemplo de Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.3. Implementaciones de Union Find . . . . . . . . . . . . . . . . . . . . . . . 483.3.1. Union Find con listas enlazadas . . . . . . . . . . . . . . . . . . . . 48

3.3.2. Union Find con Representantes . . . . . . . . . . . . . . . . . . . . 483.3.3. Union Find con ranking . . . . . . . . . . . . . . . . . . . . . . . . 49

4. Matchings 514.1. Transformación del problema de Matching a uno de flujo maximal . . . . . 514.2. Teorema de Hall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.3. Complejidad del Algoritmo de Matching . . . . . . . . . . . . . . . . . . . 534.4. Grafos con Peso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.4.1. Algoritmo de “Gross” . . . . . . . . . . . . . . . . . . . . . . . . . . 544.4.2. Ejemplo del algoritmo de “Gross” . . . . . . . . . . . . . . . . . . . 55

4.5. Prueba del teorema de HALL . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.6. Teorema del Matrimonio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614.7. Minimizar la Suma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

4.7.1. Ejemplo de Matching que minimiza la Suma (A ojo) . . . . . . . . 624.7.2. Algoritmo Húngaro . . . . . . . . . . . . . . . . . . . . . . . . . . . 634.7.3. Ejemplo del algoritmo Húngaro . . . . . . . . . . . . . . . . . . . . 634.7.4. Complejidad de algoritmo Hungaro . . . . . . . . . . . . . . . . . . 654.7.5. EJEMPLO DEL MEJORADO (FALTA) . . . . . . . . . . . . . . . 67

5. Códigos de correción de errores 685.1. Cota de Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715.2. Matriz generadora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745.3. Matriz de chequeo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 755.4. Cota Singleton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805.5. Códigos Cíclicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

5.5.1. Correción de errores “Error Trapping” . . . . . . . . . . . . . . . . . 87

6. P-NP 906.1. La clase P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 906.2. La Clase NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 906.3. Co-NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 916.4. SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

2


3/111

6.4.1. Reducción Polinomial . . . . . . . . . . . . . . . . . . . . . . . . . . 926.4.2. k − color ≤P SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

6.5. NP Completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 946.5.1. 3-SAT es NP completo . . . . . . . . . . . . . . . . . . . . . . . . . 946.5.2. 3-color es NP completo . . . . . . . . . . . . . . . . . . . . . . . . . 966.5.3. Ejemplo 3-SAT ≤P 3-color . . . . . . . . . . . . . . . . . . . . . . . 976.5.4. 2-SAT ∈ P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1006.5.5. HORN-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

7. Introducción a la Inteligencia Artificial 1027.1. Hill Climbing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1027.2. Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1027.3. Algoritmos Evolutivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1027.4. Algoritmos Genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

7.4.1. Selección . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1037.5. Ejemplo de un AG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1037.5.1. Codificación del ejemplo . . . . . . . . . . . . . . . . . . . . . . . . 1047.5.2. Fitness del ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . 1047.5.3. Entrecruzamiento del ejemplo . . . . . . . . . . . . . . . . . . . . . 1047.5.4. Mutación del ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . 1047.5.5. Selección del ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . 1057.5.6. Operadores de Selección . . . . . . . . . . . . . . . . . . . . . . . . 1057.5.7. Remainde Methods (Métodos del “Resto”) . . . . . . . . . . . . . . 1077.5.8. Otros métodos Fitness Proportional . . . . . . . . . . . . . . . . . . 1077.5.9. Sigma Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

7.5.10. Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1097.5.11. Mutación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1107.5.12. Mutaciones con Permutaciones . . . . . . . . . . . . . . . . . . . . . 110

7.6. No Free Lunch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

3


4/111

1. Coloreo y repaso de grafos

Recordemos que un grafo G es un par (V, E ) donde E ⊆ {A ⊆ V : |A| = 2}.Donde V es el conjunto de vértices o nodos y E es el conjunto de lados1 o aristas.

Ejemplo: sea G = {1, 2, 3},{1, 2}, {1, 3}Gráfico(G) : 1

2 3

Notación usual

{x, y} → xy

“Vecinos” de un nodo x: Γ(x) = {y ∈ V : xy ∈ E }

Grado2 o Valencia de un vértice: d(x) =Γ(x)

Menor valencia de G: δ = mı́n{d(x) : x ∈ V }

Mayor valencia de G: ∆ = máx{d(x) : x ∈ V }

Definiciones

Un grafo es regular si δ = ∆, a veces llamados “k-regular”.

Un camino es una sucesión de vértices x1, x2, . . . , xt todos distintos tales quexixi+1 ∈ E .

Un grafo es conexo si ∀par de vértices ∃ un camino entre ellos.

Conexo Disconexo

1

4 5

2 3

1

4

2 3 5En general definimos x ≈ y ⇔ ∃ camino entre x e y .

Ejercicio: demostrar que ≈ es una relación de equivalencia.

1. Reflexividad: x ≈ x

2. Simetría: x ≈ y ⇒ y ≈ x

3. Transitividad: x ≈ yy ≈ z

⇒ x ≈ z

1Edges.2Degree.

4


5/111

Una componente conexa de G es una clase de equivalencia de la relación ≈.Notación

La cantidad de vértices: n = |V |.

La cantidad de lados: m = |E |.

Observación

m ≤

n

2

= n∗(n−1)

2

Si G es conexo ⇒ n − 1 ≤ m

1.0.1. BFS-DFS

DFS(x)-Depth First Search3

Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que valocalizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodosque visitar en dicho camino, sube en el árbol, de modo que repite el mismo proceso concada uno de los hermanos del nodo ya procesado.

Ejemplo DFS

G ⇒ A

DF S (A) ⇒ A

Nivel 0

B

C

D

B

Nivel 1

E G

C

Nivel 2

F D

Nivel 3

E G

Nivel 4

F Nivel 5

3DFS: Búsqueda en profundidad.

5


6/111

BFS(x) - Breadth First Search4

Intuitivamente, se comienza en la raíz x y se exploran todos sus vecinos. A continuaciónpara cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hastaque se recorra todo el Grafo.

Ejemplo BFS

G ⇒ A

BF S (A) ⇒ A

Nivel 0

B

C

D

B

C

D Nivel 1

E G

E G

Nivel 2

F F Nivel 3

1.1. Coloreo

Un coloreo (propio) de G = (V, E ) con k colores es una función C : V → {1, 2, . . . , k}tal que si: xy ∈ E ⇒ C (x) = C (y)

Ejemplo de coloreo

A(1)

B(2)

C (3)

D(2)

E (1) G(1)

F (2)

1.1.1. Número Cromático

En general deseamos calcular el número cromático de G : χ(G).Donde χ(G) = mı́n{k : ∃ un coloreo propio de G con k colores }.

Propiedad: 1 ≤ χ(G) ≤ n

4BFS: búsqueda en anchura.

6


7/111

1.1.2. Algoritmo “Greedy” para coloreo

Requiere un orden de los vértices: x1, . . . , xn.Inicio: C (x1) = 1

Para j > 1

C (x j) = El menor color que no crea conflicto con los vértices ya coloreados.

C (x j) = mı́n

k : C (xi) = k ∀i < j : xi ∈ Γ(x j)

Invariante: en todo momento el coloreo es propio, por lo tanto al terminar da uncoloreo propio.

Ejemplo:

B

C

D

A

E

G F

Orden alfabético Orden alternativoVértices A B C D E F G

Color 1 2 1 2 1 3 4G C D F B A E1 2 3 2 1 2 1

Complejidad de coloreo con Greedy

Od(x1) + d(x2) + . . . + d(xn) = O(2m) = O(m)Teorema: sea G = C 2r+1 ⇒ χ(G) = 3

Prueba: Supongamos que χ(G) = 2Sea A el color del primer vértice.Sea B el color del segundo vértice.

x1x2 ∈ E ⇒ A = B

Como estamos suponiendo χ(G) = 2 estos son los únicos colores que podemos usar.

Como x2x3 ∈ E ⇒ C (x3) = B ⇒ C (x3) = AComo5 x3x4 ∈ E ⇒ C (x4) = BPor inducción:

C (xi) =

A cuando i es ImparB cuando i es Par

Pero entonces el lado x1 A

x2r+1 A

tiene los 2 vértices del mismo color Absurdo.

5Este paso es sólo ilustrativo no forma parte de una demostración formal ya que no sabemos si n > 3ó n = 3.

7


8/111

∴ χ(G) ≥ 3

Y está claro que con 3 colores alcanza definimos:

C (xi) = A cuando i es Impar


9/111

Luego Greedy corriendo en orden x1, . . . , x2r = x8 va a necesitar r = 4 colores:

Color 1 2 3 4Vértice x1 x3 x5 x7

x2 x4 x6 x8

Pero si definimos C (xi) =

1 i es impar2 i es par

nos queda que χ(G) = 2

Conclusión:Greedy(G) devuelve un coloreo que usa r colores, pero vimos que χ(G) = 2.

Sin embargo . . .

Propiedad: ∀G ∃ un ordenamiento {x1, . . . , xn} de los vértices de G en el cual Greedy()obtiene: χ(G)

Prueba: sea t = χ(G)

Sean V 1 los vértices de color 1Sean V 2 los vértices de color 2

...Sean V t los vértices de color t

en algún coloreo (propio) con t colores.Inducción en t:Si t = 1 obvio.Supongamos que vale para t − 1Orden de los vértices:

Los de V 1 < los de V 2 < . . . < los de V t , en V i los ordeno como quiero.

Por hipótesis inductiva hasta V t−1 lo coloreamos con t − 1 colores.Los de V t no están unidos entre si ⇒ Greedy en cada uno de sus vértices usará uno

de los primeros t − 1 colores o el color t, nunca hay conflicto entre ellos que demande uncolor t + 1.

Propiedad: χ(G) ≤ ∆ + 1

Prueba: usar Greedy en cualquier orden.Cuando vayamos a colorear xi lo peor que puede pasar es que todos los vecinos yaestén coloreados y con colores distintos, esto forzaría a Greedy() a usar un color distintoa esos d(xi) de esos colores.

Pero d(xi) ≤ ∆ ∴ Greedy con ∆ + 1 colores se las arregla.

9


10/111

Más aún, si G es conexo o todas sus componentes conexas sean no regulares, tenemosque:

δ = ∆ ⇒ χ(G) ≤ ∆

Prueba: sea x ∈ V : d(x) = δ Corramos B F S (x)6 y sea x1, . . . , xn el orden inverso al de BFS(x) ∴ xn = xEn BF S (x)7 todo vértice, salvo x es incorporado al árbol por medio de un vecino que

ya está en el árbol.∴ En el orden inverso todo vértice distinto de x tiene un vecino posterior en el orden

(x1, . . . , xn).∴ Cuando Greedy va a colorear xi : i < n, como xi tiene por lo menos un vecino

posterior entonces xi tiene ≤ d(xi) − 1 vecinos anteriores.

∴ Hay a lo sumo d(xi) − 1 ≤ ∆ − 1 posibles “conflictos”.

∴ Greedy puede colorear con alguno de los ∆ colores.Ahora queda colorear xn = xGreedy necesita usar d(x) + 1 colores: d(x) = δ


11/111

Luego corro Greedy con: x6 = 1 x5 = 6 x4 = 4 x3 = 5 x2 = 3 x1 = 2

Es decir en el orden: 2, 3, 5, 4, 6, 1

Y nos da χ(G) = 2

3. RLF: Recursive Largest First

1 RLF()2 {3 c o l o r = 1 ;4 R = V; // Vértices no C o l o r e a d o s 5 while ( R = ∅ ) {6 L = R;7 while ( L = ∅ ) {8 Tomar v de L : V t en ga l a mayor ca nt id ad de v e ci no s en R9 C ol or ( v ) = c o l o r ;

10 Remover ( v ) de R;

11 Remover ( v ) y Γ(v ) d e L ;12 }13 C ol or ++;14 }15 }

4. D-Saturd5(x) = #de colores de los vecinos coloreados de x .

Corre Greedy con un orden dinámico eligiendo como “próximo vértice” el que tengad5 más grande.

11


12/111

2. Flujos en networks

Un network (dirigido) es un grafo dirigido, es decir un par (V, E ) : E ⊆ V ∗ V conpesos en los lados, es decir con una función C : E → R.

En este contexto siempre pediremos C : E → R≥0 y los C (x, y) se llaman capacidades.Notación:

(x,y) → →xy (si se sobreentiende por el contexto también xy).

Γ+(x) = {y ∈ V : →xy ∈ E }.

Γ−(x) = {y ∈ V : →yx ∈ E }.

Γ(x) = Γ+(x) ∪ Γ−(x).

Definición: dado un network N = (V , E , C ) y vértices distinguidos s, t ∈ V , un flujo

en N , de s a t es una función f : E → R tal que:1. Feasability8: 0 ≤ f (

→xy) ≤ C (

→xy) ∀

→xy ∈ E

2. Conservación: y∈Γ+(x)

f (→xy) =

y∈Γ−(x)

f (→yx) ∀x = s, t

3. s Productor: y∈Γ+(s)

f (→sy) ≥

y∈Γ−(s)

f (→ys)

Como s produce se llama la fuente9 y t se llamará resumidero10.

En algunos textos se pide directamente que: y∈Γ−(s) f (→ys) = 0O más aún: C (

→ys) = 0 ∀y ∈ Γ−(s)

Notación:y∈Γ+(x)

f (→xy) = Outf (x)

y∈Γ−(x)

f (→yx) = I nf (x)

Definición: el valor del flujo es V (f ) = Outf (s) − Inf (s)

8Viabilidad.9Source.10Sink.

12


13/111

Propiedad: V (f ) = I nf (t) − Outf (t)

Prueba:

Sea D = I nf (t) − Outf (t)

Outf (x) − Inf (x) =

0 x = s, tV (f ) x = s−D x = t

∴

x∈V

Outf (x) − Inf (x)

= V (f ) − D

Notación: Si A, B ⊆ V entonces f (A, B) = x ∈ Ay ∈ B→xy ∈ E

f (→xy)

x∈V

Outf (x) =x∈V

y∈Γ+(x)

f (→xy) (1)

=

x, y ∈ V →xy ∈ E

f (→xy)

= f (V, V ) (2)

( 1) Por definición de Outf (x).( 2) Notación.Similarmente:

x∈V Inf (x) =

x∈V

y∈Γ−(x)

f (→yx) (3)

=

x, y ∈ V →yx ∈ E

f (→yx)

= f (V, V )

( 3) Por definición de I nf (x).

∴ Nos queda: f (V, V ) − f (V, V ) =0

= V (f ) − D

∴ V (f ) = D

13


14/111

Problema a resolver: dado un network N hallar f que maximice V (f ).

Esto se conoce como el problema del flujo maximal11.

Notación:Sea s = x0, x1, . . . , xr = t : −→xixi+1 ∈ E , la notación: s, x1, . . . , xr−1, t :

Significa que se mandan unidades de flujo a través de ese camino, es decir, si G eraun flujo existente definimos:

f (→xy) =

G(

−→xixi+1) + Si

−→xy =

−→xixi+1

G(−→xy) Si no

2.1. Algoritmo de Greedy para hallar Flujo

“Hasta que no se pueda más buscar caminos de s a t y mandar flujo por ellos.”

2.1.1. Ejemplos de Greedy

Todas las capacidades son 10, excepto C (→

EF ) = 15.

A C

G

s

E F

t

B D

H

Corremos Greedy en orden alfabético

1. Primer camino: s, A, C, E, F, G, t: 10

2. Segundo camino: s, B, D, E, F, H, t: 5

3. No hay más caminos posibles.

Para este ejemplo podemos demostrar que no sólo es flujo sino también que es

maximal, ya que, en pocas palabras C (→

EF ) = 15 y es un cuello de botella, y nos

da: f (→

EF ) = 15

Ejemplo: todas las capacidades son 1000 excepto: C (

→CD) = 1 y C (

→CB) = 900

A

B

s

t

C

D

Corremos Greedy con el orden alfabético11Por ahora no está claro que f exista.

14


15/111

1. Primer camino: s, A, B, t: 1000

2. Segundo camino: s, C, D, t: 1

3. Terminamos porque no hay más posibles caminos.

En este caso el flujo obtenido (1001) no es maximal, el flujo maximal correspondientees: (1901)

Eligiendo caminos obtenemos el flujo maximal correspondiente :1901

1. Primer camino: s, A, D, t: 999

2. Segundo camino: s, A, B, t: 1

3. Tercer camino: s, C, B, t: 900

4. Cuarto camino: s, C, D, t: 1

2.1.2. Complejidad de Greedy

Greedy

Buscar camino dirigido: O(m)

Aumentar en ese camino: O(n)

Total por aumento: O(m) + O(n) = O(m)

¿Cuántos aumentos de flujo hay?

En Greedy una vez que un lado se “satura”, es decir f (→xy) = C (

→xy), no se vuelve a

usar, ya que no se devuelve flujo.Además sabemos que por cada aumento se satura al menos un lado.∴ Hay a lo sumo m aumentos.∴ Complejidad(Greedy) = m ∗ O(m) = O(m2)

2.2. Algoritmo de Ford y Fulkerson

Definición: un camino aumentante12 de s a t es una sucesión de vértices:s = x0, x1, . . . , xr = t : ∀i ≤ r − 1

O bien: −→xixi+1 ∈ E : f (

−→xixi+1) < C

−→xixi+1

estos son los lados Forward.

O bien: −→xi+1xi ∈ E : f (

−→xi+1xi) > 0 i.e. que haya mandado flujo, lados Backward.

“Hasta que no se pueda más buscar caminos aumentantes y mandar flujo por ellos”.

12Augmenting path.

15


16/111

2.2.1. Lema del Camino Aumentante

Si f es un flujo y se aumenta a lo largo de un camino aumentante el resultado tambiénes flujo. Más aún si se manda por el camino aumentante, el valor del nuevo flujo es

V (f ) + .Prueba:

Sea s = x0, x1, . . . , xr = t un camino aumentante.

Sea i =

C (

−→xixi+1) − f (

−→xixi+1) para los lados forward

f ( −→

xi+1xi) para los lados backward

Elijo = mı́n{i} “Aumentar f ” es tomar

f ∗( →xy) = f (

−→xixi+1) + Si

→xy =

−→xixi+1 forward

f ( −→xi+1xi) − Si →xy = −→xi+1xi backwardf (

→xy) en caso contrario

Queremos ver que f ∗ es flujo y que V (f ∗) = V (f ) +

Feasability: Obvio por definición de i , .

Conservación: x = s, t ⇒ x = xi : 0 < i < r.

Hay que analizar 4 casos:

1. F-F: xi−1

+−→ xi

+−→ xi+1

Outf ∗(xi) = Outf (xi) + // →xixi+1

Inf ∗(xi) = I nf (xi) + // →xi−1xi

Outf ∗(xi) − Inf ∗(xi) = Outf (xi) − Inf (xi) + − = 0 porque f es flujo.

2. F-B: xi−1+

−→ xi−

←− xi+1

Outf ∗(xi) = Outf (xi)

Inf ∗(xi) = I nf (xi) + −

Luego: Outf ∗(xi) − Inf ∗(xi) = 0

3. B-F: xi−1−

←− xi+

−→ xi+1

Inf ∗(xi) = I nf (xi)

Outf ∗(xi) = Outf (xi) + −


16


17/111

4. B-B: xi−1−

←− xi−

←− xi+1

Inf ∗(xi) = I nf (xi) −

Outf ∗(xi) = Outf (xi) −


En el caso de s:

1. s +−→ x1

Outf ∗(s) = Outf (s) +

Inf ∗(s) = I nf (s)

∴ V (f ∗) = V (f ) +

2. s −←− x1

Outf ∗(s) = Outf (s)

Inf ∗(s) = I nf (s) −

∴ V (f ∗) = V (f ) − (−)

= V (f ) +

Definición: dado N = (V , E , C ) con vértices s = fuente, t = resumidero.

Un corte es un subconjunto S ⊆ V : s ∈ S, t ∈ S

Ejemplos de cortes:

S = {s}.

S = V − {t}.

¿Cuántos cortes hay? 2n−2

La capacidad de un corte S es:

Cap(S ) = C (S, S ) : S = V − S

=

x ∈ S y ∈ S →xy ∈ E

C (→xy)

17


18/111

Lema: sea N network, f flujo y S corte entonces:

1. V (f ) = f (S, S ) − f (S, S )

2. V (f ) ≤ Cap(S )

3. Si V (f ) = Cap(S ) entonces f es Maximal, y S es Minimal i.e. el corte de menorcapacidad.

Prueba:

1. Observemos que:

f (A ∪ B, C ) = f (A, C ) + f (B, C ) : A, B disjuntos.

f (A, B ∪ C ) = f (A, B) + f (A, C ) : B, C disjuntos.

Además:

Outf (x) = f

{x}, V

Inf (x) = f

V, {x}

Además si x ∈ S :

Outf (x) − Inf (x) =

V (f ) Si x = s

0 Si x = s pues t ∈ S

x∈S

Outf (x) − Inf (x)

= 0 + . . . + 0 + V (f )

= V (f )

∴ V (f ) =x∈S

Outf (x) −x∈S

Inf (x)

=x∈S

f

{x}, V

−x∈S

f

V, {x}

(4)

= f (S, V ) − f (V, S )

= f (S, S ∪ S ) − f (S ∪ S, S ) (5)=

f (S, S ) + f (S, S ) − f (S, S ) − f (S, S ) (6)

= f (S, S ) − f (S, S )

( 4) Por la observación.

( 5) V = S ∪ S .

( 6) Disjuntos.

18


19/111

2. V (f ) 1= f (S, S ) − f (S, S )

≥0


20/111

2.3. Teorema: Max-Flow Min-Cut

En todo network el valor de todo flujo maximal es igual a la capacidad de todo corteminimal, es decir si f es maximal ⇒ ∃S corte : V (f ) = Cap(S ).

Demostración: dado f maximal13

construyamos S recursivamente así:

s ∈ S por definición.

Si x ∈ S, y ∈ Γ+(x) : f (→xy) < C (

→xy) entonces agregamos “y” a S .

† Si x ∈ S, y ∈ Γ−(x) : f (→yx) > 0 entonces agregamos “y” a S .

Es decir S es el conjunto de vértices que revisamos tratando de obtener un caminoaumentante de s a t.

Si t estuviera en S habría un camino aumentante de s a t.Por el lema del camino aumentante podríamos construir un flujo g tal que:

V (g) = V (f ) + para algún > 0∴ V (g) > V (f ) Absurdo pues f es maximal.

∴ t ∈ S i.e. S es corte.

Sólo resta ver que: V (f ) = Cap(S )

∴ Por el lema anterior: V (f ) = f (S, S ) − f (S, S )

Si

x ∈ S

y ∈ S →xy ∈ E

⇒ f (→xy) = C (

→xy) porque sino hubieramos agregado a “y” en algún momento

Def ⇒ f (S, S ) = C (S, S ) = Cap(S )

Six ∈ S y ∈ S →yx ∈ E

†⇒ f ( →yx) = 0 ⇒ f S, S = 0

∴ V (f ) = f (S, S ) − f (S, S )

= Cap(S ) − 0

= Cap(S )

Corolario14: Ford-Fulkerson es correcto i.e. si el output es un flujo f , entonces f esmaximal.

Prueba: el algoritmo aumenta a partir del flujo “0” usando caminos aumentantes hastaque no encuentra más caminos.

Sea f el flujo obtenido allí.

13Todavía no demostramos que exista.14De la demostración.

20


21/111

Cuando < F − F >15 intentó aumentar f no pudo, entonces camino aumentantepara f entre s y t.

∴ Los vértices que se buscaron formaron un corte S .Por la prueba del teorema16, tenemos que V (f ) = Cap(S ) entonces f es maximal por

el lema previo al teorema.

2.3.1. Complejidad de Ford Fulkerson

Los lados se pueden des-saturar por lo tanto el análisis de Greedy no vale.De todas maneras existen ejemplos en que < F − F > no termina, por lo que no

podemos hablar de su complejidad.Ejemplo en que < F − F > no termina

x1

y1

s

x2

y2

t

x3 y3

Capacidades: todas 2 salvo: −→

st : 1000 −→x1y1 : 1

−→x2y2 : r

−→x3y3 : r

2

Donde: r = −1+√ 5

2 es raíz de: P (r) = r2 + r − 1

Observación:

1 − r = r2

r − r2 = r3

Satisface: 1 > r > r2 > .. . > rk > r k+1

Corramos < F − F >

1. s, x1, y1, t : 1

2. s, x3, y3, ←−y1, x1, x2, y2, t : r

2

3. s, x2, y2, ←−y3, x3, x1, y1, t : r

3

4. s, x1, y1, ←−y2, x2, x3, y3, t : r

4

Luego < F − F > repite (2) (3) (4) con r5 r6 r7 . . .

15Denotaremos así al algoritmo de Ford-Fulkerson.16Max Flow Min Cut.

21


22/111

∴< F − F > no termina, más aún si f i son los flujos intermedios:

ĺımi→∞

V (f i) = 1 + r + r2 + r3 + . . .

= ∞i=0

ri − r

= 1

1 − r − r

= 1 − r(1 − r)

1 − r = 2

Pero el flujo maximal es: 1002, mandando st = 1000.Observación: si las capacidades son enteras entonces como el primer valor del flujo es

0 ∈ Z, y aumenta por:

= mı́n{i} : i = C − f f ∈ ZEntonces será un entero y los flujos intermedios también.∴ Si les llamamos f 1, f 2, . . . ⇒ V (f i+1) ≥ V (f i) + 1.Como hay cota superior, como por ejemplo: Cap({s}), en algún momento debemos parar.Es decir si las capacidades son enteras < F − F > siempre termina, inclusive cuando

termina sabemos que el flujo que devuelve es entero, sumado al hecho de que < F − F >terminó, sabemos que ese flujo es maximal. Y llegamos a demostrar el Teorema de laintegralidad: si las capacidades son enteras entonces existe un flujo maximal entero.

Ejemplo

A

s

t

B

Capacidades:−→AB : 1, las demás: 106

Corremos < F − F >:

1. s,A,B,t : 1

2. s, ←−B,A,t : 1

Luego repetimos los pasos: (1 ↔ 2) 2 ∗ 106 veces, pero vamos a terminar en algúnmomento.

Anexo: recordemos la notación δ (u, v) que referencia la longitud del menor caminoentre u y v .

22


23/111

Lema: sea G un grafo conexo, dirigido o no, sea T = BF S (x) para algún x ∈ V ,entonces:

∀z ∈ V δ (z, x) = N ivelT (z )

Prueba:Como T ⊆ G ⇒ δ G(z, x) ≤ δ T (z, x)

?= NivelT (z )

Para demostrar que vale el “=” lo vamos a hacer por inducción en δ (z, x).

Caso base:δ (z, x) = 0 ⇒ z = x ⇒ N ivelT (z ) = 0 = δ (z, x)

Paso inductivo:

Supongamos que vale para δ (z, x) = k y tomemos un z con δ (z, x) = k+1.

Por lo que vimos al comienzo de la prueba:k + 1 = δ G(z, x) ≤ N ivelT (z )

Si es igual ya está.

Entonces supongamos que NivelT (z ) = j > k + 1Luego δ (z, x) = k + 1 ⇒ ∃ un camino de longitud mínima entre x y z de la forma:

x = x0, x1, . . . , xk, xk+1 = z

Entonces x = x0, x1, . . . , xk es de longitud mínima entre x y xk ⇒ δ (x, xk) = k H.Ind

⇒NivelT (xk) = k

xkz ∈ E NivelT (z ) = j

NivelT (xk) = k

T =BF S (x)⇒ | j − k| ≤ 1Ya que como son vecinos la diferencia de nivel es 0 ó 1.

Pero | j − k| ≤ 1

j > k + 1

⇒ Absurdo.

2.4. Algoritmo de Edmonds Karp

En 1970 Edmonds y Karp dieron 2 “heurísticas”, que de ahora en adelante llamaremos< E − K >.

Consiste en correr < F − F > usando caminos aumentantes de longitud mínima:

< E − K > = < F − F > +BF S

23


24/111

2.4.1. Complejidad de Edmonds-Karp

Teorema: la complejidad17 de < E − K > es O(nm2).Prueba:

Supongamos que < E − K > crea flujos intermedios: O = f 0, f 1, . . .El paso k es el paso que “crea” f kDefino:

dk(x) = “distancia” entre s y x en el paso k.

bk(x) = “distancia” entre x y t en el paso k .

“Distancia”: longitud del menor camino aumentante entre dos vértices.

Lema interno

dk(x) ≤ dk+1(x)

bk(x) ≤ bk+1(x)

Prueba: lo haremos para d ya que para b es similar.

Sea A =

z ∈ V : dk+1(z ) < dk(z )

Queremos ver que A = ∅, supongamos que no y lleguemos a un absurdo.

Si A = ∅ tomamos q ∈ A tal que dk+1(q ) ≤ dk+1(z ) ∀z ∈ A (1)

Como q ∈ A ⇒ dk+1(q ) < dk(q ) (2)Observación: q = s pues dk+1(s) = dk(s) = 0Sea s = x0, x1, . . . , xr−1, xr = q Un camino aumentante de longitud mínima r = dk+1(q ) entre s y q .

(El camino existe pues (2) ⇒ dk+1(q )


25/111

Diremos que un lado (u, v) está “disponible” en un paso j si:

Es Forward con f j−1(→uv) < C (

→uv)

Es Backward con f j−1( →vu) > 0 i.e. →vu ∈ E ¿Está disponible (x, q ) en el paso k?

Supongamos que sí entonces:

dk(q ) ≤ dk(x) + 1(4)

≤ dk+1(x) + 1(3)= dk+1(q )

⇒ Contradice (2) Absurdo!

Por lo tanto xq no está disponible en el paso k , pero sí lo está en el paso k + 1.Entonces lo usamos para el otro lado en el paso k , i.e. (q, x) se usó en el paso k .Como estamos usando < E − K > los caminos aumentantes son de longitud mínima.

∴ dk(x) = dk(q ) + 1 (5)

Entonces: dk+1(q ) (3)= dk+1(x) + 1

(4)

≥ dk(x) + 1(5)= dk(q ) + 1 + 1

= dk(q ) + 2(2)> dk+1(q ) + 2

⇔ 0 > 2 Absurdo!

Fin Lema Interno

Continuando con el teorema, llamemos “crítico” a un lado disponible en un paso y noen el siguiente.

Supongamos que xz se vuelve crítico en el paso k, antes de poder ser crítico otra vezdebe ser usado en la otra dirección, sea L > k el paso donde se usa la próxima vez parael otro lado.

Pues estoy en < E − K > entonces

dk(z ) = dk(x) + 1

dL(x) = dL(z ) + 1 †

dL(t) = dL(x) + bL(x)

= dL(z ) + 1 + bL(x) (7)

≥ dk(z ) + 1 + bk(x) (8)

= dk(x) + 1 + 1 + bk(x) (9)

= dk(t) + 2

25


26/111

∴ dL(t) ≥ dk(t) + 2

( 7) Por †( 8) Por el Lema Interno

( 9) Por Por lo tanto cuando un lado se vuelve crítico recién puede volver a usarse cuando ladistancia a t haya aumentado en por lo menos 2.

# Veces que un lado puede volverse crítico = O(n)

Exactamente sería: n−12Complejidad de cada búsqueda BF S + Aumento = O(m) + O(n) = O(m)En cada aumento al menos un lado se vuelve crítico.Hay m lados y cada uno se vuelve crítico ≤ O(n) veces.

∴ Complejidad(< E − K >) = O(m) ∗ O(m) ∗ O(n) = O(nm2)

Corolario de la complejidad de < E − K >

Siempre existe un flujo maximal.

26


27/111

2.4.2. Ejemplo de Edmonds Karp

Capacidades Caminos

sA:20 Primer Camino: s, A, B,t : 10

sC:20s A C B E F I D K t

s s A A A A C C B20 20 20 3 10 3 10 10 10

AB:20 Segundo Camino: s, A, I, t : 3

AE:3s A C B E F I D K J G H t

s s A A A A C C B E E I10 20 10 3 10 3 10 10 10 3 3 3

AF:10 Tercer Camino: s, C, D, t : 10

AI:3 s A C B E F D K I J G H ts s A A A C C B B E E D7 10 7 3 7 10 10 7 7 3 3 10

Bt:10 Cuarto Camino: s, A, B , I, t : 7

BI:10s A C B E F K I J G H t

s s A A A C B B E E I7 10 7 3 7 10 7 7 3 3 7

BJ:10CD:10 Quinto Camino: s , C, K , I, B , D, t : 2

CK:10

s C K I A B E F J G H t

s C K I − I − A A B E E J10 10 10 3 7 3 3 7 3 3 2

Dt:22

EG:10 Sexto Camino: s, C,K,←−

I, A, E, G , D, t : 3

EH:10s C K I A B E F J G H D t

s C K I − I − A A B E E G D8 8 8 3 5 3 3 5 3 3 3 3

FG:10

GD:3 Séptimo Camino: s,C,K,←−

I, B←−,A,F,

←−G,E,H,D,t : 3

HD:10

s C K I B J A F G E H D t

s C K I − B B− A F G− E H D5 5 5 5 5 5 5 5 3 3 3 3

It:10Jt:2 Octavo Camino?: No llega a t

KI:10s C K I B J A F G

s C K I − B B− A F2 2 2 2 2 2 2 2

27


28/111

Obtengo el Corte: S = {s,c,k,i,b,j,a,f,g}

Capacidad del corte S

Cap(S ) =10 + 10 + 10 + 2 + 3 + 3 = 38cd + it + bt + dt + ae + gd

⇒ V (f ) = Outf (s) −

=0 Inf (s)

= f (−→sa) + f (

−→sc )

= 20 + 18 = 38

2.4.3. Pseudo-Código de Edmonds Karp

1 E−K(Network N)

2 {3 F = 0 ; / / F l u j o4 v = 0 ; // V al or d e l F l uj o5 S = V; / / C o r te 6 while ( t ∈ S ) { // mi en tr as e l v e r t i c e t e s te en e l c o r te 7 / / b u s c a r ca mi no y a u me n ta r 8 Q = new_queue ( S ) ; / / Cr ea r c o l a 9 E [ x ] = ∞ ∀x ∈ V ;

10 S = { s } ; / / c o r t e 11 while ( h e a d ( q ) = t ) {12 x = head ( q ) ;13 Forward_search ( x ) ;14 Backward_search ( x) ;

15 dequeue (q ) ; // s ac o x de l a c o la 16 }17 i f ( t ∈ S ) {18 Aumentar_flujo ( ) ;19 }20 }21 return ( F , v , S ) / / f l u j o , v a l or , c o r t e 22 }2324 F o rw a rd _ se a rc h ( v e r t i c e x )25 {26 f or ( q ∈ Γ+(x) && q ∈ S ) {

27 i f

( f (

−→

xq ) < C (

−→

xq ) ) {28 enqueue (Q, q) ; / / A gr e ga r q a Q 29 S = S ∪ { q } ;30 A[ q ] = x ; / / Ancestro

31 E [ q ] = min{E( x ) ,C(−→

xq ) − F(−→

xq ) } ;32 b [ q ] = 1 ; / / f o r w a r d 33 }34 }35 }36373839

28


29/111

4041 B a ck w ar d_ se ar ch ( v e r t i c e x )42 {43 f or ( q ∈ Γ−(x) && ( q ∈ S ) ) {

44 i f ( f (−→

qx ) > 0) {45 enqueue (Q, q) ; / / A gr e ga r q a Q 46 S = S ∪ { q } ;47 A[ q ] = x ; / / Ancestro48 b [ q ] = −1; //Backward

49 E [ q ] = min{E( x ) ,F(−→

qx ) } ;50 }51 }52 }5354 Aumentar_Flujo ()55 {56 p = t ; / / p i v o t e

57 = E( t ) ;58 v = v + ;59 while ( p = s ) {60 q = a [ p ] ;61 i f ( b [ p ] == 1 ) { / /FORWARD

62 f (−→

qp ) = f (−→

qp ) + ;63 } e l s e {

64 f (−→

pq ) = f (−→

pq ) − ;65 }66 p = q ;67 }68 }

2.5. Algoritmos Tipo Dinic

Idea: usar un network auxiliar que se construye de la siguiente manera: corremosBFS de caminos aumentantes, como en < E − K >, agregando los vértices y ladoscorrespondientes excepto que en < E − K > cuando p encuentra un q que ya está, no loagrega, mientras que acá a veces sí, i.e. supongamos que estamos revisando p y hallamosq ∈ Γ+( p) con f (

→ pq ) < C (

→ pq ) ó q ∈ Γ−( p) : f (

→qp) > 0, pero que q ya está en el network

auxiliar, entonces agregamos un lado pq al network auxiliar si el N ivel(q ) = N ivel( p) + 1.Definición: un flujo G se dice bloqueante o saturante si para todo camino:

s = x0, x1, . . . , xr = t con ( −→

xixi+1) ∈ E ∃i : G( −→

xixi+1) = C ( −→

xixi+1)

Dado f flujo en N y g flujo en un network auxiliar denotemos por:

(f ⊕ g)(x, y) =

f (x, y) + g(x, y) Forwardf (x, y) − g(y, x) Backward

29


30/111

2.5.1. Esquema general Tipo Dinic

1 D i n i c ( )2 {

3 f = 0 ;4 S to p = NO;5 while (Stop == NO){6 NA = New_Na( f ) ; // c o n s t ru i r Network a u x i l i a r a p a r t i r de f 7 i f ( t ∈ NA) {8 g = H al la r_ bl oq ue an te (NA) ; / / bu sc o u n f l u j o b l o qu e a n te en NA9 f = f ⊕ g ;

10 } e l s e {11 Stop = Sí ;12 }13 }14 return f ;15 }

Teorema

La distancia en NA18 sucesivos aumenta, por lo tanto hay a lo sumo n, NA’s.Demostración:Sea A un NA y A el siguiente NA, denotamos con δ la distancia en A y δ la distancia

en A.Como A y A se construyen con BFS ⇒ δ ≤ δ

Queremos ver que vale el “

∴ δ (t) < δ (t)

Caso 2: xi ∈ A ∀i

Como antes de pasar a A debemos saturar todos los caminos de A, se sigue queningún camino de A es un camino de A.

Luego: s, x1, . . . , xr−1, t no es camino en A, como xi ∈ A ∀i ⇒ ∃i : →

xixi+1 ∈ A

Y tomemos el primer tal i.

18NA: networks auxiliares.

30


31/111

• Caso 2-a: δ (xi+1) < i + 1

Como i + 1 = δ (xi+1) ⇒ δ (xi+1) < δ (xi+1)

Luego:

δ (t) = δ (xi+1) + b(xi+1)

< δ (xi+1) + b(xi+1) (12)

≤ δ (xi+1) + b(xi+1) (13)

= δ (t)

( 12) Por

( 13) Por < E − K >

• Caso 2-b: δ (xi+1) = i + 1

Observación: es ≤ por < E − K > no hace falta ver “ >”.Como i es el primero con −→xixi+1 ∈ A ⇒

−→x j−1x j ∈ A ∀ j ≤ i

∴ s = x0, x1, . . . , xi ∈ A

∴ δ (xi) = i ⇒ δ (xi+1) = i + 1 = δ (xi) + 1

Como los niveles son los “correctos” la única razón por la cual xixi+1 ∈ A esporque no está “disponible” en N , i.e. es Forward saturado o Backward vacío.

Pero −→xixi+1 ∈ A

entonces se usó para el otro lado en A, es decir: −→xi+1xi ∈ A Absurdo

pues Nivel(xi+1) = i + 1, y N ivel(xi) = i.

Corolario: si un algoritmo tiene complejidad O(b) para hallar flujo bloqueante en elNA, entonces la complejidad del algoritmo completo es O(n ∗ b).

Dinic = Algoritmo tipo Dinic + Greedy “DFS” para hallar flujo bloqueante.A simple vista sería: Complejidad(Dinic) = O(nm2) = Complejidad(< E − K >)Parecería que no ganamos nada.Pero veremos que en realidad Complejidad(Greedy en NA) = O(nm).∴ Tendremos Complejidad(Dinic) = O(n2m)

31


32/111

2.5.2. Ejemplo de Dinic

Ejemplo: Aplicar Dinic al siguiente Network.

Inicial Primera Modificación caminos (4) Segunda Modificación (final) Caminos (6)sA:8 sA:0 sAFt:4 sA:0 sD

←−

FAIt : 1

sC:7 sC:0 sAGt:3 sC:0 sD←−

GAIt : 2

sD:10 sD:7 sAIt:1 sD:4 sE←−

FAIt : 3

sE:12 sE:11 sCGt:2 sE:1 sE←−

GAIt : 1

AF:4 AF:0 sCHt:3 AF:4 sEGBIt : 1AG:3 AG:0 sCJt:2 AG:3 SEGBJt : 2

AI:8 AI:7 sDFt:3 AI:0 SE←−

GCJt : 1

BI:2 BI:2 sEHt:1 BI:1 sE←−

HCJt : 2BJ:2 BJ:2 BJ:2CG:2 CG:0 CG:1CH:3 CH:0 CH:2CJ:5 CJ:3 CJ:0DF:4 DF:1 DF:0DG:2 DG:2 DG:0EF:3 EF:3 EF:0EG:5 EG:5 EG:0EH:4 EH:3 EH:1Ft:7 Ft:0 Ft:0Gt:5 Gt:0 Gt:0GB:4 GB:4 GB:1Ht:4 Ht:0 Ht:0It:9 It:8 It:0

Jt:15 Jt:13 Jt:8

Primer Network Auxiliar Segundo Network auxiliar

I

A

G

s

C

F

t

D

H

E

J

D

F (−)

A I

s

G

(−)

(−)

B

t

E

H

(−)

C

J

Tercer Network auxiliar

s

D

E H (−)

C G B I (−)

A F

Obtengo el corte del conjunto de vértices del NA que no llega a t, el último.

S = {s,d,e,h,c,g,b,i,a,f }

Cap(S ) = 4+ 5+ 5+ 2 + 9+ 7 = 32ht+ cj+ gt+ bj + it+ f t

32


33/111

Se ve que C ap(S ) = 32 = Outf (s)

Entonces tengo una garantía de la resolución del ejercicio.Otra garantía es ver que los caminos obtenidos de un NA tengan el mismo tamaño y

que a medida que voy construyendo otros NA’s sean más largos, en este caso los primerostenían 4 de largo y los caminos del segundo network auxiliar tenian un largo de 6.

2.5.3. Pseudo Código algoritmos Tipo Dinic

1 Dini c ( Net work Na) { / / P a r te B l oq u e an t e , V e rs i on c on G ot o2 g = 0 ;

3 2 p = s ; / / l a b e l 2 , p i vo t e

4 1 i f ( p = t ) { / / l a b e l 15 i f ( Γ+( p) = ∅ ) {6 avanzar ( ) ;

7 goto 1 ;8 } e ls e i f ( p = s ) {9 r e t r o c e d e r ( ) ;

10 goto 1 ;11 } e l s e r et ur n g ;12 } e l s e {13 I nc re me nt ar _f l uj o ( ) ;14 goto 2 ;15 }16 }1718 D i n i c ( N et wo rk Na ) { \ \ P a r te B l o qu e an t e , V e r s i on goto l e s s ;19 g = 0 ;

20 E( s ) = ∞ ;21 c on ti nu ar = 1 ;22 while ( c o n t i n u a r ) {23 p = s ;24 while ( p = t && cont inu ar ) {25 i f ( Γ+( p) = ∅ ) {26 Avanzar ( ) ;27 } e ls e i f ( p = s ) {28 R e t r o c e d e r ( ) ;29 } e l s e {30 c o n t i n u a r = 0 ;31 }32 }33 i f (p == t ){34 I nc re me n ta r_ fl uj o ( ) ;35 }36 }37 Return g38 }394041424344

33


34/111

4546 // Pre p t i e n e v e ci n o47 A v an za r ( p i v o t e p ) {48 Tomar q ∈ Γ+( p)

49 A( q) = p ; // a n ce st r o de q e s p50 E ( q ) = min {E ( p ) ,C (

−→

pq )−G(−→

pq ) } ;51 p = q ;52 }5354 // Pre p t i e n e v e ci n o55 R e t r o c e d e r ( p i v o t e p )56 {57 Bo rrar p de Γ+(A( p))58 p = A( q) ;59 }6061 I ncrement ar_Flujo ( )

62 {63 = E( t ) ;64 q = t ;65 while ( q = s ) {66 p = a ( q ) ;

67 G(−→

pq ) = G(−→

pq ) + ;

68 i f (G(−→

pq ) == C (−→

pq ) ) {69 Bo rrar q de Γ+( p)70 }71 }72 q = p ;73 }

34


35/111

2.5.4. Complejidad de Dinic

Teorema: la complejidad de Dinic es O(n2m)Prueba: por el teorema general de los algoritmos “tipo Dinic” basta ver que la com-

plejidad del paso bloqueante es O(n ∗ m).Sea:

A = Avanzar()

R = Retroceder()

I = Incrementar_Flujo() + Inicialización (O(1))

Una corrida de Dinic luce como:

A . . . AIA. . . ARAIA. . . ARAI . . . RRRRA . . . AI

Sea X = I ó R.Tomemos una sucesión de palabras de la forma: A . . . AX

1. ¿Cuántas palabras hay?

Si X = R: borramos un lado.

Si X = I : borramos al menos un lado.

∴ Cada X borra al menos un lado ⇒ hay ≤ m palabras de la forma A . . . AX

2. ¿Cuál es la complejidad máxima de cada palabra?

Complejidad de R = O(1)Complejidad de I = O(n); hay ≤ n vértices en el camino s, . . . , t.

∴ Complejidad(X ) = O(n)

Complejidad de A = O(1)

∴ Complejidad(A . . . A r

X ) = O(r) + O(n)

Como cada Avanzar() mueve el pivote un nivel más cerca de t entonces hay a lo sumon Avanzar() antes de un R o un I ∴ r ≤ n.

Complejidad(A . . . A X ) = O(n) + O(n) = O(n)

(1) + (2) ⇒ Complejidad(Paso Bloqueante de Dinic) = m ∗ O(n) = O(n ∗ m)

35


36/111

2.6. Algoritmo Wave de Tarjan

Es un ejemplo de una clase de algoritmos en los cuales la invariante no es más “serflujo”.

Definición: un Preflujo es como un flujo sin la condición de balanceo.En el caso de Wave19 el desbalanceo sólo podrá ser por exceso de entrada, pero otros

algoritmos permiten desbalanceo de los dos lados.Idea: una ola hacia adelante (“Forward”) que balancea si puede y marca (“bloquea”) si

no.Una ola hacia atrás que balancea los bloqueados (“Backward”).

2.6.1. Pseudo Código de Wave

1 Wave(){2 i n i c i a l i z a r ( ) ;

3 o la Fo rw ar d ( ) ;4 o la Ba ck wa rd ( ) ;5 while (N ! = 2 ) {6 olaForward ( ) ;7 olaBackward ( ) ;8 }9 return g ;

10 }1112 i n i c i a l i z a r ( ) {13 g = 0 ;14 ∀(x = s){15 B( x ) = 0 ; / / No b l o q u e a d o

16 D( x ) = 0 / / D esba la nceo17 A( x ) = ∅ // s u bc o nj u nt o de a q u e l l o s q ue l e mandaron f l u j o a x 18 }1920 D( s ) = 0 ;21 N = 1 ; / / #V e r t i c e s b a l a n c e a d o s 2223 ∀(x ∈ Γ+(s)){

24 G(−→

sx ) = C (−→

sx ) ;

25 D( s ) = D( s ) − C(−→

sx ) ;

26 D( x ) = C(−→

sx ) ;27 N++;

28 A( x ) = { s } ;29 }30 }3132 olaForward ()33 {34 f or ( x = s +1; To ; t −1) { //Orden BFS( )35 i f (D(x)>0)36 ForwardBalance ( x) ;37 }38 }

19Wave: inglés, ola.

36


37/111

3940 olaBackward ()41 {42 f or ( x = t − 1 DownTo s +1){ //Orden BFS( )

43 i f (D(x)>0 && B(x) == 1)44 BackwardBalance ( x) ;45 }46 }4748 B a ck w ar d Ba l an c e ( v e r t i c e x ) {49 while (D(x)>0){50 Tomar y ∈ A(x ) ;

51 m = min {D( x ) ,G(−→

yx ) } ;

52 g (−→

yx ) = g (−→

yx ) − m;53 D( x ) = D( x ) − m;54 i f (D( y) == 0) {55 N++;

56 }57 D( y) = D( y) + m;

58 i f (G(−→

yx ) == 0) {59 A( x ) = A( x ) − { y } ;60 }61 }62 N−−;63 }646566 F o r w ar d Ba l an c e ( v e r t i c e x ) {67 while (D(x)>0 && (Γ+(x) = ∅)) {

68 Tomar y ∈ Γ+

(x) ;69 i f ( B( y ) == 1 ) {70 Γ+(x) = Γ+(x) − {y}71 } e l s e {

72 m = min{D( x) ,C(−→

xy ) − G(−→

xy ) }

73 G(−→

xy ) = G(−→

xy ) + m ;74 D( x ) = D( x ) − m;75 i f ( D( y ) == 0) {76 N++;77 }78 D( y ) = D( y ) + m;79 A( y ) = A( y ) ∪ { x } ;

80 i f (G(−→

xy ) == C(−→

xy ) ) {

81 Γ+(x) = Γ+(x) − {y}82 }83 }84 }85 i f (D(x)>0)86 B( x ) = 1 ; / / Blo quea mos x 87 e l s e88 N−−;89 }

37


38/111

2.6.2. Complejidad de Wave

Teorema: la complejidad de Wave es O(n3)Prueba: como es “Tipo Dinic” sólo basta ver que la complejidad del paso bloqueante

es O(n2).Sea ()t partes del algoritmo en donde se satura totalmente un lado o se vacía totalmente

un lado.Y sea () p donde se manda o devuelve parcialmente flujo.

Compl(Wave_bloqueante) = Compl(Wave_bloqueante)t + Compl(Wave_bloqueante) p

Analicemos primero la Compl(Wave_bloqueante) p .

Cada ola Forward, salvo quizás la última bloquea al menos un vértice nuevo.

∴ Hay a lo sumo n ciclos: (ola forward,ola backward) En cada ola forward hay n − 2, ForwardBalance(x)

Entonces:

Compl(olaForward) p = n ∗ Compl(ForwardBalance(x)) p

= n ∗ Compl(ForwardBalance(x)) p O(1)

(14)

= O(n)

( 14) Pues en cada F B(x) a sólo un lado le mandamos flujo parcial.

Compl(ola F orward) p = O(n) (2)

Luego:(2) y ⇒ Compl(Wave_bloqueante) p = O(n2)

Ahora analicemos Compl(Wave_bloqueante)t.

Cada vez que un lado se satura completamente no puede volver a saturarse, pues si

el lado es →xy lo quisiera volver a saturar debería primero hacer que “ y” le devuelva

el flujo a “x”.Pero esto sólo puede pasar si “ y” está bloqueado y en ese caso “x” no le puedemandar más flujo, en particular no lo puede volver a saturar.

Similarmente, un lado →xy sólo se puede vaciar totalmente una vez porque sólo puede

hacerlo si “y” está bloqueado.

∴ #Saturamientos + #V aciamientos ≤ 2m

∴ Compl(Wave_bloqueante)t = O(m)

38


39/111


40/111

Aplicar Wave Respetando el orden alfabético y observar que el flujo es distinto

sA:8 → 0sC:7 → 0sD:10 → 5sE:7 → 0AF:4AG:3AI:8 → 0CG:2CH:3 → 0CJ:5 → 1DF:4 → 0DG:2 → 1

EF:3 → 0EG:5 → 1EH:4Ft:7 → 0Gt:5 → 0Ht:4 → 0It:9 → 1Jt:15 → 11

Nivel 0 Nivel 1 Nivel 2 Nivel 3

s A C D E F G I H J t-32 8 7 10 7 4 3 1 3 2 7

4 5 6 4 8 5 0 0 0 121 2

4 0 11 7 13

0 0 4 11 16→

6 18

-27 3 2 5 0 3 7 2 25

7 0 0 1 0 0 270 0 ←

Importante ver que termino porque Outf (s) = I nf (t)

40


41/111

3. MST

MST: minimal spanning tree, árbol de expansión o generador minimal.Definición: sea G un grafo, un árbol generador de G es un subgrafo de G que es

árbol y generador.Es decir T es árbol generador de G si:

1. T subgrafo de G.

2. T árbol ⇒ Conexo sin ciclos.

3. T generador ⇒ V (T ) = V (G).

Obviamente si G tiene árbol generador debe ser G conexo si lo es DFS o BFS dan unárbol generador.

Repaso de árboles

Propiedad: T árbol ⇒ m = n − 1Demostración: si T es árbol, entonces DF S (T ) = T .Si A(q ) denota el antecesor de q en DFS, todos los lados de DFS son de la forma:

A(q )q para algún q = raíz.

∴ Hay n − 1 lados. (uno por cada vértice = raíz)

Propiedad:

(1) T árbol ⇔ T conexo y m = n − 1 (2)

⇔ T no tiene ciclos y m = n − 1 (3)

Prueba:

(1) ⇒

(2) y (3)

ya está.

(3) ⇒ (1) : T no tiene ciclos y m = n − 1 ?⇒ T árbol

Sólo tengo que ver que es conexo.Sean {x, y} ∈ T , supongamos que no hay un camino entre x e y .

En particular xy ∈ E (T )Sea T = T ∪ {xy}Como no hay caminos en T entre x e y en T no hay ciclos.

Si C fuese ciclo

Como T es acíclico ⇒ xy ∈ T

Entonces C − xy , es un camino en T entre x e y absurdo.

41


42/111

Conclusión: si x, y no tiene un camino entre ellos, T ∪ {x, y} sigue siendo acíclico.Continuando de esta forma terminamos con un

T conexo y acíclico.

Es decir árbol tal que T ∪ {xy} ⊆

T

E T = V T − 1 (15)= |V (T )| − 1

= |E (T )| (16)

( 15) T es árbol( 16) Por HIP.(3)

Absurdo pues T ∪ {x, y} ⊆ T ⇒ E T

≥ |E (T )| + 1

(2) ⇒ (1) : T conexo y m = n − 1 ?⇒ T árbol

Sólo tengo que ver que no contenga ciclos.Supongamos que T tenga un ciclo, borrando el lado del ciclo, el grafo resultante sigue

siendo conexo.Por lo tanto puedo ir borrando un lado de cada ciclo manteniendo continuidad.Eventualmente llegamos a un grafo H sin ciclos que sigue siendo conexo.∴ H es árbol. E (H ) = V (H )− 1 = V (T )− 1 = E (T )Absurdo porque por lo menos quité un lado.

Definición: dado un grafo G conexo con pesos en los lados, es decir W : E (G) → R≥0.Un MST20 para G es un spanning tree T tal que:

xy∈E (T )W (xy) ≤

xy∈E (T )

W (xy) ∀spanning Tree T

Notaciónxy∈E (T )

W (xy) = W (T ).

Problema: dado G conexo, hallar un MST para G.

3.1. Kruskal

Repetir hasta tener n − 1 lados, agregar el lado de menor peso que no forme ciclo.Se necesita una estructura de datos de “conjuntos disjuntos”.

1. Makeset(x): construye un conjunto {x}.

2. Find(x): devuelve el conjunto al cual pertenece x.

3. Union(A, B): devuelve la unión de A y B.

20Minimal Spanning Tree.

42


43/111

3.1.1. Pseudo Código de Kruskal

1 K r u s k al ( )2 {

3 // α4 ∀(x ∈ V ){5 Makeset ( x ) ;6 }78 // β 9 E dg es _S or t ( ) ; / / Or de na r l o s l a d o s : W( E[ i ] ) ≤ W(E[ i +1])

10 m = 0 ; // c a n t i d ad d e l a d o s 11 i = 1 ; // i n d i c e 1213 // γ 1415 while (M < N−1) {

16 A = f in d ( x [ i ] ) ;17 B = f in d ( y [ i ] ) ;18 i f (A = B) {19 t re e . add ( e [ i ] ) ; // a g r e g ar a l a r b o l e [ i ] 20 m++;21 Union (A, B) ;22 }23 i ++;24 }252627 }

3.1.2. Teorema: Kruskal devuelve un MST

Demostración: el invariante es ser acíclico y termina con n − 1 lados, entonces tenemosgarantizado que termina con un spanning tree.

Veamos ahora que es minimal.

Prueba por inducción: sea K j el grafo en el paso j

Si j = 0 queda demostrado porque los vértices desconectados siempre están.

Hipótesis inductiva: ∀ j ∃ un MST T j : K j ⊆ T j

Supongamos que K j ⊆ T j MST.

Sea e : K j+1 = K j ∪ {e}

• Si e ∈ T j ya está pues K j+1 ⊆ T j• Por lo tanto supongamos: e ∈ T j

En este caso, T j ∪ {e} tiene: n − 1 + 1 = n lados ∴ no es árbol.Como T j es conexo ⇒ T j ∪ {e} es conexo.Como no es árbol ⇒ T j ∪ {e} tiene un ciclo C .Pero T j no tiene ciclos ⇒ e forma parte del ciclo C .

43


44/111

Sea f un lado de C que no esté en K j+1 (∃f ⇐ K j+1 es acíclico).

T j+1 = (T j − f ) ∪ {e}

= (T j ∪ {e}) − f

Como C es un ciclo: y f ∈ C ⇒ (T j ∪ {e}) − f sigue siendo conexo.

∴ T j+1 es conexo y tiene: n − 1 + 1 − 1 = n − 1 lados ⇒ T j+1 es un árbol.

Como K j+1 ⊆ T j+1 basta ver que T j+1 es minimal.

Pero W (T j+1) = W (T j ) − W (f ) + W (e)

Pero f ∈ K j+1Si W (f ) < W (e) ⇒ f se “analizó” antes de e.

Como f ∈ K j+1 entonces se rechazó.

Entonces K j ∪ {f } tiene un ciclo absurdo pues K j ∪ {f } ⊆ T j árbol

Ya que

K j ⊆ T j y f ∈ T j

(estoy diciendo que un subconjunto de un árbol tiene un ciclo, absurdo).

∴ W (f ) ≥ W (e)

W (T j+1) ≤ W (T j)Como T j es MST

⇒ T j+1 también.

3.1.3. Complejidad de Kruskal

Volviendo al pseudocódigo:

α = O(n)

β = O(m log(m)) = O(m log(n2)) = O(2m log(n)) = O(m log(n))

γ = n ∗ (2 ∗ Compl(Find) + Compl(Union))

Como en general β > γ

∴ Compl(Kruskal) = O(m log(n))

3.1.4. Kruskal Delete

Repetir() hasta tener n − 1 lados.() Borrar el lado de mayor peso que no desconecte el grafo.

3.1.5. Complejidad Kruskal Delete

No demostraremos el orden pero diremos que la complejidad es: O

m log(n) (log (log(n)))3

44


45/111

3.1.6. Ejemplo de Kruskal

A B C D E F A − 5 − 3 1 3

B 5 − 1 4 − −C − 1 − 7 − −D 3 4 7 − 4 2E 1 − − 4 − 3F 3 − − 2 3 −

(0) A C E

B D F (1) A

1

C B

E D F (2) A

1

B

1

D

E C F

(3) A

1

B

1

D

2

E C F (4) A

3

1 E B

1

F 2 D C

(5) A

3

1 E B

1

F 1 D

4

C

F 3

3

2

A 1

5 3

E

4

B

1

4

D

7

C

45


46/111

3.2. PRIM

Prim(x) = agregar el lado de menor peso que conecte x con otro vértice, creando unaregión R luego ir agregando el lado de menor peso que conecte R con V − R.

Generalmente se implementa con un heap.

3.2.1. Pseudo Código de Prim

1 P rim ( v e r t i c e x )2 {3 ∀( p ∈ V ){4 Costo [ p ] = ∞ ;5 V eci no [ p ] = NULL ;6 }78 Costo ( x) = 0 ;

9 M = 0 ;10 Aux = V ;1112 //FALTA CASO BASE 1314 while (m < n−1) {15 // p r e : c o s t o ( p )< c o s t o ( q ) ∀q ∈ Aux16 ∀(q ∈ Γ( p)){17 i f ( cos t o ( q )> V( pq) ) {18 c o s t o ( q ) = W( pq ) ;19 v e c i n o ( q ) = p ;20 }21 }

22 Add (p , v e ci n o ( p ) ) ;23 m++;24 }252627 }

3.2.2. Correctitud de Prim

Como el invariante es ser árbol cuanto termina es efectivamente spanning tree.Sólo resta ver que es minimal y lo haremos por inducción.

Si P j es el árbol en el paso j , probaremos que ∃ MST T j : P j ⊆ T j

j = 0: Trivial.

Supongamos que vale para j

Si P j+1 ⊆ T j ya está.

De lo contrario existe e ∈ P j+1 : e ∈ T j (y de hecho, será P j+1 = P j ∪ {e} ).

e une P j con V − P j

Como T j es Spanning Tree ⇒ debe conectar P j con V − P j .

46


47/111

Sea f un lado en T j que conecte estas dos regiones.

Como e es el menor lado que conecta esas dos regiones tenemos que:

W (e) ≤ W (f )

Entonces: W (T j ∪ {e} − f ) ≤ W (T j)

∴ T j ∪ {e} − f es un MST que contiene a P j+1.

3.2.3. Ejemplo de Prim

A B C D E F A − 5 − 3 1 3B 5 − 1 4 − −C − 1 − 7 − −D 3 4 7 − 4 2E 1 − − 4 − 3F 3 − − 2 3 −

Prim(A), Método Gráfico:

(1) A 1 E (2) A

3

1 E

D

(3) A

3

1 E

D 2 F

(4) A

3

1 E

D 2

4

F

B

(5) A

3

1 E

D 2

4

F

B 1 C

Prim(A), Método Analítico;

B C D E F

1) (5, A) (∞, −) (3, A) (1,A) (3, A)

2) (5, A) (∞, −) (3,A) − (3, A)

3) (4, D) (7, D) − − (2,D)

4) (4,D) (7, D) − − −

5) − (1,B) − − −

∴ Complejidad(Prim) = O(n2)

47


48/111

3.3. Implementaciones de Union Find

1. Linked lists. (listas enlazadas)

2. Representantes.3. Union Find By Rank.

3.3.1. Union Find con listas enlazadas

Union es O(1)Find es O(n)Recordemos que Kruskal hace: 2m “Finds()” y n − 1 “Unions()”.

∴ O(mn) + O(n) = O(nm)

Como mn > m log(n) Ordenar los lados

no sirve.

3.3.2. Union Find con Representantes

12 M a k e s e t ( x ) { //O(1)3 R( x ) = x ;4 }56 F i n d ( x ) { / / O(1 )7 return R(x) ;8 }9

10 Union( R1, R2 ) { / / O(n)11 ∀(x ∈ V ){12 i f (R(x) == R2 ) {13 R( x ) = R1 ;14 }15 }16 }

Compl(Kruskal) = O(m log(n)) Ordenar los lados + O(m) m Finds + O(n2) n Unions

∴ Compl(Kruskal) = O(m log(n) + n2) bastante bien si: m ≈ n2

Es decir no funciona tan bien si es un grafo ralo, i.e. con pocos lados.

48


49/111

3.3.3. Union Find con ranking

1 M ak es et ( v e r t i c e x ) {2 Π(x) = x ;

3 Rk( x) = 0 ; //Ranking 4 }5 F in d ( v e r t i c e x ) { // r e c u rs i vo a l a c o la 6 i f ( Π(x) == x)7 return x ;8 e l s e re tu rn f i n d ( Π(x))9 }

10 F in d ( v e r t i c e x ) { // i t e r a t i v o11 y = x ;12 while ( y = Π(y) )13 y = Π(y) ;14 return y ;15 }

16 / ∗ Pre : F 1 = F in d ( x [ 1 ] ) ; F 2 = F in d ( x [ 2 ] ) ; F 1 = F 2 ∗/ 17 Union( F 1, F 2 ) {18 k1 = Rank( F 1 ) ;19 k2 = Rank( F 2 ) ;20 i f ( K 1 > K 2 ) {21 Π(F 2) = F 1 ; // c a b ez a d e l 2 do a pu nt a a l p ri me ro22 } e l s e {23 Π(F 1) = F 2 ; / / c ab e z a d e l p ri me ro a pu nt a a l s eg un do24 i f ( k1 == k2 ) {25 Rank ( F 2 ) = k2 +1 ;26 }27 }28 }

Con esta implementación:makeset(x) = (1)

Union = O(1);

Find(x) = O(rank(representante(x)) ≤ O(log(n))

Teorema Find es O(log(n))

Corolario: Compl(Kruskal) = O(m log(n))Demostración:

Compl(Kruskal) = O(m log(n)) Ordenar los lados

+ O(m) m Finds

+ O(n2) n Unions

= O(m log(n))

Demostración del Teorema

Lema interno 1: (Rank(x) < Rank(Π(x)) : ∀x : x = Π(x))

Obvio pues Rank solo cambia con Union, y lo cambia sólo a F 2 cuando Π(F 1) == F 2

En ese caso incrementa el rango de F 2

49


50/111

Lema interno 2: Rank(x) = k ⇒ ∃ ≥ 2k elementos “por debajo” de x, contando ax.

Prueba por inducción.

• k = 0 obvio

• Supongo que vale para k

• Veamos para k + 1

Rank(x) = k + 1 ⇒ alguna vez fue k y union lo subió a k + 1 y esto sólo pasasi unimos 2 de rango k .

Entonces la cantidad de elementos por debajo de x ≥ 2k + 2k = 2k+1

Lema interno 3: Hay ≤ n2k elementos de rango k, está demostrado en los lemas.

Finalmente Rango(x) ≤ log(n) ∀x

Pues sea k el mayor rango ⇒ ∃ por lo menos un elemento de rango k .

⇒ 1 ≤ n2k

⇒ 2k ≤ n

∴ k ≤ log2(n).

¿Qué pasa si los lados vienen ordenados o se pueden ordenar21 en O(m)?

Se puede usar “Path compresion”Solo cambia Find

1 F i n d ( x ) {2 i f ( Π(x) = x ) {3 Π(x) = F in d ( Π(x)) ;4 }5 return Π(x) ;6 }

El análisis es más complicado, cada F ind() puede ser O(log(n))Se puede ver:

Teorema: la complejidad de m Finds + n Unions, está acotado por O

m log∗(n)Esencialmente: O(m) ∀n “razonable”.O log∗(n) = # de veces que hay que aplicar log para llegar a algo ≤ 1

n 1 2 {3,4} {5,. . . ,16} {17,. . . ,216} {216+1,...,265536}log(n) 0 1 2 3 4 5

21Bucket sort.

50


51/111

4. Matchings

Dado un grafo G, un matching en G es un subgrafo M tal que el grado en M de todossus vértices es 1.

Un matching es perfecto si “cubre” a G, es decir: V (M ) = V (G).De ahora en más supondremos que G es bipartito.Cuando escribamos G = (X ∪ Y, E ) asumimos que X e Y son las partes.

Es decir: pq ∈ E ⇒ p ∈ X, q ∈ Y

Problema: hallar un matching perfecto en G, o en su defecto uno “maximal” (con lamayor cantidad de lados posibles).

4.1. Transformación del problema de Matching a uno de flujo

maximal

Dado G = (X ∪ Y, E ) creamos el siguiente network.

N =

X ∪ Y ∪ {s, t},→E, C

→E =

−→sx

x∈X

−→xy : x ∈ X y ∈ Y xy ∈ E

−→yty∈Y La capacidad de todos los lados es : 1.

Ejemplo

X A

B

C

Y 1 2

3

⇒

s

A

B

C

1 2

3

t

Teorema

Flujos maximales en N corresponden con matchings maximales en G y V (f max) = #lados.Dicho de otra manera: existe una correspondencia entre matchings maximales en G(bipartito) y flujos maximales enteros en N.

Prueba: dado un flujo entero f construimos un matching M f y dado un Matching M construimos un flujo entero f M .

Dado f sea M f = (V f , E f ) :V f =

xy∈E f

{x, y}

E f = {xy ∈ E : f (−→xy) = 1}

Hay que ver que M f es matching.

51


52/111

Observemos que por definición de V f tenemos que δ M f (z ) ≥ 1 ∀z ∈ V f

Si M f no es matching ⇒ ∃z : δ M f (z ) ≥ 2

Caso 1: z ∈ X como δ M f (z ) ≥ 2 entonces ∃y1, y2 : y1 = y2

zy1, zy2 ∈ E f

Entonces f (−→zy1) = f (

−→zy2) = 1

∴ Outf (z ) ≥ 2

Pero I nf (z ) = f (−→sz ) ≤ 1

⇒ Absurdo.

Caso 2: z ∈ Y ⇒ ∃x1, x2 : x1 = x2

x1z, x2z ∈ E f

Entonces f (−→x1z ) = f (−→x2z ) = 1

∴ I nf (z ) ≥ 2

Pero Outf (z ) = f (−→zt ) ≤ 1

⇒ Absurdo

Concluimos que M f es matching.

Dado ahora un Matching M sea f M definido así:

f M (−→xy) = 1 Si xy ∈ E (M )0 Si nof M (

−→sx) =

1 Si x ∈ V (M ) ∩ X 0 Si no

f M (−→yt ) =

1 Si y ∈ V (M ) ∩ Y 0 Si no

Como M es matching, está claro que:

M f (z ) = Outf (z ) = 1 Si z ∈ V (M )0 Si z ∈ V (M )Además está claro que: M f M = M y que: f M f = f

52


53/111

Veamos ahora que: V (f ) = |E M f |

V (f ) = Outf (s) −

=0

Inf (s)= x∈X

f (−→sx)

= #{x : f (−→sx) = 1}

= #{x : I nf (x) = 1}

= #{x : Outf (x) = 1} por ser f un flujo

= |V f ∩ X |

= |E M f |

Por lo tanto flujos maximales enteros corresponden a matchings maximales.

Definición: Sea S ⊆ V ⇒ Γ(S ) =

z∈S Γ(z ) = {w ∈ V : ∃z ∈ S : wz ∈ E }

Definición: Si G = (X ∪ Y, E ) es bipartito, un matching se dice completo de X a Y si cubre a X, i.e. X ⊆ V (M ).

4.2. Teorema de Hall

Sea G = (X ∪ Y, E ) bipartito entonces:∃ un matching completo de X a Y ⇔ : Γ(S ) ≥ S ∀S ⊆ X

4.3. Complejidad del Algoritmo de Matching

Asumiendo |X | = |Y | = n

Matching inical: O(n2).

Extender el matching en un lado: O(n2).

Extenderlo O(n) veces.

∴ Nos queda: O(n3

)

4.4. Grafos con Peso

Sea G = (X ∪ Y, E ) grafo bipartito, con |X | = |Y | = n y sea C una matriz de costosn ∗ n

C x,y = Costo de asignar el trabajo X al trabajador Y.22

Hay 2 (al menos) formas de minimizar:

1. Minimizar el máximo.22A veces pueden ser “Ganancias”.

53


54/111

2. Mimizar la suma.

El problema 1 a veces es llamado el: bottleneck problem23, se resuelve con el algoritmode “Gross” y es bastante simple.

4.4.1. Algoritmo de “Gross”

Dado C :

1. Ordenar los C i,j como : b1 < b2 < . . . < bk (k ≤ n2)

2. Tomar, para r= 1, ..., k:

(Ar)i,j =

1 Si C i,j ≤ br0 Si no

(r es el “umbral”)

3. Hallar r: Ar tenga Matching perfecto y Ar−1 no, eso da un matching M tal que:

máx{C i,j : {i, j} ∈ E (M )} ≤ máx{C i,j : {i, j} ∈ E (M )} ∀M

23Problema de cuello de botella.

54


55/111

4.4.2. Ejemplo del algoritmo de “Gross”

Hallar un Matching que minimice el MáximoI II III IV V VI VII

A 1 2 15 2 7 5 4B π e e2 5 8 2 1C 9 2 1 10 8 100 9D e2 1 2 10 4 10 10E 10 9 7 8 1 9 10F 1 2 3 4 5 6 7G 8 2 9 10 5 10 10

Ordeno los C i,j: 1, 2, e, 3, π, 4, 5, 6, 7, e2, 8, 9, 10, 15, 1000

máx{ḿın(filas); mı́n(columnas)} = máx{1, 1, 1, 1, 1, 1, 2; 1, 1, 1, 2, 1, 2, 1} = 2

Umbral 7Busco Matching Intento extenderlo

I II III IV V VI VIIA 1 1 0 1 1 1 1B 1 1 0 1 0 1 1C 0 1 1 0 0 0 0D 0 1 1 0 1 0 0E 0 0 1 0 1 0 0 F 1 1 1 1 1 1 1

G 0 1 0 0 1 0 0

I II III IV V VI VIIA 1 1 0 1 1 1 1B 1 1 0 1 0 1 1C 0 1 1 0 0 0 0D 0 1 1 0 1 0 0E 0 0 1 0 1 0 0 F 1 1 1 1 1 1 1G 0 1 0 0 1 0 0

G E EI II III IV V VI VII

A 1 1 0 1 1 1 1B 1 1 0 1 0 1 1 IIC 0 1 1 0 0 0 0 IIID 0 1 1 0 1 0 0 VE 0 0 1 0 1 0 0 F 1 1 1 1 1 1 1G 0 1 0 0 1 0 0

G E E

I II III IV V VI VIIA 1 1 0 1 1 1 1B 1 1 0 1 0 1 1 II C 0 1 1 0 0 0 0 III D 0 1 1 0 1 0 0 V E 0 0 1 0 1 0 0 F 1 1 1 1 1 1 1G 0 1 0 0 1 0 0

B G E B E B B

Extiendo el MatchingI II III IV V VI VII

A 1 1 0 1 1 1 1 IB 1 1 0 1 0 1 1 II C 0 1 1 0 0 0 0 III D 0 1 1 0 1 0 0 V E 0 0 1 0 1 0 0 F 1 1 1 1 1 1 1 IVG 0 1 0 0 1 0 0

B G E B E B B

55


56/111

I II III IV V VI VII

A 1 1 0 1 1 1 1 I

B 1

1 0 1 0 1 1 II

C 0 1 1 0 0 0 0 III

D 0 1 1 0 1 0 0 V E 0 0 1 0 1 0 0

F 1 1 1 1 1 1 1 IV

G 0 1 0 0 1 0 0

B G E B E B B


A 1 1 0 1 1 1 1 I

B 1 1 0 1 0 1 1 II

C 0 1 1 0 0 0 0 III D 0 1 1 0 1 0 0 V E 0 0 1 0 1 0 0

F 1 1 1 1 1 1 1 IV

G 0 1 0 0 1 0 0

B G E B E B BE E


A 1 1 0 1 1 1 1 I

B 1 1 0 1 0 1 1 II

C 0 1 1 0 0 0 0 III III

D 0 1 1 0 1 0 0 V V

E 0 0 1 0 1 0 0 F 1 1 1 1 1 1 1 IV

G 0 1 0 0 1 0 0

B G E B E B B

E E


A 1 1 0 1 1 1 1 I

B 1 1 0 1 0 1 1 II

C 0 1 1 0 0 0 0 III I

D 0 1 1 0 1 0 0 V E 0 0 1 0 1 0 0 F 1 1 1 1 1 1 1 IV

G 0 1 0 0 1 0 0

B G E B E B BC E E

I II III IV V VI VIIA 1 1 0 1 1 1 1 I B 1 1 0 1 0 1 1 II C 0 1 1 0 0 0 0 III III D 0 1 1 0 1 0 0 V V E 0 0 1 0 1 0 0 F 1 1 1 1 1 1 1 IV G 0 1 0 0 1 0 0 II

B G E B E B B

C E E

Obtengo:

• S = {C, D, E, G} = Filas etiqueteadas.

• Γ(S ) = {II, III, V } = Columnas etiqueteadas.

• Luego |Γ(S )| = 3 < 4 = |S | ∴ Matching Perfecto.Entonces tengo que subir el umbral.

56


57/111

Umbral 9


A 1 1 0 1 1 1 1B 1 1 1 1 1 1 1C 1 1 1 0 1 0 1D 1 1 1 0 1 0 0E 0 1 1 1 1 1 0F 1 1 1 1 1 1 1G 1 1 1 0 1 0 0

Busco Matching


A 1 1 0 1 1 1 1

B 1 1 1 1 1 1 1

C 1 1 1 0 1 0 1

D 1 1 1 0 1 0 0

E 0 1 1 1 1 1 0

F 1 1 1 1 1 1 1G 1 1 1 0 1 0 0


A 1 1 0 1 1 1 1

B 1 1 1 1 1 1 1C 1 1 1 0 1 0 1

D 1 1 1 0 1 0 0

E 0 1 1 1 1 1 0

F 1 1 1 1 1 1 1G 1 1 1 0 1 0 0

G G G GI II III IV V VI VII

A 1 1 0 1 1 1 1 I

B 1 1 1 1 1 1 1 II

C 1 1 1 0 1 0 1 III

D 1 1 1 0 1 0 0 V

E 0 1 1 1 1 1 0F 1 1 1 1 1 1 1G 1 1 1 0 1 0 0

G G G G


A 1 1 0 1 1 1 1 I

B 1 1 1 1 1 1 1 II

C 1 1 1 0 1 0 1 III

D 1 1 1 0 1 0 0 V

E 0 1 1 1 1 1 0F 1 1 1 1 1 1 1G 1 1 1 0 1 0 0

G G G A G A A

Extiendo el Matching


A 1 1 0 1 1 1 1 I B 1 1 1 1 1 1 1 II C 1 1 1 0 1 0 1 III D 1 1 1 0 1 0 0 V E 0 1 1 1 1 1 0F 1 1 1 1 1 1 1G 1 1 1 0 1 0 0

G G G A G A A

Existe Matching ∴ hay que bajar el umbral:

M = { A-VII:4 ; B-II:e ; C-III:1 ; D-V:4 ; E-IV:8 ; F-VI:6 ; G-I:8 }

∴ Tengo un Matching de 8, entonces no hago el umbral de 8, sólo basta ver si hayMatching de 1s con umbral e2.

57


58/111

Umbral de e2

I II III IV V VI VIIA 1

notas de discreta 2

Documents