discreta2 resumen general
TRANSCRIPT
Resumen de Discreta II
Maximiliano Illbele
16 de agosto de 2012
Índice1. 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 . . . . . . . . . . . . . . . . . . . . . . 302.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
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 . . . . . . . . . . . . . . . . . . . . 483.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 . . . . . . . . . . . . . . . . . . . . . . . . . 604.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
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 ≤P3-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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1087.5.10. Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1097.5.11. Mutación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1107.5.12. Mutaciones con Permutaciones . . . . . . . . . . . . . . . . . . . . . 110
7.6. No Free Lunch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
3
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: ∆ = max{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 Disconexo1
��������
======== 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
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
zzzzzzzzz
� ???????? DFS(A)⇒ A
�
Nivel 0
B
�
_C
yyyyyyyyy_
@@@@@@@@ D
mmmmmmmmmmmmmmmm
�
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
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 BFSG⇒ A
zzzzzzzzz
� ???????? BFS(A)⇒ A
�sssssssssssss
???????? Nivel 0
B
�
_C
yyyyyyyyy_
@@@@@@@@ D
�mmmmmmmmmmmmmmmm 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) 6= C(y)
Ejemplo de coloreoA(1)
xxxxxxxxx
� FFFFFFFFF
B(2)
�
_C(3)
xxxxxxxxx_
FFFFFFFFFD(2)
�kkkkkkkkkkkkkkkkkk
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
1.1.2. Algoritmo “Greedy” para coloreo
Requiere un orden de los vértices: x1, . . . , xn.Inicio: C(x1) = 1Para j > 1
C(xj) = El menor color que no crea conflicto con los vértices ya coloreados.
C(xj) = mın{k : C(xi) 6= k ∀i < j : xi ∈ Γ(xj)
}Invariante: en todo momento el coloreo es propio, por lo tanto al terminar da un
coloreo propio.Ejemplo:
B _
@@@@@@@@@@@@@@@@@@@ C _
���������������D
@@@@@@@@
~~~~~~~~~~~~~~~~~~~
A
~~~~~~~~
@@@@@@@@ E
~~~~~~~~
G F_
Orden alfabético Orden alternativoVértices A B C D E F GColor 1 2 1 2 1 3 4
G C D F B A E1 2 3 2 1 2 1
Complejidad de coloreo con Greedy
O(d(x1) + d(x2) + . . .+ d(xn)
)= O(2m) = O(m)
Teorema: sea G = C2r+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 6= B
Como estamos suponiendo χ(G) = 2 estos son los únicos colores que podemos usar.Como x2x3 ∈ E ⇒ C(x3) 6= 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
∴ χ(G) ≥ 3
Y está claro que con 3 colores alcanza definimos:
C(xi) =
A cuando i es Impar < 2r + 1B cuando i es ParC cuando i = 2r + 1
Corolario: si C2r+1 ⊆ G⇒ χ(G) ≥ 3Definición: un grafo G es bipartito si: χ(G) = 2
Teorema: G es bipartito ⇔ @C2r+1 ⊆ G
Más aún existe un algoritmo de complejidad polinomial para determinar si G es bi-partito o no.
Prueba: el algoritmo que daremos da un coloreo (propio) con dos colores, si χ(G) = 2,y si el algoritmo colorea con más de 2 colores entonces veremos que existe C2r+1 ⊆ G ∴χ(G) ≥ 3
En realidad esto lo haremos para cada componente conexa de G.Vamos a suponer G conexo.Sea x ∈ V , y corramos BFS(x) y tomemos el siguiente coloreo que puede no ser
propio:
C(z) =
0 Nivel(BFS(x), z
)es Par
1 Nivel(BFS(x), z
)es Impar
Si ese coloreo es propio ya está.Supongamos que no ⇒ ∃v, w : vw ∈ E : C(v) = C(w)Como vw ∈ E y estamos usando BFS, Si v fue puesto antes que w en el árbol entonces
debe ser:
nivel(w) = nivel(v + 1)⇒ Absurdo pues nivel(v) ≡ nivel(w) (2)
O bien nivel(v) = nivel(w) ∴ Hay un ciclo impar ⇒ χ(G) ≥ 3
1.1.3. Propiedades de Greedy
Analizando a Greedy, podemos decir que en ciertos casos puede andar muy malEjemplo:
Sea G : V = {1, . . . , 2r} y con E = ij
{i es Imparj es Par
y j 6= i+ 1
Para simplificar veamos el grafo correspondiente a r = 4
x1
BBBBBBBB
QQQQQQQQQQQQQQQ
UUUUUUUUUUUUUUUUUUUUUUU x3
BBBBBBBB
QQQQQQQQQQQQQQQ x5
BBBBBBBB x7
x2
||||||||
mmmmmmmmmmmmmmm
iiiiiiiiiiiiiiiiiiiiiii x4
||||||||
mmmmmmmmmmmmmmm x6
||||||||x8
8
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 V1 los vértices de color 1Sean V2 los vértices de color 2
...Sean Vt 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 V1 < los de V2 < . . . < los de Vt , en Vi los ordeno como quiero.
Por hipótesis inductiva hasta Vt−1 lo coloreamos con t− 1 colores.Los de Vt 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 ya
esté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
Más aún, si G es conexo o todas sus componentes conexas sean no regulares, tenemosque:
δ 6= ∆⇒ χ(G) ≤ ∆
Prueba: sea x ∈ V : d(x) = δCorramos BFS(x)6 y sea x1, . . . , xn el orden inverso al de BFS(x) ∴ xn = xEn BFS(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) = δ < ∆⇒ δ + 1 ≤ ∆
Ejemplos donde χ(G) = ∆ + 1
1. Los ciclos impares: χ(C2r+1) = 3 = 2 + 1 = ∆ + 1
2. Los grafos completos: χ(Kn) = n = (n− 1) + 1 = ∆ + 1
El teorema de Brooks dice que si G es conexo esos son los únicos ejemplos.
1.1.4. Heurísticas
1. Welsh-Powell
Greedy en el orden: d(x1) ≥ d(x2) ≥ . . . ≥ d(xn)
2. Matul-Marble-Isaacson
xn : d(xn) = δ
Sea Gn−1 = Gn − xnTomo xn−1 : δGn−1(xn−1) = δ(Gn−1) y así seguimos . . .
1
>>>>>>>>
MMMMMMMMMMMMMMM 3
;;;;;;;;
���������5
��������
qqqqqqqqqqqqqqqq
2
���������
qqqqqqqqqqqqqqqq4
��������6
3
>>>>>>>>
��������5
���������
qqqqqqqqqqqqqqqq
2
��������
qqqqqqqqqqqqqqqq4
���������6
3
���������5
��������
pppppppppppppppp
2
���������
pppppppppppppppp 4
��������
3
��������5
qqqqqqqqqqqqqqq
2
��������
qqqqqqqqqqqqqqq
3
��������
2 2
6O lo mismo DFS(x).7O DFS(x).
10
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 First1 RLF( )2 {3 c o l o r = 1 ;4 R = V; // Vértices no Coloreados5 while (R 6= ∅) {6 L = R;7 while (L 6= ∅) {8 Tomar v de L : V tenga l a mayor cant idad de vec ino s en R9 Color ( v ) = co l o r ;10 Remover (v ) de R;11 Remover (v ) y Γ(v ) de L ;12 }13 Color ++;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
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 flujoen 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 6= 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) = 0
O más aún: C(→ys) = 0 ∀y ∈ Γ−(s)
Notación:∑y∈Γ+(x)
f(→xy) = Outf (x)
∑y∈Γ−(x)
f(→yx) = Inf (x)
Definición: el valor del flujo es V (f) = Outf (s)− Inf (s)
8Viabilidad.9Source.
10Sink.
12
Propiedad: V (f) = Inf (t)−Outf (t)
Prueba:Sea D = Inf (t)−Outf (t)
Outf (x)− Inf (x) =
0 x 6= s, t
V (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 Inf (x).
∴ ? Nos queda: f(V, V )− f(V, V )︸ ︷︷ ︸=0
= V (f)−D
∴ V (f) = D
13
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: 102. Segundo camino: s, B, D, E, F, H, t: 53. No hay más caminos posibles.
Para este ejemplo podemos demostrar que no sólo es flujo sino también que esmaximal, 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
��00000000000000// B
��>>>>>>>>
s
��????????
??��������t
C
GG��������������// D
??��������
Corremos Greedy con el orden alfabético11Por ahora no está claro que f exista.
14
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
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 esV (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 backward
f(→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 6= 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) = Inf (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) = Inf (xi) + �ε− �ε
Luego: Outf∗(xi)− Inf∗(xi) = 0
3. B-F: xi−1−ε←− xi
+ε−→ xi+1
Inf∗(xi) = Inf (xi)
Outf∗(xi) = Outf (xi) + �ε− �ε
Luego: Outf∗(xi)− Inf∗(xi) = 0
16
4. B-B: xi−1−ε←− xi
−ε←− xi+1
Inf∗(xi) = Inf (xi)− ε
Outf∗(xi) = Outf (xi)− ε
Luego: Outf∗(xi)− Inf∗(xi) = 0
En el caso de s:
1. s +ε−→ x1
Outf∗(s) = Outf (s) + ε
Inf∗(s) = Inf (s)
∴ V (f ∗) = V (f) + ε
2. s −ε←− x1
Outf∗(s) = Outf (s)
Inf∗(s) = Inf (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 6∈ 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 ∈ Sy ∈ S→xy ∈ E
C(→xy)
17
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 6= s pues t 6∈ 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
2. V (f)1= f(S, S)− f(S, S)︸ ︷︷ ︸
≥0︸ ︷︷ ︸<0
∴ V (f) ≤ f(S, S) ≤ C(S, S) = Cap(S)
3. Sea g un flujo cualquiera:
V (g)2
≤ Cap(S)Hip(3)
= V (f)⇒ f es maximal
Similarmente, si T es corte tenemos que:
Cap(T )2
≥ V (g) ∀g
En particular elijo como flujo a f y me queda:
Cap(T )2
≥ V (f)Hip= Cap(S) ∴ S es minimal
19
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 6∈ 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)
Six ∈ Sy 6∈ 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 ∈ Sy 6∈ 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
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 22
��@@@@@@@@
??~~~~~~~~// x2
��
// y2
��
// t
x3 // y3
jj
??��������
Capacidades: todas 2 salvo:−→st : 1000
−→x1y1 : 1
−→x2y2 : r
−→x3y3 : r2
Donde: r = −1+√
52
es raíz de: P (r) = r2 + r − 1Observación:
1− r = r2
r − r2 = r3
Satisface: 1 > r > r2 > . . . > rk > rk+1
Corramos < F − F >
1. s, x1, y1, t : 1
2. s, x3, y3,←−y1, x1, x2, y2, t : r2
3. s, x2, y2,←−y3, x3, x1, y1, t : r3
4. s, x1, y1,←−y2, x2, x3, y3, t : r4
Luego < F − F > repite (2) (3) (4) con r5 r6 r7 . . .15Denotaremos así al algoritmo de Ford-Fulkerson.16Max Flow Min Cut.
21
∴< F − F > no termina, más aún si fi son los flujos intermedios:
lımi→∞
V (fi) = 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 − ff
∈ Z
Entonces ε será un entero y los flujos intermedios también.∴ Si les llamamos f1, f2, . . .⇒ V (fi+1) ≥ V (fi) + 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.
EjemploA
��
��>>>>>>>>
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
Lema: sea G un grafo conexo, dirigido o no, sea T = BFS(x) para algún x ∈ V ,entonces:
∀z ∈ V δ(z, x) = NivelT (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⇒ NivelT (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) ≤ NivelT (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) = kH.Ind⇒
NivelT (xk) = k
xkz ∈ ENivelT (z) = jNivelT (xk) = k
T=BFS(x)⇒ |j − k| ≤ 1
Ya que como son vecinos la diferencia de nivel es 0 ó 1.
Pero|j − k| ≤ 1j > 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 > +BFS
23
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 = f0, f1, . . .El paso k es el paso que “crea” fkDefino:
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 6= ∅ 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 6= s pues dk+1(s) = dk(s) = 0Sea s = x0, x1, . . . , xr−1, xr = qUn camino aumentante de longitud mínima r = dk+1(q) entre s y q.
(El camino existe pues (2) ⇒ dk+1(q) <∞).Sea x = xr−1
Tenemos: dk+1(x) = r − 1 = dk+1(q)− 1 < dk+1(q)
∴ dk+1(x) < dk+1(q) (3)
dk+1(x) < dk+1(q)⇒ x 6∈ A por (1)
(En otras palabras, como x está antes que q, no puede estar en A)
Luego como x 6∈ A⇒ dk(x) ≤ dk+1(x) (4)
17Recordando que: n = |V | y m = |E|.
24
Diremos que un lado (u, v) está “disponible” en un paso j si:
Es Forward con fj−1(→uv) < C(
→uv)
Es Backward con fj−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
∴ 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 la
distancia a t haya aumentado en por lo menos 2.
# Veces que un lado puede volverse crítico = O(n)
Exactamente sería: n−12
Complejidad de cada búsqueda BFS + 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
2.4.2. Ejemplo de Edmonds Karp
Capacidades CaminossA: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:3s A C B E F D K I J G H t
s 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:10s 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:10s 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
Obtengo el Corte: S = {s,c,k,i,b,j,a,f,g}
Capacidad del corte SCap(S) =10 + 10 + 10 + 2 + 3 + 3 = 38
cd+ 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 ; // Flu jo4 v = 0 ; // Valor d e l F lu jo5 S = V; // Corte6 while (t ∈ S ) { //mientras e l v e r t i c e t e s t e en e l co r t e7 // buscar camino y aumentar8 Q = new_queue (S) ; //Crear co l a9 E[ x ] = ∞ ∀x ∈ V ;10 S = { s } ; // cor t e11 while ( head (q ) 6= t ) {12 x = head (q ) ;13 Forward_search (x ) ;14 Backward_search (x ) ;15 dequeue (q ) ; // saco x de l a co l a16 }17 i f (t ∈ S ) {18 Aumentar_flujo ( ) ;19 }20 }21 return (F , v , S) // f l u j o , va lor , co r t e22 }2324 Forward_search ( v e r t i c e x )25 {26 for (q ∈ Γ+(x) && q 6∈ S ) {27 i f ( f (
−→xq ) < C(
−→xq ) ) {
28 enqueue (Q, q ) ; //Agregar q a Q29 S = S ∪ {q } ;30 A[ q ] = x ; //Ancestro31 E[ q ] = min{E(x ) ,C(
−→xq ) − F(
−→xq ) } ;
32 b [ q ] = 1 ; // forward33 }34 }35 }36373839
28
4041 Backward_search ( v e r t i c e x )42 {43 for (q ∈ Γ−(x) && (q 6∈ S ) ) {44 i f ( f (
−→qx )>0) {
45 enqueue (Q, q ) ; //Agregar q a Q46 S = S ∪ {q } ;47 A[ q ] = x ; //Ancestro48 b [ q ] = −1; //Backward49 E[ q ] = min{E(x ) ,F(
−→qx ) } ;
50 }51 }52 }5354 Aumentar_Flujo ( )55 {56 p = t ; // p i v o t e57 ε = E( t ) ;58 v = v + ε ;59 while ( p 6= s ) {60 q = a [ p ] ;61 i f (b [ p ] == 1) { //FORWARD62 f (
−→qp ) = f (
−→qp ) + ε ;
63 } else {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 Nivel(q) = Nivel(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
2.5.1. Esquema general Tipo Dinic
1 Dinic ( )2 {3 f = 0 ;4 Stop = NO;5 while ( Stop == NO){6 NA = New_Na( f ) ; // con s t r u i r Network a u x i l i a r a p a r t i r de f7 i f ( t ∈ NA){8 g = Hal lar_bloqueante (NA) ; // busco un f l u j o b l oquean te en NA9 f = f ⊕ g ;10 } else {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 “<”.
Sea s = x0, x1, . . . , xr = t un camino en A′.
Caso 1: ∃i ∈ {1, . . . , r − 1} : xi 6∈ A
⇒ δ(t) ≤ δ(xi) (10)≤ δ′(xi) (11)= i < r = δ′(t)
( 10) Sino lo hubiera agregado.
( 11) Por < E −K >
∴ δ(t) < δ′(t)
Caso 2: xi ∈ A ∀iComo 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 6∈ AY tomemos el primer tal i.
18NA: networks auxiliares.
30
• 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 6∈ A⇒−→
xj−1xj ∈ 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 6∈ 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 Absurdopues Nivel(xi+1) = i+ 1, y Nivel(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
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 : 2
BJ: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:0Jt:15 Jt:13 Jt:8
Primer Network Auxiliar Segundo Network auxiliar
I
��///////////////
A
>>}}}}}}}}//
AAAAAAA G
��>>>>>>>>
s
??��������//
��????????
��/////////////// C
>>}}}}}}}
AAAAAAA
��000000000000000 F // t
D
>>}}}}}}}
GG���������������H
??��������
E
GG���������������
II����������������������
>>}}}}}}}J
GG���������������
D //
AAAAAAA F(−) // A // I
��========
s
��????????
??��������G //
(−)
AAAAAAA
(−)>>~~~~~~~~B
??��������
��??????? t
E //
>>}}}}}}}
GG���������������H
(−) // C // J
@@��������
Tercer Network auxiliars //
��???????? 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+ ft
32
Se ve que Cap(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 Dinic (Network Na) { // Parte Bloqueante , Version con Goto2 g = 0 ;3 2 p = s ; // l a b e l 2 , p i v o t e4 1 i f (p 6= t) { // l a b e l 15 i f (Γ+(p) 6= ∅) {6 avanzar ( ) ;7 goto 1 ;8 } else i f (p 6= s) {9 r e t r o c ed e r ( ) ;10 goto 1 ;11 } else return g ;12 } else {13 Incrementar_f lu jo ( ) ;14 goto 2 ;15 }16 }1718 Dinic (Network Na) { \\ Parte Bloqueante , Vers ion goto l e s s ;19 g = 0 ;20 E( s ) = ∞ ;21 cont inuar = 1 ;22 while ( cont inuar ) {23 p = s ;24 while (p 6= t && cont inuar ) {25 i f ( Γ+(p) 6= ∅) {26 Avanzar ( ) ;27 } else i f (p 6= s ) {28 Retroceder ( ) ;29 } else {30 cont inuar = 0 ;31 }32 }33 i f (p == t ) {34 Incrementar_f lu jo ( ) ;35 }36 }37 Return g38 }394041424344
33
4546 // Pre p t i e n e vec ino47 Avanzar ( p ivote p) {48 Tomar q ∈ Γ+(p)49 A(q ) = p ; // ances t ro de q es p50 E(q ) = min{E(p) ,C(
−→pq )−G(
−→pq ) } ;
51 p = q ;52 }5354 // Pre p t i e n e vec ino55 Retroceder ( p ivote p)56 {57 Borrar p de Γ+(A(p))58 p = A(q ) ;59 }6061 Incrementar_Flujo ( )62 {63 ε = E( t ) ;64 q = t ;65 while (q 6= s) {66 p = a (q ) ;67 G(
−→pq ) = G(
−→pq ) + ε ;
68 i f (G(−→pq ) == C (
−→pq ) ) {
69 Borrar q de Γ+(p)70 }71 }72 q = p ;73 }
34
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 . . . AX) = O(n) +O(n) = O(n)
(1) + (2)⇒ Complejidad(Paso Bloqueante de Dinic) = m ∗O(n) = O(n ∗m)
35
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 olaForward ( ) ;4 olaBackward ( ) ;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 6= s){15 B(x ) = 0 ; //No b loqueado16 D(x ) = 0 //Desbalanceo17 A(x ) = ∅ // subconjunto de a q u e l l o s que l e mandaron f l u j o a x18 }1920 D( s ) = 0 ;21 N = 1 ; // #Ver t i c e s ba lanceados2223 ∀(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 for ( x = s +1; To ; t−1){ //Orden BFS()35 i f (D(x )>0)36 ForwardBalance (x ) ;37 }38 }
19Wave: inglés, ola.
36
3940 olaBackward ( )41 {42 for ( x = t − 1 DownTo s+1){ //Orden BFS()43 i f (D(x )>0 && B(x ) == 1)44 BackwardBalance (x ) ;45 }46 }4748 BackwardBalance ( 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 ForwardBalance ( v e r t i c e x ) {67 while (D(x )>0 && (Γ+(x) 6= ∅)) {68 Tomar y ∈ Γ+(x) ;69 i f (B(y ) == 1) {70 Γ+(x) = Γ+(x) − {y}71 } else {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 ; //Bloqueamos x87 else88 N−−;89 }
37
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 FB(x) a sólo un lado le mandamos flujo parcial.
Compl(ola Forward)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 siel lado es →xy lo quisiera volver a saturar debería primero hacer que “y” le devuelvael 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 puedehacerlo si “y” está bloqueado.
∴ #Saturamientos+ #V aciamientos ≤ 2m
∴ Compl(Wave_bloqueante)t = O(m)
38
Compl(Wave_bloqueante) = Compl(Wave_bloqueante)t + Compl(Wave_bloqueante)p= O(m) +O(n2)
= O(n2)
2.6.3. Ejemplos de Wave
Aplicar Wave al siguiente Network Auxiliar
sA:8 → 0sC:7 → 0sD:10 → 7sE:7 → 0AF:4 → 0AG:3 → 0AI:8 → 7CG:2 → 0CH:3 → 0CJ:5 → 3DF:4 → 1DG:2 → 2EF:3EG:5EH:4Ft:7 → 3Gt:5 → 0Ht:4 → 0It:9 → 8Jt:15 → 13
Nivel 0 Nivel 1 Nivel 2 Nivel 3s 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 6 0 0 ��12
�1 �2 ��4 6 0 ��11 �7 ��13
0 0 ��4 ��11 ��16
→ ��6 ��18
-25 ��6 �4 �
�1 ��2
��7 �7 0 00 ←
→ ��3 �4 19
��3
-19 0 0←
39
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 → 1EF:3 → 0EG:5 → 1EH:4Ft:7 → 0Gt:5 → 0Ht:4 → 0It:9 → 1Jt:15 → 11
Nivel 0 Nivel 1 Nivel 2 Nivel 3s A C D E F G I H J t-32 6 8 �7 ��10 6 7 6 4 6 3 6 1 6 3 6 2 �7
6 4 6 5 6 6 6 4 �8 �5 �0 0 �0 ��12
6 1 6 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 27
0 0 ←
Importante ver que termino porque Outf (s) = Inf (t)
40
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 DFS(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 6= raíz.
∴ Hay n− 1 lados. (uno por cada vértice 6= 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 6∈ 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
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ón∑xy∈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
3.1.1. Pseudo Código de Kruskal
1 Kruskal ( )2 {3 //α4 ∀(x ∈ V ){5 Makeset ( x ) ;6 }78 //β9 Edges_Sort ( ) ; //Ordenar l o s l ados : W(E[ i ] ) ≤ W(E[ i +1])10 m = 0 ; // cant idad de l ados11 i = 1 ; // ind i c e1213 // γ1415 while (M < N−1){16 A = f ind (x [ i ] ) ;17 B = f ind (y [ i ] ) ;18 i f (A 6= B){19 t r e e . add ( e [ i ] ) ; // agregar a l a r bo 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 Kj 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 Tj : Kj ⊆ Tj
Supongamos que Kj ⊆ Tj MST.Sea e : Kj+1 = Kj ∪ {e}
• Si e ∈ Tj ya está pues Kj+1 ⊆ Tj
• Por lo tanto supongamos: e 6∈ TjEn este caso, Tj ∪ {e} tiene: n− 1 + 1 = n lados ∴ no es árbol.Como Tj es conexo ⇒ Tj ∪ {e} es conexo.Como no es árbol ⇒ Tj ∪ {e} tiene un ciclo C.Pero Tj no tiene ciclos ⇒ e forma parte del ciclo C.
43
Sea f un lado de C que no esté en Kj+1 (∃f ⇐ Kj+1 es acíclico).
Tj+1 = (Tj − f) ∪ {e}= (Tj ∪ {e})− f
Como C es un ciclo: y f ∈ C ⇒ (Tj ∪ {e})− f sigue siendo conexo.
∴ Tj+1 es conexo y tiene: n− 1 + 1− 1 = n− 1 lados ⇒ Tj+1 es un árbol.
Como Kj+1 ⊆ Tj+1 basta ver que Tj+1 es minimal.Pero W (Tj+1) = W (Tj)−W (f) +W (e)
Pero f 6∈ Kj+1
Si W (f) < W (e)⇒ f se “analizó” antes de e.Como f 6∈ Kj+1 entonces se rechazó.Entonces Kj ∪ {f} tiene un ciclo absurdo pues Kj ∪ {f} ⊆ Tj︸︷︷︸
árbolYa que
(Kj ⊆ Tj y f ∈ Tj
)(estoy diciendo que un subconjunto de un árbol tiene un ciclo, absurdo).
∴ W (f) ≥ W (e)
W (Tj+1) ≤ W (Tj)Como Tj es MST
}⇒ Tj+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
3.1.6. Ejemplo de Kruskal
A B C D E FA − 5 − 3 1 3B 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�
F2 _D C
(5) A
3�
1 _E B
1�
F1 _D
4~~~~~~~~C
F3
~~~~~~~~3
@@@@@@@@
2
000000000000000
A1 _
5� 3
PPPPPPPPPPPPPPP E
4�
B
1 @@@@@@@@ 4_D
7~~~~~~~~
C
45
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 Prim( v e r t i c e x )2 {3 ∀(p ∈ V ){4 Costo [ p ] = ∞ ;5 Vecino [ p ] = NULL;6 }78 Costo (x ) = 0 ;9 M = 0 ;10 Aux = V;1112 //FALTA CASO BASE1314 while (m < n−1){15 // pre : cos to (p )< cos to ( q ) ∀q ∈ Aux16 ∀(q ∈ Γ(p)){17 i f ( co s to (q )> V(pq ) ) {18 cos to (q ) = W(pq ) ;19 vec ino (q ) = p ;20 }21 }22 Add(p , vec ino (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 Pj es el árbol en el paso j, probaremos que ∃ MST Tj : Pj ⊆ Tj
j = 0: Trivial.
Supongamos que vale para j
Si Pj+1 ⊆ Tj ya está.
De lo contrario existe e ∈ Pj+1 : e 6∈ Tj (y de hecho, será Pj+1 = Pj ∪ {e} ).e une Pj con V − PjComo Tj es Spanning Tree ⇒ debe conectar Pj con V − Pj.
46
Sea f un lado en Tj que conecte estas dos regiones.
Como e es el menor lado que conecta esas dos regiones tenemos que:
W (e) ≤ W (f)
Entonces: W (Tj ∪ {e} − f) ≤ W (Tj)
∴ Tj ∪ {e} − f es un MST que contiene a Pj+1.
3.2.3. Ejemplo de Prim
A B C D E FA − 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) A3
�
1 _E
D
(3) A3
�
1 _E
D2 _F
(4) A3
�
1 _E
D2 _
4�
F
B
(5) A3
�
1 _E
D2 _
4�
F
B1 _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
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 Makeset ( x ) { //O(1)3 R(x ) = x ;4 }56 Find (x ) { // O(1)7 return R(x ) ;8 }910 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
3.3.3. Union Find con ranking
1 Makeset ( v e r t i c e x ) {2 Π(x) = x ;3 Rk(x ) = 0 ; //Ranking4 }5 Find ( v e r t i c e x ) { // r e cu r s i v o a l a co l a6 i f (Π(x) == x)7 return x ;8 else return f i nd (Π(x))9 }10 Find ( v e r t i c e x ) { // i t e r a t i v o11 y = x ;12 while ( y 6= Π(y))13 y = Π(y) ;14 return y ;15 }16 /∗ Pre : F1 = Find ( x [ 1 ] ) ; F2 = Find ( x [ 2 ] ) ; F1 6= F2 ∗/17 Union (F1, F2 ) {18 k1 = Rank(F1 ) ;19 k2 = Rank(F2 ) ;20 i f (K1 > K2 ) {21 Π(F2) = F1 ; // cabeza d e l 2do apunta a l primero22 } else {23 Π(F1) = F2 ; // cabeza d e l primero apunta a l segundo24 i f (k1 == k2 ) {25 Rank(F2 ) = 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 6= Π(x))
Obvio pues Rank solo cambia con Union, y lo cambia sólo a F2 cuando Π(F1) == F2
En ese caso incrementa el rango de F2
49
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) ∀xPues 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 Find (x ) {2 i f (Π(x) 6= x) {3 Π(x) = Find (Π(x)) ;4 }5 return Π(x) ;6 }
El análisis es más complicado, cada Find() 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
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 flujomaximal
Dado G = (X ∪ Y,E) creamos el siguiente network.N =
(X ∪ Y ∪ {s, t},
→E,C
)→E =
{−→sx}x∈X
⋃−→xy :x ∈ Xy ∈ Yxy ∈ E
⋃{−→yt}y∈YLa capacidad de todos los lados es : 1.
Ejemplo
X A
� ;;;;;;;;; B
�
C
�
Y 1 2
���������3
⇒
s
� AAAAAAAA
}}}}}}}}
A
� @@@@@@@@ B
�
C
�
1 2
~~~~~~~~3
t
� ~~~~~~~~~
@@@@@@@@@
TeoremaFlujos maximales en N corresponden con matchings maximales en G y V (fmax) = #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 Mf y dado un Matching Mconstruimos un flujo entero fM .
Dado f sea Mf = (Vf , Ef ) :Vf =
⋃xy∈Ef
{x, y}
Ef = {xy ∈ E : f(−→xy) = 1}
Hay que ver que Mf es matching.
51
Observemos que por definición de Vf tenemos que δMf(z) ≥ 1 ∀z ∈ Vf
Si Mf no es matching ⇒ ∃z : δMf(z) ≥ 2
Caso 1: z ∈ X como δMf(z) ≥ 2 entonces ∃y1, y2 :
y1 6= y2
zy1, zy2 ∈ EfEntonces f(
−→zy1) = f(
−→zy2) = 1
∴ Outf (z) ≥ 2
Pero Inf (z) = f(−→sz ) ≤ 1
⇒ Absurdo.
Caso 2: z ∈ Y ⇒ ∃x1, x2 :x1 6= x2
x1z, x2z ∈ EfEntonces f(
−→x1z) = f(
−→x2z) = 1
∴ Inf (z) ≥ 2
Pero Outf (z) = f(−→zt ) ≤ 1
⇒ Absurdo
Concluimos que Mf es matching.
Dado ahora un Matching M sea fM definido así:
fM(−→xy) =
{1 Si xy ∈ E(M)0 Si no
fM(−→sx) =
{1 Si x ∈ V (M) ∩X0 Si no
fM(−→yt ) =
{1 Si y ∈ V (M) ∩ Y0 Si no
Como M es matching, está claro que:
Mf (z) = Outf (z) =
{1 Si z ∈ V (M)0 Si z 6∈ V (M)
Además está claro que: MfM = M y que: fMf= f
52
Veamos ahora que: V (f) = |EMf|
V (f) = Outf (s)−=0︷ ︸︸ ︷
Inf (s)
=∑x∈X
f(−→sx)
= #{x : f(−→sx) = 1}
= #{x : Inf (x) = 1}= #{x : Outf (x) = 1} por ser f un flujo= |Vf ∩X|= |EMf
|
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 Ysi 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
Cx,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
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 Ci,j como : b1 < b2 < . . . < bk (k ≤ n2)
2. Tomar, para r= 1, . . . , k:
(Ar)i,j =
{1 Si Ci,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:
max{Ci,j : {i, j} ∈ E(M)} ≤ max{Ci,j : {i, j} ∈ E(M)} ∀M
23Problema de cuello de botella.
54
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 Ci,j: 1, 2, e, 3, π, 4, 5, 6, 7, e2, 8, 9, 10, 15, 1000
max{mın(filas); mın(columnas)} = max{1, 1, 1, 1, 1, 1, 2; 1, 1, 1, 2, 1, 2, 1} = 2
Umbral 7
Busco 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 1G 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 ��VE 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 ��VE 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
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
D 0 1 1 0 1 0 0 ��VE 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
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
D 0 1 1 0 1 0 0 ��VE 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
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 IIID 0 1 1 0 1 0 0 ��V VE 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
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 ��VE 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 ��VE 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
Umbral 9
I II III IV V VI VIIA 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
I II III IV V VI VIIA 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 ?
I II III IV V VI VIIA 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 �?
G G G GI II III IV V VI VII
A 1 1 0 1 1 1 1 IB 1 1 1 1 1 1 1 IIC 1 1 1 0 1 0 1 IIID 1 1 1 0 1 0 0 VE 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
I II III IV V VI VIIA 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 MatchingI 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 ��A ��G ��A AExiste 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 1′s con umbral e2.
57
Umbral de e2
I II III IV V VI VIIA 1 1 0 1 1 1 1B 1 1 1 1 0 1 1C 0 1 1 0 0 0 0D 1 1 1 0 1 0 0E 0 0 1 0 1 0 0F 1 1 1 1 1 1 1G 0 1 0 0 1 0 0
Busco Matching
I II III IV V VI VIIA 1 1 0 1 1 1 1B 1 1 1 1 0 1 1C 0 1 1 0 0 0 0D 1 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 ?
I II III IV V VI VIIA 1 1 0 1 1 1 1B 1 1 1 1 0 1 1C 0 1 1 0 0 0 0D 1 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 1 1 0 1 1 IIC 0 1 1 0 0 0 0 IIID 1 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 1 1 0 1 1 ��II
C 0 1 1 0 0 0 0 ��III
D 1 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 �?
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 1 1 0 1 1 ��II
C 0 1 1 0 0 0 0 ���III
D 1 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 �?
��B ��G ��E ��B ��E ��B B
58
I II III IV V VI VIIA 1 1 0 1 1 1 1 I
B 1 ��1 1 1 0 1 1 ��IIC 0 1 1 0 0 0 0 ��III IIID 1 1 1 0 1 0 0 �V VE 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
�E �E
I II III IV V VI VIIA 1 1 0 1 1 1 1 I
B 1 ��1 1 1 0 1 1 ��IIC 0 1 1 0 0 0 0 ��III ��IIID 1 1 1 0 1 0 0 �V �VE 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 BD C �E �E
I II III IV V VI VIIA 1 1 0 1 1 1 1 I I
B 1 ��1 1 1 0 1 1 ��IIC 0 1 1 0 0 0 0 ��III ��IIID 1 1 1 0 1 0 0 �V �VE 0 0 1 0 1 0 0 �? �?F 1 1 1 1 1 1 1G 0 1 0 0 1 0 0 �? II�B �G �E �B �E �B B�D �C �E �E
I II III IV V VI VIIA 1 1 0 1 1 1 1 I �I
B 1 ��1 1 1 0 1 1 ��IIC 0 1 1 0 0 0 0 ��III ��IIID 1 1 1 0 1 0 0 �V �VE 0 0 1 0 1 0 0 �? �?F 1 1 1 1 1 1 1G 0 1 0 0 1 0 0 �? ��II�B �G �E �B �E �B B�D �C �E A �E A A
Extiendo el MatchingI II III IV V VI VII
A ��1 1 0 1 1 1 1 I ��I
B 1 ��1 1 1 0 1 1 ��II
C 0 1 1 0 0 0 0 ���III �
��III
D 1 1 1 0 ��1 0 0 ��V ��V
E 0 0 1 0 1 0 0 �? �?
F 1 1 1 1 1 1 1G 0 1 0 0 1 0 0 �? ��II
��B ��G ��E ��B ��E ��B B��D ��C ��E ��A ��E ��A ��A
Hallé un Matching que minimiza el máximo: (e2)M =
{A− V II : 4;B − V I : 2;C − III : 1;D− I : e2;E − V : 1;F − IV : 4;G− II : 2
}
59
4.5. Prueba del teorema de HALL
Sea G = (X ∪ Y,E) grafo bipartito entonces:existe matching completo de X a Y ⇔ |S| ≤ |Γ(S)| ∀S ≤ X
Prueba:⇒ Obvio pues el matching induce una funcion ψ : 1− 1 de X en Y y la imagen de S
por esa función está incluida en Γ(S)
∴ |S| ψ1−1= |ψ(S)| ≤ |Γ(S)|
⇐ Es equivalente a ver que:
Si @ un matching completo ⇒ ∃S ⊆ X : |S| > |Γ(S)|
Corramos el algoritmo de hallar matching (Filas X, Columnas Y )Cuando termine habrá filas sin Matchear24.Sea S0 = Filas sin Matchear.Sea T1 = Γ(S0) son las columnas etiqueteadas por las filas de S0
S1 = Filas etiqueteadas por las columas de T1
T2 = columnas etiqueteadas por las filas de S1.No necesariamente T2 6= Γ(S1).Pero si tenemos que T1 ∪ T2 = Γ(S0 ∪ S1)Y así seguimos:Nos queda definido:
Sj = Filas etiqueteadas por las columnas de Tj
Tj+1 = las columnas etiqueteadas por las filas de SjSj = filas Matcheadas con Tj.∴ Si Tj 6= ∅ ⇒ Sj también.El algoritmo se detiene sin extender el matching (por hipótesis).Por lo tanto se detiene en un k con Tk+1 = ∅Observación:
1. |Sj| = |Tj| ∀j Pues Sj son las filas Matcheadas con Tj
2. Γ(S0 ∪ . . . ∪ Sj) = T1 ∪ T2 ∪ . . . ∪ Tj+1
Sea S = S0 ∪ S1 ∪ . . . ∪ Sk
|Γ(S)| = |Γ(S0 ∪ . . . ∪ Sk)|= |T1 ∪ . . . ∪ Tk ∪ Tk+1| (17)= |T1 ∪ . . . ∪ Tk| (18)= |T1|+ . . .+ |Tk| (19)= |S1|+ . . .+ |Sk| (20)= |S| − |S0|< |S|
24Las marcadas con ?.
60
( 17) Por las observación 2.( 18) Tk+1 = ∅( 19) Unión Disjunta.( 20) Por las observación 1.
4.6. Teorema del Matrimonio
Todo grafo bipartito regular (con lados) tiene un matching perfecto.
Prueba: sea G = (X ∪ Y,E) : E 6= ∅, regular.Dado W ⊆ V con W ⊆ X ó W ⊆ YDefinimos:
Ew = Lados con un extremo en w= {xy ∈ E : x ∈ Wó y ∈ W}
Supongamos W ⊆ X
|Ew| =∣∣∣{xy ∈ E : x ∈ w}
∣∣∣=∑x∈w
∣∣∣{y : xy ∈ E}∣∣∣
=∑x∈w
d(x)︸︷︷︸∆
(21)
= ∆ ∗ |w|
( 21) Por ser G regular.Similar prueba si: W ⊆ YObservemos que por ser G bipartito: Ex = E = Ey∴ |Ex| = |Ey| ⇒ ∆ ∗ |X| = ∆ ∗ |Y |Como ∆ 6= 0⇒ |X| = |Y |Por lo tanto para ver si existe un matching perfecto en G, basta ver que existe un
matching completo de X a Y .Por el teorema de Hall basta entonces con ver: |S| ≤ |Γ(S)| ∀S ⊆ XSea entonces S ⊆ X
Sea e ∈ Es ⇒ ∃x ∈ Sy ∈ Y : e = xy
⇒ y ∈ Γ(x) ⊆ Γ(S)⇒ e = x y ∈ EΓ(s)
∴ Hemos probado que: Es ⊆ EΓ(S)
⇒ |Es| ≤ |EΓ(S)|∆|S| ≤ ∆|Γ(S)|∴ |S| ≤ |Γ(S)|
61
4.7. Minimizar la Suma
Problema: dada una matriz de costos C, hallar el menor M, Matching.
Simbólicamente buscamos M: M = mınn∑
i = 1j : ij ∈M
Ci,j
La solución a este problema usa una idea sencilla: sea C una matriz de costos que seobtiene de C restándole o sumándole una constante a una fila o columna.
Entonces sea Mmın(C) un Matching que minimiza la suma.
Si a la fila i le resto una constante k, i.e. Ci,j{
Ci,j Si i 6= i
Ci,j − k Si i = i
Está claro que:n∑
i = 1j : ij ∈M
Ci,j =( n∑
i = 1j : ij ∈M
Ci,j
)− k , similar para las columnas.
∴Mmın(C) también minimiza C
Segunda Observación: si Ci,j ≥ 0.Entonces si M es un matching de 0′s es decir Ci,j = 0 ∀i, j ∈ M ⇒ M minimiza la
suma.Idea básica: restar o sumar fila “inteligentemente” hasta hallar un matching de ceros.
Ese matching automáticamente minimiza la matriz original.
4.7.1. Ejemplo de Matching que minimiza la Suma (A ojo)
I II III IVA 2 5 7 7B 9 10 5 11C 1 6 7 10D 10 1 4 4
Restamos a cada fila su mínimo Restamos a cada columna su mínimoI II III IV
A 0 3 5 5B 4 5 0 6C 0 5 6 9D 9 0 3 3
I II III IVA 0 3 5 2B 4 5 0 3C 0 5 6 6D 9 0 3 0
@ Matching de 0′s.
Restamos 5 a la tercer fila.I II III IV
A 0 3 5 2B 4 5 0 3C -5 0 1 1D 9 0 3 0
Existe Matching Pero tengo un número Negativo.
62
Sumamos 5 a la columna I Restamos el mínimo a cada fila. Hallé un Matching de 0′s.I II III IV
A 5 3 5 2B 9 5 0 3C 0 0 1 1D 14 0 3 0
I II III IVA 3 1 3 0B 9 5 0 3C 0 0 1 1D 14 0 3 0
I II III IVA 3 1 3 0B 9 5 0 3C 0 0 1 1D 14 0 3 0
M ={AIV : 7;BIII : 5;CI : 1;DII : 1
}∴ Hallé un matching que minimiza la suma(14).
4.7.2. Algoritmo Húngaro
Algoritmo de Khun-Munkres, conocido como algoritmo húngaro.
1. Restar el mínimo de cada fila a cada fila.
2. Restar el mínimo de cada columna a cada columna.
3. Buscar Matchings de 0′s
Si existe hallé un matching que minimiza la suma.
Sino tomar S: |S| > |Γ(S)|, y restarle un cierto m a las filas de S y sumarle ma las columnas de Γ(S)
• ¿Cuál m?• m = mınS ∩ Γ(S)
Equivalentemente: restar m a S ∩ Γ(S) y sumar m a S ∩ Γ(S)
4.7.3. Ejemplo del algoritmo Húngaro
I II III IV
A 2 5 7 7B 9 10 5 11C 1 6 7 10D 10 1 4 4
1. Restamos a cada fila su mínino:
I II III IV
A 0 3 5 5B 4 5 0 6C 0 5 6 9D 9 0 3 3
63
2. Restamos a cada columna su mínimo:
I II III IV
A 0 3 5 2B 4 5 0 3C 0 5 6 6D 9 0 3 0
3. Buscamos Matching de 0′s
I II III IVA 0 3 5 2B 4 5 0 3C 0 5 6 6 *D 9 0 3 0
I II III IVA 0 3 5 2B 4 5 0 3C 0 5 6 6 6 ∗D 9 0 3 0
C
I II III IVA 0 3 5 2 IB 4 5 0 3C 0 5 6 6 6 ∗D 9 0 3 06 C
4. No hay matching perfectoI II III IV
A 0 3 5 2 6 IB 4 5 0 3C 0 5 6 6 6 ∗D 9 0 3 06 C
Tengo S = {A,C} , las filas etiqueteadas.Γ(S) = I , las columas etiqueteadas.
Con |S| > |Γ(S)|
5. Calculo: m = mınS ∗ Γ(S)
I II III IVA 0 3 5 2 6 IB 4 5 0 3C 0 5 6 6 6 ∗D 9 0 3 06 C
m=2−→
I II III IV
A 0 1 3 0B 6 5 0 3C 0 3 4 4D 11 0 3 0
Referencias:
S ∩ Γ(s) No lo modificoS ∩ Γ(s) Sumo mS ∩ Γ(S) No lo modificoS ∩ Γ(S) Resto m
64
6. Busco Matching de 0′S
a) No encuentro:
I II III IV
A 0 1 3 0
B 6 5 0 3C 0 3 4 4D 11 0 3 0
b) Intento extenderlo:
I II III IVA 0 1 3 0B 6 5 0 3C 0 3 4 4 ��*D 11 0 3 0
C
⇒
I II III IVA 0 1 3 0 IB 6 5 0 3C 0 3 4 4 ��*D 11 0 3 0
��C
I II III IVA 0 1 3 0 ��IB 6 5 0 3C 0 3 4 4 ��*D 11 0 3 0
��C A
Extiendo el matching
I II III IVA �
�0 1 3 0 ��IB 6 5 0 3C 0 3 4 4 ��*D 11 0 3 0
��C A
7. Llegué al Matching de 0′s:
I II III IV
A 0 1 3 0B 6 5 0 3
C 0 3 4 4
D 11 0 3 0
“A mano”
1. Tachar filas de S, y las columnas de Γ(S).
2. De lo no tachado, calcular el mínimo m.
3. Restar de lo no tachado m.
4. Sumar, a lo tachado dos veces, m.
4.7.4. Complejidad de algoritmo Hungaro
Restar el mínimo en cada fila: O(n2).
Restar el mínimo en cada columna: O(n2).
Buscar Matching inicial: O(n2)
Extender matching en un lado: “Paso” ∴ hay O(n) pasos.
65
Complejidad de cada Paso
Buscar m, restarlo y sumarlo: O(n2).
Buscar Matching en la nueva matriz O(n3).
¿Cuántas veces buscamos m en un paso? No sabemos
∴ Compl(Hungaro) = O(n) ∗O(n3) ∗ (No sabemos)
Llamémosle “cambio de matriz” a buscar el m, restarlo y sumarlo.
Lema: luego de un cambio de matriz el matching parcial que se tenía no se pierde.
Prueba: la idea está en fijarse dónde está el matching. A AB C
SS
Γ(S) Γ(S)
Referencias
A: puede haber ceros.
B: No hay ceros, no hay matching.
C: Ceros del Matching.
S ∩ Γ(S) y S ∩ Γ(S) no cambian.
Por lo tanto cualquier 0 de matching ahí permanece.
En S ∩ Γ(S) no hay ceros, por lo tanto no hay matching.Sólo queda por ver: S ∩ Γ(S), donde puede haber ceros, pero ninguno del matching,
pues supongamos que hubiera uno en la columna j, fila i.i 6∈ S, j ∈ Γ(s).Cuando revisamos la columna j buscamos el elemento del matching, ∴ hubieramos
agregado la fila i a S, absurdo.
Corolario: luego de un cambio de matriz, aumenta el matching, (i.e. se termina el paso)o bien aumenta S.
Prueba:En S ∩Γ(S) habrá un nuevo cero, digamos en la columna j, al revisar la j si está libre
extendemos el matching.Sino hay una fila i con {i, j} ∈ M :matching, por lo tanto agregamos la fila i a S.
Entonces S crece.Observación: i no formaba parte de S, pues por el lema anterior i debe estar en S.Corolario: hay a lo sumo n cambios de matriz en cada paso, pues S sólo puede crecer
n veces.
66
Por lo tanto:
Compl(Hungaro) = n ∗ Compl(paso)
Compl(paso) = n︸︷︷︸cambio de matriz
∗Compl(cambiar la matriz) +O(n2)
Compl(cambiar la matriz) = O(n2)
Compl(paso) = O(n3)
Compl(Hungaro) = O(n4)
Sin embargo, siendo “truquero” se puede reducir la complejidad a O(n3).
∴ Compl(Hungaro) = O(n3)
1. ¿Cómo restar m de S y sumar m a Γ(S) en tiempo O(n)?
Agregamos etiquetas: cada fila y cada columna tiene una etiqueta que indica cuántose le suma o resta.
Cambiar las etiquetas es: O(n).
Costo: en vez de chequear if(Ci,j == 0) hay que revisar: (Ci,j − ETi + ETj == 0)
Acá suponemos que el costo de sumar y restar es O(1).
2. ¿Cómo calcular mın{S ∩ Γ(S)} en tiempo O(n)?
Tendremos una etiqueta ψ que por cada columna guardará el mínimo, de la inter-sección de esa columna con S.
∴ Verificar el mínimo de {S ∩ Γ(S)} es simplemente calcular:mın{ψ(y) : ψ(y) 6= 0} = O(n) ya que ψ(y) == 0⇔ y ∈ Γ(S)
Y los ψ(y) los vamos actualizando a medida que examinamos las filas de S.
4.7.5. EJEMPLO DEL MEJORADO (FALTA)
67
5. Códigos de correción de errores
En general un código, sobre un alfabeto A, de longitud n es un subconjunto de An.En general usaremos: A = {0, 1}.Llamaremos “Código”, a un código binario de bloque25.Definición: dados x, y ∈ {0, 1}n la distancia de Hamming entre x e y es:
dH(x, y) = d(x, y) = #{i : xi 6= yi}
El peso de Hamming de x ∈ {0, 1}n es: W (x) = |x| = #{i : xi 6= 0} = d(x, 0n)Claramente: d(x, y) = d(x⊕ y, 0) = |x⊕ y| ⇒ (x⊕ y)i = xi ⊕ yi i.e. ⊕ = suma en Zn2Con ⊕ xor definido de la siguiente manera:
0⊕ 0 = 0
0⊕ 1 = 1
1⊕ 0 = 1
1⊕ 1 = 0
es decir la suma módulo 2.Propiedad d es una distancia.Prueba:1. d(x, x) = 0
2. d(x, y) = 0⇒ x = y
3. d(x, y) = d(y, x)
4. Desigualdad triangular: d(x, y) ≤ d(x, z) + d(z, y) ∀zSean: A = {i : xi = yi}, B = {i : xi = zi}, C = {i : yi = zi}.
Si xi = ziyi = zi
}⇒ xi = yi
∴ i ∈ B ∩ C ⇒ i ∈ A, es decir (B ∩ C) ⊆ A
Aplico De morgan: (B ∩ C) ⊆ A y obtengo:
A ⊆ B ∪ C|A| ≤ |B ∪ C|≤ |B|+ |C|
∴ d(x, y) ≤ d(x, z) + d(z, y)
25“Block code”: código de bloque.
68
Definiciones
Br(x) = {y ∈ Zn2 : d(x, y) ≤ r}
Un código C detecta r errores si: C ∩Br(x) = {x} ∀x ∈ C
Un código C corrige t errores si: Bt(x) ∩Bt(y) = ∅ ∀x, y ∈ C : x 6= y
Notación: δ = mın{d(x, y) : x 6= y : x, y ∈ C}Ejemplos:
1. C1 = {00, 01, 10, 11} ⇒ δ(C1) = 1
2. C2 = {000, 011, 110, 101}
HHHHHHC2
C2 000 011 110 101
000 2 2 2011 2 2110 2101
⇒ δ(C2) = 2
3. C3 = {000000, 010101, 101010, 111111}
HHHHHHC3
C3 000000 010101 101010 111111
000000 3 3 6010101 6 3101010 3111111
⇒ δ(C3) = 3
69
Teorema: sea C código binario y d = δ(C) entonces:
1. C detecta d− 1 errores y no detecta d errores.
2. C corrige bd−12c errores y no corrige bd−1
2c+ 1 errores.
Prueba:
1. Detecta d− 1:
Recordemos que δ es la “menor distancia entre palabras del código ”
Sea x ∈ C, y ∈ Bd−1(x) ∩ C ?⇒ x = y
d(x, y) ≤ δ − 1 < δPero x, y ∈ C ⇒ x = y
No detecta d:
Sean x, y ∈ C : x 6= yd(x, y) = δ
}⇒ y ∈ Bd(x) ∩ C
Como y 6= x
}⇒no detecta d errores.
2. Corrige bd−12c errores:
Sea t = bd−12c.
Sean x, y ∈ C, x 6= y.
Supongamos Bt(x) ∩Bt(y) 6= ∅ ⇒ ∃z ∈ Bt(x) ∩Bt(y)
δ ≤ d(x, y) (22)≤ d(x, z) + d(z, y)
≤ 2t (23)≤ δ − 1
∴ 0 ≤ −1 absurdo
( 22) Ya que x 6= y y las dos están en C.
( 23) Ya que z está en las dos Bolas.
No corrige bd−12c+ 1 errores:
Sean x, y ∈ C : d(x, y) = d, sea e = x⊕ yEntonces e tiene d unos.
Sea e′ con bd−12c+ 1 unos de estos.
Sea z = x⊕ e′
Quiero ver que z ∈ Bb d−12c+1(x) ∩ Bb d−1
2c+1(y) y ya está porque justamente la inte-
sección es no vacía.
Luego d(x, z) = |x⊕ z| = |x⊕ x⊕ e′| = |e′| = bd−12c+ 1
70
d(y, z) = |y ⊕ z| = |y ⊕ x⊕ e′| = |e⊕ e′| = d−(
1 + bd− 1
2c)
?
≤ bd− 1
2c+ 1
Demostración de ?
Si d = 2k + 1 (Impar)d−
(1 + bd−1
2c)
= 2k + 1− 1− k = k = bd−12c < bd−1
2c+ 1
Si d = 2k (Par)d−(1 + bd−1
2c)
= 2k−1− (k−1) = 2k−1−k+ 1 = k = k−1 + 1 = bd−12c+ 1
Suposiciones acerca del medio de transmisión
1. No se pierden ni agregan bits.26
2. Sean:
E+i el evento “Bit i cambia de 0→ 1”.
E−i el evento “Bit i cambia de 1→ 0”.
Entonces: P(E+i
)= P
(E−i). Denotamos Ei al evento: cambia el Bit i.
3. Ei es independiente de Ej ∀i 6= j
4. 0 < P (Ei) = P (Ej) <12
5.1. Cota de Hamming
Teorema: sea C código de longitud n que corrija t errores entonces:
|C| ≤ 2n
1 + n+ . . .+(nt
)Prueba: sea A =
⋃x∈C
Bt(x)
Como C corrije t errores, esa unión es disjunta.
∴ |A| =∑x∈C
|Bt(x)|
Calculemos |Bt(x)|:Para ello definamos:
Sr(x) = {y ∈ Zn2 : d(x, y) = r}26Sólo hay flips de bits.
71
∴ Bt(x) =t⋃
r=0
Sr(x) unión disjunta.
|Bt(x)| =t∑
r=0
|Sr(x)|
y ∈ Sr(x)⇔ d(x, y) = r
⇔ (x⊕ y) = r donde defino (x⊕ y) = e
⇔ ∃ e : |e| = r︸ ︷︷ ︸∈Sr(0)
: y = e⊕ x
∴ Sr(x) = x⊕ Sr(0)⇒ |Sr(x)| = |Sr(0)|
Luego e ∈ Sr(0)⇔ tiene r 1′s y n− r 0′s
De las n ubicaciones hay que elegir las r donde irán los 1′s.∴ |Sr(0)| =
(nr
)∴ |A| =
∑x∈C
|Bt(x)|
=∑x∈C
(t∑
r=0
(n
r
))
=∣∣∣ t∑r=0
(n
r
)∣∣∣ ∗ ∣∣∣C∣∣∣Como A ⊆ Zn2 ⇒ |A| ≤ 2n
⇒∣∣∣ t∑r=0
(n
r
)∣∣∣ ∗ ∣∣∣C∣∣∣ ≤ 2n
⇒∣∣∣C∣∣∣ ≤ 2n
1 + n+ . . .+(nt
)Definición: un código se dice perfecto si C es un subespacio vectorial de Zn2Recordemos que un subespacio vectorial27 se da si:
1. C 6= ∅
2. Si x, y ∈ C ⇒ x⊕ y ∈ C
3. x ∈ C, k ∈ Z2 ⇒ k ∗ x ∈ C27SEV.
72
Pero Z2 = {0, 1}• 1*X = X• 0*X = 0
∴ Trivialmente está en C, bastaría ver que 0 ∈ C.
C 6= ∅ ⇒ ∃x ∈ C ⇒ x⊕ x︸ ︷︷ ︸=0
∈ C
∴ C es lineal si y sólo si (⇔)
C 6= ∅
x, y ∈ C ⇔ x⊕ y ∈ C
Teorema: C lineal ⇒ δ = mın{|x| : x ∈ C, x 6= 0
}Prueba:Sea w = mın{|x| : x ∈ C, x 6= 0}Sean x, y ∈ C : x 6= y con d(x, y) = δ
δ = |x⊕ y|
Como C es lineal x⊕ y ∈ C y x⊕ y 6= 0, pues x 6= y ⇒ δ ≥ wSea ahora x ∈ C, x 6= 0 con |x| = wEntonces w = d(x, 0) , 0 ∈ C pues C es lineal.Como δ es la menor distancia tenemos que δ ≤ w
∴ δ = w
Ejemplos: C1, C2, C3 son obviamente lineales
C1 = {11, 00, 01, 10} = Z22 ⇒ w = δ = 1
C2 = {000, 110, 101, 011} ⇒ w = δ = 2
C3 = {000000, 111111, 101010, 010101} ⇒ w = δ = 3
Notación: si C es lineal k denotará la dimensión de C.
Corolario: si C es lineal de dimensión k ⇒ |C| = 2k
Prueba: obvio pues k = Dim(C)⇒ C ' Zk2 ⇒ |C| = 2k
73
5.2. Matriz generadora
Definición: una matriz generadora G para C es una matriz cuyas filas forman una basede C.
Por lo tanto si C es de dimesión k y longitud n y G es generadora de C entonces G esKxN .
G generadora ⇔ G es KxN, con k = Dim(x) y C = EF (G)Recordemos que: EF (G) = {x ∈ Zn2 : ∃U ∈ Zk2 : x = U ∗G}
Sea G =
1 0 0 1 1 10 1 0 1 0 10 0 1 1 0 0
C = {x1x2x3x4x5x6 : ∃u1, u2, u3 : x = U ∗G}
u1u2u3 ∗G = u1u2u3(u1 ⊕ u2 ⊕ u3)u1(u1 ⊕ u2)
C =
0 0 0 0 0 00 0 1 1 0 00 1 0 1 0 10 1 1 0 0 11 0 0 1 1 11 0 1 0 1 11 1 0 0 1 01 1 1 1 1 0
⇒ δ = 2
En particular:
G =
1
n−1︷︸︸︷I ...
1
Da el código:
C = {x1 . . . xn : xn = x1 ⊕ . . .⊕ xn−1} = {x1 . . . xn : x1 ⊕ . . .⊕ xn−1 ⊕ xn = 0}
“Bit parity Code” tiene δ = 2Otro ejemplo de código lineal: códigos de repetición
C = {︷ ︸︸ ︷x1 . . . xk
︷ ︸︸ ︷x1 . . . xk . . .
︷ ︸︸ ︷x1 . . . xk︸ ︷︷ ︸
r veces
}
n = r ∗ kUna matriz generadora G =
[I I I I I I
]︸ ︷︷ ︸r I′s
⇒ δ = peso mínimo no nulo = r
74
5.3. Matriz de chequeo
Una matriz H se dice matriz de chequeo si C = Nu(H) = {x ∈ Zn2 : Hxt = 0}Propiedad
k
N︷ ︸︸ ︷[
I︸︷︷︸kxk
A︸︷︷︸n−k
]es generadora de C ⇔ n− k
{[At︸︷︷︸k
I︸︷︷︸n−k
]es de chequeo.
Todo código tiene una matriz de chequeo.
Prueba: Hay que ver que EF([IA]
)= Nu
([AtI]
)⊆ Sea x ∈ EF
([I|A]
)⇒ ∃U : x = U [I|A] = U(U.A)
[At|I]xt = [At|I]
[U t
(U.A)t
]= AtU t ⊕ (UA)t
= AtU t ⊕ AtU t
= 0
Entonces x ∈ Nu([AtI])
⊇ EF [I|A] ⊆ Nu([At|I])
Pero Dim(EF ([I|A])) = kDim(Nu([ At︸︷︷︸
kdep.
| I︸︷︷︸n− k
indeptes
])) = k
∴ son iguales
Ejemplo:
G =
1 0 0 1 1 10 1 0 1 0 10 0 1 1 0 0
⇒ H =
1 1 1 1 0 01 0 0 0 1 01 1 0 0 0 1
Entonces Nu(H) =
x1 . . . x6 :
1 1 1 1 0 01 0 0 0 1 01 1 0 0 0 1
x1
x2
x3
x4
x5
x6
= 0
=
x1 . . . x6 :x1 ⊕ x2 ⊕ x3 ⊕ x4 = 0x1 ⊕ x5 = 0x1 ⊕ x2 ⊕ x6 = 0
=
x1 . . . x6 :x4 = x1 ⊕ x2 ⊕ x3
x5 = x1
x6 = x1 ⊕ x2
que es lo que tenía antes.
75
Ejercicio: calcular las palabras del código que genera la siguiente matriz G.
Si G =
1 1 0 1 1 1 0 00 1 1 0 0 0 1 01 0 1 1 0 0 0 1
⇒ H =
1 0 0 0 0 1 0 10 1 0 0 0 1 1 00 0 1 0 0 0 1 10 0 0 1 0 1 0 10 0 0 0 1 1 0 0
en este caso δ = 3
Teorema: sea H la matriz de chequeo de C, si H no tiene la columna 0 ni columnasrepetidas entonces δ ≥ 3. Y por lo tanto corrige al menos un error.
Prueba: supongamos que no (δ < 3)⇒ δ = 1 ó δ = 2
Supongamos δ = 1.
Como C es lineal ⇒ ∃x ∈ C : |x| = 1⇒ ∃i : x = ei28
Como x ∈ C ⇒ Hxt = 0
∴ 0 = Hxt = Heti = H(i) Columna i de H. ⇒ H(i) = 0 absurdo.
Supongamos δ = 2.
Entonces ∃x ∈ C : |x| = 2
Entoces ∃i,j : i 6= j : x = ei ⊕ ej0 = Hxt = Heti ⊕Hetj = H(i) ⊕H(j)
∴ H(i) = H(j) absurdo.
Ejemplo
Sea H =
1 0 0 0 1 1 1 10 1 0 0 0 1 1 10 0 1 0 1 0 1 10 0 0 1 1 1 0 1
H es 4x9
C = Nu(H)
|C| ?= 2k = 25 = 32
k∗= 9− 4 = 5
9 variables - 4 independientes∗= #Columnas−Rango es n porque tengo la identidad.
δ(C)?=
Como H no tiene la columna 0 ni columnas repetidas ⇒ δ(C) ≥ 3Como H(1) +H(5) = H(9)
28Recordemos ei = 0 . . . 0 1︸︷︷︸i
0 . . . 0.
76
Entonces x = 010001001 ∈ C ⇒ δ(C) ≤ 3
∴ δ(C) = 3
Una matriz que cumple esa condición es una matriz r ∗ (2r − 1)Con todas las columnas posibles no nulas de altura r.Entonces C = código de Hamming
H2 = H =
[1 0 10 1 1
]orden posible.
H2 =
{xyz :
x⊕ z = 0y ⊕ z = 0
}= {xyz : z = x = y}= código de repetición
H3 = H =
1 0 0 1 0 1 10 1 0 1 1 0 10 0 1 0 1 1 1
K = 4
H4 = H =
1010101 01101010110011 00100110001111 00011110000000 1111111
K = 11
Propiedad: los Hamming son perfectos.
Prueba: Hay que ver∣∣Hr
∣∣ = 2n
1+n
Donde n = 2r − 1⇒ 1 + n = 2r
∴2n
1 + n=
2n
2r= 2n−r = 22r−1−r = 2k =
∣∣Hr
∣∣Algoritmo para corregir 1 error
Cuando H(i) 6= 0, H(j)
Supongamos que el emisor manda x ∈ C y el receptor recibe y = x⊕ e con |e| ≤ 1.Si e = 0Hyy = Hxt = 0 ∴ y ∈ CSi e = e
⇒ Hyt = Hxt ⊕Heti= 0⊕H(i)
= H(i)
77
∴ El algoritmo es:
1. Calcular Hyt.
2. Si Hyt = 0 Aceptar y.
3. Si Hyt = H(i) Aceptar y ⊕ ei.
4. Si Hyt 6= 0, H(i) ∀i⇒ hubo ≥ 2 errores, pedir retrasmisión.
Ejemplo:
H =
1 0 0 0 0 1 1 1 10 1 0 0 1 0 1 1 10 0 1 0 1 1 0 1 10 0 0 1 1 1 1 0 1
Se recibe: y = 01000100
Hyt = H(2) ⊕H(3) ⊕H(7)
=
0100
⊕
0010
⊕
1101
=
1011
= H(6)
∴ La palabra enviada fue x = y ⊕ e6 = 011001100Pero si recibo z = 000011000
Hzt = H(5) ⊕H(6)
=
0111
⊕
1011
=
1100
6= 0, H(i) ∀i ∴ Hubo ≥ 2 errores
Por ejemplo me pueden haber mandado: 000000000 ó 110011000En el caso del Hamming Hyt siempre va a ser 0 ó algún H(i)
El algoritmo si se usa la matriz con H(i) =
[(i)
Binario
]Es más fácil:
1. Calcular Hyt
2. Si Hyt = 0 aceptar y
3. Sino tomar i: (representación binaria i)= Hyt y acepto y ⊕ ei
78
EjemploH5 tiene n = 25 − 1 = 31⇒ k = 31− 5 = 26∴∣∣H5
∣∣ = 226
Supongamos que llega y = e1 ⊕ e2 ⊕ e11 ⊕ e27 ⊕ e31
Entonces:
Hyt = H(1) ⊕H(2) ⊕H(11) ⊕H(27) ⊕H(31)
=
10000
⊕
01000
⊕
11010
⊕
01101
⊕
11111
=
10000
= H(1)
∴ Mandaron x = y ⊕ e1
Si hubiese sido y = e2 ⊕ e7 ⊕ e17
Hyt =
01000
⊕
11100
⊕
10001
=
00101
= H(20)
∴ Mandaron x = y ⊕ e20
Observación: Hamming más un bit de paridad avisa si hay 2 errores.
Teorema: sea C = Nu(H)⇒ δ(C) = mın{j : ∃j columnas L.D. de H}29
Prueba:≥ : Sea x : |x| = δ(C) = dEntonces ∃i1, i2, . . . , id : x = ei1 ⊕ . . .⊕ eid
0 = Hxt
= Heti1 ⊕ . . .⊕Hetid
= H(i1) ⊕ . . .⊕H(id)
Entonces {H(i1), . . . , H(id)} es L.D.∴ δ ≥ mın{j : ∃j columnas dependientes de H} = j∗
≤ ∃i1, . . . , ij∗ : {H i1 , . . . , H ij∗} es L.D.Entonces ∃c1, . . . , cj∗ no todos nulos tal que: c1Hi1 , . . . , cj∗Hij∗ = 0Como j∗ es el mínimo ⇒ c1, . . . , cj∗ 6= 0 todos no nulos.Como Ci ∈ Z2 ⇒ ci = 1 ∀i∴ H(i1) ⊕ . . .⊕H(ij∗ ) = 0Entonces x ∈ C donde x = ei1 ⊕ . . .⊕ eij∗∴ δ ≤ j∗
29LD: Linealmente dependientes.
79
5.4. Cota Singleton
Corolario: si C es un código lineal de longitud n y dimensión k entonces δ(C) ≤ n−k+1Prueba:Sean d = δ(C), H : C = Nu(H)
d = mın{j : ∃j columnas L.D. de H}= 1 + max{j : Todo conjunto de j columnas es L.I.}≤ 1 + max{j : Existe un conjunto de j columnas L.I.}≤ 1 +Rango(H)
= 1 + n− k
Definición: un Código con δ = n− k + 1 se llama un código MDS30.
5.5. Códigos Cíclicos
Definición: sea W = w0w1 . . . wn−1 definimos Rot(W ) = wn−1w0w1 . . . wn−2
Definición: un código C es cíclico si:
1. Es lineal.
2. Invariante por rotaciones: i.e. W ∈ C ⇒ Rot(W ) ∈ C
Ejemplos
Z2+ Bit de paridad es cíclico C = {000, 110, 101, 011}
C = {000, 100, 010, 001} es invariante por rotación pero no cíclico ya que no eslineal: C[1] + C[2] 6∈ C
C = {000, 100, 011, 111} es lineal pero no es cíclico.
Identificación: w0w1 . . . wn−1 ↔ w0 + w1x+ . . .+ wn−1xn−1
Definición: si P (x), H(x) son polinomios.
P (x) mod H(x) es el resto de dividir P (x) por H(x).
Teorema: si W tiene longitud n entonces:
Rot(W ) = xW (x) mod (1 + xn)
Prueba:
xW (x) = x(w0 + w1x+ . . . wn−1x
n−1)
= w0x+ w1x2 + . . .+ wn−2x
n−1 + wn−1xn
30MDS: maximun distances separable.
80
Aplico módulo 1 + xn
xW (x) mod (1 + xn) = w0x+ w1x2 + . . .+ wn−2x
n−1 + wn−1 (24)= wn−1 + w0x+ w1x
2 + . . .+ wn−2xn−1 (25)
↔ wn−1w0 . . . wn−2
= Rot(W )
( 24) wn−1xn = wn−1(xn + 1)︸ ︷︷ ︸
Cociente
+wn−1︸ ︷︷ ︸Resto
( 25) Conmuto.
Ejemplo
C = {0000, 1010, 0101, 1111}C ↔ {0, 1 + x2, x+ x3, 1 + x+ x2 + x3}
• Tomo w = 1010⇒ Rot(w) = 0101
1 + x2 ⇒ x(1 + x2) = x+ x3 mod (1 + x4) = x+ x3 ↔ 0101
• Tomo w = 0101⇒ Rot(w) = 1010
x+ x3 ⇒ x(x+ x3) = x2 + x4
x2 + x4 mod (1 + x4) = x2 + 1 = 1 + x2 ↔ 1010
Corolario:
Sea C cíclico de longitud n, W (x) ∈ CQ(x) ∈ Z2(x)
}⇒ W (x)Q(x) mod (1 + xn) ∈ C
Propiedad: sea C lineal entonces ∃! polinomio no nulo de grado mínimo.
Definición: si C es cíclico, el único polinomio no nulo de grado mínimo se llama elpolinomio Generador de C, y usualemente se lo denomina G(x).
Prueba:Sean g1, g2 dos de ellos : Gr(g1) = Gr(g2) = tg1 + g2 ∈ C pues C es lineal.Entonces: Gr(g1 + g2)
?= Gr(g1 − g2) < t que era el menor grado.
∴ g1 + g2 = 0⇒ g1 = g2
? : g1(x) = a0 + a1x+ . . .+ at−1xt−1 + 1.xt
: g2(x) = b0 + b1x+ . . .+ bt−1xt−1 + 1.xt
Entonces: g1 + g2 = (a0 + b0) + (a1 + b1)x+ . . .+ (at−1 + bt−1)xt−1 + 0
81
Propiedad: sea G(x) Generador : G(x) 6= 0⇒ Gr(G(x)) ≤ Gr(p(x)) ∀p(x) ∈ C
Teorema: sea C un código cíclico de longitud n,G(x) su polinomio generador entonces:
C ={P (x) ∈ Z2(x) : Gr(P (x)) ≤ n− 1 y G(x)|P (x)
}Prueba:
⊇ Si G(x) dividide a P(x):
G(x)|P (x) ⇒clase pasada
∃q(x) : P (x) = q(x) ∗G(x)⇒ P (x) mod (1 + xn) ∈ C
Como Gr(P (x)) ≤ n− 1⇒ P (x) mod (1 + xn) = P (x)⇒ P (x) ∈ C
⊆ La parte importante
Sea P (x) ∈ C ⇒ Gr(P (x)) ≤ n− 1
Para la segunda condición:
Sean Q(x), R(x) ∈ Z2(x) : P (x) = Q(x)G(x) +R(x): con Gr(R(x)) < Gr(G(x))
Como Gr(R(x)) < Gr(G(x))⇒ Gr(R(x)) < n− 1Gr(P (x)) ≤ n− 1
}⇒ Gr(Q(x)G(x)) ≤ n− 1
Entonces por ⊇ Q(x)G(x) ∈ C
∴ R(x) = P (x)︸ ︷︷ ︸∈C
+Q(x)G(x)︸ ︷︷ ︸∈C
∈ C por ser lineal.
Gr(R(x)) < Gr(G(x)) ≤ n− 1R(x) ∈ C
}⇒ R(x) = 0
∴ P (x) = Q(x)G(x)⇒ G(x)|P (x)
82
TeoremaSea C cíclico de longitud n, y G(x) el polinomio generador de C, con k = Dim(C)
Entonces:
1. Gr(G(x)) = n− k
2. G(x)|1 + xn
3. G(x) = 1 +g1(x) + . . . i.e. g0 = 1
Prueba
1. Sea P (x) : Gr(P (x)) ≤ n− 1
Por el teorema anterior P (x) ∈ C ⇔ ∃Q(x) : P (x) = Q(x)G(x)
Si t = Gr(G(x))⇒ n− 1 ≥ Gr(P (x)) = Gr(Q(x)) +Gr(G(x))︸ ︷︷ ︸=t
∴ Gr(Q(x)) ≤ n− t− 1
Viceversa si P (x) = Q(x)G(x) con Gr(Q(x)) ≤ n− t− 1
Entonces: Gr(P (x)) ≤ n− t− 1 + t = n− 1
∴ P (x) ∈ C
C =
{P (x) : ∃Q(x) :
{Gr(Q(x)) ≤ n− t− 1P (x) = Q(x)G(x)
}Esto da una biyección entre C y
{Q(x) : Gr(Q(x)) ≤ n− t− 1
}= ?
∴ |C| = | ? |= |{Q(x) = q0 + q1x+ . . .+ qn−t−1x
n−t−1}|= 2n−t
Como k = Dim(C)⇒ |C| = 2k ⇒ 2k = 2n−t ⇔ k = n− t⇔ t = n− k
2. Supongamos G(x) = g0 + g1x+ . . .+ gn−k−1xn−k−1 + xn−k
Por lo demostrado en 1. sabemos que es de esa manera.
Multiplico por xk:
xkG(x) = g0xk + g1x
k+1 + . . .+ gn−k−1xn−1 + xn
= (1 + g0xk + . . .+ gn−k−1x
n−1)︸ ︷︷ ︸Rotk(G)
+(1 + xn) (26)
83
( 26) Sumo dos veces 1 en Z2, que es lo mismo que sumar 0.
Como C es cíclico y G(x) ∈ C ⇒ Rotk(G(x)) ∈ CComo G(x) es generador ∃Q(x) : Rotk(G) = Q(x)G(x)
∴ xkG(x) = Rotk(G(x)) + (1 + xn)
= Q(x)G(x) + (1 + xn)
∴ 1 + xn = xkG(x) +Q(x)G(x)
=(xk +Q(x)
)G(x)
Entonces G(x)|1 + xn
3. 1 + xn = V (x)G(x)⇒ 1 = v0g0 ⇔ g0 = 1
Esto da origen a un método para codificar:
Primer método:
Simplemente dada m(x) de grado ≤ k − 1.
Tomo V (x) = m(x)G(x)
Ejemplo:
G(x) = 1 + x2 + x3 : n = 7
¿Cuánto vale k = Dim(C) ?
n− k = Gr(G(x)) ∴ 7− k = 3⇒ k = 4
Por lo tanto el código tiene 24 = 16 palabras.
Supongamos que queremos codificar:
• m = 1011↔ m(x) = 1 + x2 + x3
V (x) = m(x)G(x)
= (1 + x2 + x3)2
= 1 + x4 + x6
↔ 1000101
∴ Mando 1000101
84
• Otra: m = 0110↔ x+ x2
V (x) = (x+ x2)(1 + x2 + x3)
= x+ x3 +��x4 + x2 +��x
4 + x5
= x+ x2 + x3 + x5
↔ 0111010
Esto corresponde a la siguiente matriz generadora:1 g1 g2 . . . gn−k−1 1 0 0 . . . 00 1 g1 g2 . . . gn−k−1 1 0 . . . 00 0 1 g1 g2 . . . gn−k−1 1 . . . 0...
...... . . . . . . . . . . . . . . . . . . ...
0 0 0 0 1 g1 g2 . . . gn−k−1 1
G =
1 0 1 1 0 0 00 1 0 1 1 0 00 0 1 0 1 1 00 0 0 1 0 1 1
Segundo Método
Idea: sea(P (x) +
(P (x) mod G(x)
))= 0 mod (G(x))
G(x)|[P (x) + (P (x) mod G(x))]
∴ Si el Gr(P (x)) ≤ n− 1 ya está: P (x) + (P (x) mod G(x)) ∈ CTruco
Dado m(x) con Gr(m(x)) ≤ k − 1⇒ Gr(xn−km(x)) ≤ n− 1
En definitiva m(x)→ V (x) = xn−km(x) mod G(x) + xn−km(x)
Ejemplos:
• m(x) = 1011↔ 1 + x2 + x3 : n = 7⇒ k = 4
x3m(x) mod G(x) = 0
∴ V (x) = 0 + x3m(x) = x3 + x5 + x6 ↔ 0001011
• m(x) = 0110↔ x+ x2
x3m(x) = x4 + x5
x3m(x) mod G(x)?=
Truco: G(x) = 1 + x2 + x3 ⇒ 1 + x2 + x3 ≡ 0(G(x))
x3 ≡ 1 + x2(G(x))
85
x4 ≡ x+ x3 (G(x))
≡ x+ 1 + x2 (G(x))
≡ 1 + x+ x2 (G(x))
x5 ≡ x+ x2 + x3 (G(x))
≡ x+��x2 + 1 +��x
2 (G(x))
≡ 1 + x (G(x))
∴ x4 + x5 mod G(x) ≡ �1 +�x+ x2 + �1 +�x ≡ x2
∴ V (x) = (x4 + x5) mod G(x) + x4 + x5
= x2 + x4 + x5
↔ 001 0110︸ ︷︷ ︸m(x)
Esto corresponde a la matriz generadora:
G =
xn−k mod G(x) + xn−k
xn−k−1 mod G(x) + xn−k−1
......
......
xn−1 mod G(x) + xn−1
Teníamos:
x3 mod G(x) ≡ 1 + x2
x4 mod G(x) ≡ 1 + x+ x2
x5 mod G(x) ≡ 1 + xx6 mod G(x) ≡ 1 + x2
⇒ G =
1 0 1 1 0 0 01 1 1 0 1 0 01 1 0 0 0 1 00 1 1 0 0 0 1
Es decir obtenemos la matriz G con identidad a derecha.
Una matriz de chequeo H es:
H =
1 0 0 1 1 1 00 1 0 0 1 1 10 0 1 1 1 0 1
En general esto vale claramente: es decir, H(i) = xi mod G(x) : 0 ≤ i ≤ n− 1
86
Ejemplo: sea G(x) = 1 + x2 + x3 + x4 : n = 7Hallar una matriz de chequeo con la identidad a izquierda.
x4 mod G(x) ≡ 1 + x2 + x3
x5 mod G(x) ≡ x+ x3 + x4
≡ x+��x3 + 1 + x2 +��x
3
≡ 1 + x+ x2
x6 mod G(x) ≡ x+ x2 + x3
H =
1 0 0 0 1 1 00 1 0 0 0 1 10 0 1 0 1 1 10 0 0 1 1 0 1
5.5.1. Correción de errores “Error Trapping”
Teorema: sea C cíclico de longitud n que corrige t errores, con G(x) = generador.Asuma que se manda V (x) y llega W (x) : E(x) = V (x)⊕W (x)Con |E| ≤ t, “error corregible”.
Sean Si los “síndromes”: Si(x) = xiW (x) mod (G(x)) : 0 ≤ i ≤ n− 1
Si ∃i : |Si| ≤ t⇒
E(x) = Rotn−i(Si)
= xn−iSi mod (1 + xn)
Prueba de “Error Trapping”:
Observación: Rot(U) mod G(x) = xU(x) mod G(x)Pues Rot(U) = xU(x) mod (1 + xn)∴ ∃Q(x) : xU(x) = Q(x)(1 + xn) +Rot(U)
xU(x) mod G(x) =(Q(x)(1 + xn mod G(x)︸ ︷︷ ︸
0 pues G(x)|1+xn
))
+Rot(U) mod (G(x))
∴ Rot U(x) mod G(x) = xU(x) mod G(x)∴ RotiU(x) mod G(x) = xiU(x) mod G(x)
Sea i : |Si| ≤ t ?
Si(x) = xiU(x) mod G(x)⇒ absurdo.Si(x) = Roti(W (x)) mod G(x)⇒ ∃P (x): Roti(W (x)) = P (x)G(x) + Si(x) �? y � ⇒ Roti(W (x)) ∈ Bt(P (x)G(x)) ♦Pero P (x)G(x) ∈ C
87
Pero W (x) = V (x) + E(x)
Roti(W (x)) = Roti(V (x)) +Roti(E(x)) †Y |Roti(E(x)| = |E(x)| ≤ t
∴ Roti(W (x)) ∈ Bt(Roti(V (x)︸ ︷︷ ︸∈C
) ♣
♦ y ♣ ⇒ Bt(P (x)G(x)︸ ︷︷ ︸∈C
) ∩Bt(Roti(V (x))︸ ︷︷ ︸∈C
) 6= ∅
⇒ P (x)G(x) = Roti(V (x)) ♠Entonces por ♠ y � y † ⇒ Si(x) = Roti(E(x))
∴ E(x) = Rotn−iSi
Ejemplo
G(x) = 1 + x4 + x6 + x7 + x8 : n = 15 con t = 2
Llega W (x) = 1100 1110 1100 010W (x) = 1 + x+ x4 + x5 + x6+ x8 + x9 + x13
Al aplicar mod G(x) solo tengo que resolver los xi : i > k = 7 (los encuadrados).
x8 mod G(x) ≡ 1 + x4 + x6 + x7
x9 mod G(x) ≡ x+ x5 + x7 + x8
≡ x+ x5 +��x7 + 1 + x4 + x6 +��x
7
≡ 1 + x+ x4 + x5 + x6
x10 mod G(x) ≡ x+ x2 + x5 + x6 + x7
x11 mod G(x) ≡ x2 + x3 + x6 + x7 + x8
≡ x2 + x3 +��x6 +��x
7 + 1 + x4 +��x6 +��x
7
≡ 1 + x2 + x3 + x4
x12 mod G(x) ≡ x+ x3 + x4 + x5
x13 mod G(x) ≡ x2 + x4 + x5 + x6
S0 = W (x) mod G(x)
= 1 + x+ x4 + x5 + x6 + 1 + x4 + x6 + x7︸ ︷︷ ︸x8 mod G(x)
+ 1 + x+ x4 + x5 + x6︸ ︷︷ ︸x9 mod G(x)
+x2 + x4 + x5 + x6︸ ︷︷ ︸x13 mod G(x)
= 1 + x2 + x5 + x7
∴ |S0| = 4 > 2
88
Continúo calculando |S1|, hasta encontrar uno tal que |Si| ≤ 2
S1 = x(W (x) mod G(x))
= x(
1 + x2 + x5 + x7)
= x+ x3 + x6 + x8
= x+ x3 +��x6 + 1 + x4 +��x
6 + x7
= 1 + x+ x3 + x4 + x7
S2 = 1 + x+ x2 + x3 + x5 + x6 + x7
S3 = 1 + x+ x2 + x3 + x4
...S6 = x3 + x4 + x5 + x6 + x7
S7 = x4 + x5 + x6 + x7 + x8
=��x4 + x5 +��x
6 +��x7 + 1 +��x
4 +��x6 +��x
7
= 1 + x5
∴ |S7| = 2 ≤ 2 = 7
Entonces: E(x) = xn−iSi mod (1 + xn)
= x15−7S7 mod (1 + x15)
= x8(1 + x5) mod (1 + x15)
= x8 + x13
∴ V (x) = W (x) + E(x) = 1 + x+ x4 + x5 + x6 + x9
Ejercicio: sea G(x) = 1 + x2 + x4 + x5 + x6 + x10 + x11 : n = 23 con t = 3
W (x) = 1 + x7 + x8 + x9 + x12 + x13
Respuesta:
V (x) = 1 + x8 + x9 + x12 + x13 + x14 + x15 + x16
Con S16 = 1 + x8 + x9
Definición:
Polinomio Chequeador H(x) =1 + xn
G(x)
Propiedad (ejercicio)
W (x) ∈ C ⇔ H(x)W (x) mod (1 + xn) = 0 : Gr(W (x)) ≤ n− 1
89
6. P-NPDefinición: un “problema” de decisión es un problema cuyas únicas respuestas posibles
son Sí o No (alternativamente 1 ó 0).Ejemplos
Matching: dado un grafo G ¿tiene G un matching perfecto?
Primo: dado un n ∈ N ¿es n primo?
K-color: dado un grafo G ¿es χ(G) ≤ k?
Semiformalización de “problema de decisión”.Un conjunto I (conjunto de instancias del problema y una función Π : I → {Sí,No}Alternativamente, tomando el conjunto de instancias positivas.
S = {x ∈ I : Π(x) = Sí}
Se puede pensar que un problema es un par (I,S) con S ⊆ I.En general, dado x ∈ I tenemos una “medida” del “tamaño” de x.En general, # de bits necesarios para representar a x, o algo ligado a eso.Lo denotaremos |x|.Por ejemplo si I = {G : G es un grafo finito}, podemos tomar |G| = #de vértices.Si I = N⇒ |n| = dlog(n)e = #bits de n
6.1. La clase P
P = clase de problemas de decisión tal que existe un polinomio P (x), y un algoritmoA tal que A resuelve el problema para x ∈ I en tiempo O(P (x))
Resolver es que: A(x) =
{Sí Si Π(x) = SíNo Si Π(x) = No
O bien en la forma “{I,S}” A(x) = Sí ⇔ x ∈ SEjemplos:
2− color ∈ P
Matching bipartito: como Matching con instancia reducida a grafos bipartitos.
Vimos que Matching bipartito31 ∈ P
6.2. La Clase NP
NP no significa “No Polinomial”. (de hecho P ⊆ NP ).
NP significa: “Non deterministic Polynomial”.
Otra forma de definir esta clase que es la clase de problemas de decisión para los cualesexisten “certificados” que verifican la respuesta “Sí” en tiempo polinomial.
31Edmonds probó que Matching ∈ P .
90
Formalmente
(I, S) ∈ NP ⇔ ∃j,∃t ⊆ IxJ y ∃P (x) tales que:
1. (IxJ, T ) ∈ P
2. Dado x ∈ I vale x ∈ S ⇔ ∃y ∈ J :
{(x, y) ∈ T|y| ≤ P (|x|)
6.3. Co-NP
Definición: Co-NP = problema de decisión tal que el “complemento” está en P.Ejemplo: Primo ∈ Co-NPCertificado para “NO” una factorización.(En 1976 se probó que Primo ∈ NP) y en 2002 se probó que PRIMO ∈ P .
“Complemento de Π”
Es Π(x) =
{No Si Π(x) = SíSí Si Π(x) = No
ó (I, S)→ (I, I − S)
k-color ∈ NP ∀k
Certificado: dado un coloreo con k colores ver que es propio es: O(m) = O(n2)Observación:
Claramente P ⊆ NP .
“El” problema del millón es ¿P=NP?
6.4. SAT
Un problema importate: SATUna variable booleana x es una variable que sólo puede tomar dos valores 0 ó 1.Dado un conjunto de variables Booleanas: x1, . . . , xn.Un literal: es una de esas variables o la negación de ellas. (x = 1⊕ x).Una claúsula: (“Clause”) es un “∨” de literales (“Disjunción”).Ejemplo: x1 ∨ x2 . . .Una expresión Booleana en forma Conjuntiva Normal32, es una conjunción (“∧”) de
claúsulas.Ejemplo:
(x1 ∨ x2) ∧ (x1 ∨ x3 ∨ x7) ∧ (x2 ∨ x3 ∨ x4)
SAT es:33 dada B en CNF:
¿∃ un asignamiento de valores a las variables que la vuelva verdadera?32CNF: Conjuctive Normal Form.33Nota: “SAT”, sería sin pedir CNF, esto sería “CNF-SAT, pero todo el mudo lo llama SAT”.
91
SAT ∈ NP : Certificación una valuación.Otras formas de SAT están en P.
DNF − SAT ∈ P : ∨′s de ∧′s
Xor − SAT ∈ P : ∧′s de ⊕′s (Xors)
Pero SAT no se sabe, de hecho Cook probó que SAT ∈ P ⇒ P = NPNo probaremos este teorema pero daremos una “olfateada” al mismo.La clave está en lo que Cook llamó: “Reducción Polinomial”.Que ahora también se conoce como “Reducción de Cook”.
6.4.1. Reducción Polinomial
Definición: dados dos problemas de decisión π = (I, S) , τ(J, T )Diremos que π se reduce a τ (π ≤P τ) si:∃ Polinomio P (x) y una función ψ : I → J :
1. Calcular ψ(x) es O(P (x)) y ψ(x) es polinomial en x.
2. x ∈ S ⇔ ψ(x) ∈ τ i.e. π(x) = “Sí” ⇔ τ(ψ(x)) =“Sí”.
Ejemplos sencillos:
Tonto y no del todo correcto:
• π : Dada ax2 + bx + c = 0 ¿tiene solución ∈ R?• τ : Dado t ∈ R ¿es t ≥ 0?
Entonces: π ≤P τ tomando t = b2 − 4 ∗ a ∗ c
Otro ejemplo
• π : Dada A ∈ Qn∗n ¿A es invertible?
• Dado t ∈ Q ¿es t 6= 0?
π ≤P τ tomando Det(A) = t.
6.4.2. k − color ≤P SAT
Teorema: k − color ≤P SATPrueba: Dado un grafo G debemos construir polinomialmente una B ∈ CNF tal que:
χ(G) ≤ k ⇔ B es satisfactible i.e. ∃ un asignamiento que la vuelve verdadera.Sea n = # vértices de G.Tomemos variables xi,j : 1 ≤ i ≤ n, 1 ≤ j ≤ kPara i = 1, . . . , n defino Ci = xi,1 ∨ xi,2 ∨ . . . ∨ xi,k
C = C1 ∧ C2 ∧ . . . ∧ Cn
92
Di =∧j, rj < r
j, r = 1, . . . , k
(xi,j ∨ xi,r
)
D = D1 ∧ . . . ∧Dn
Sea Fi,j,l = xi,j ∨ xl,j
F =n∧
i, l = 1il ∈ E
k∧j=1
Fi,j,l
Tomo B = C ∧D ∧ F es O(n+m)
Ahora hay que probar que χ(G) ≤ k ⇔ B es satisfactible.⇒ Sea C un coloreo propio con k colores de G.Debemos construir un asignamiento de valores a las variables.xi,j → xi,j ∈ {0, 1}
Definimos xi,j =
{1 Si C(i) = j0 c.c.
Debemos ver que : B = B(xi,j) = 1
Todo vértice tiene un color
⇒ ∀i ∃j ≤ k : C(i) = j⇒ ∀i ∃j ≤ k : xi,j = 1⇒ ∀i : xi,1 ∨ xi,2 ∨ . . . ∨ xi,k︸ ︷︷ ︸
Ci
= 1
∴ C = C1 ∧ . . . ∧ Cn = 1
Todo vértice tiene un sólo color
∀i ∃! j ≤ k : C(i) = j∴ ∀i @j 6= r : C(i) = j, C(i) = r∀i, ∀j < r : C(i) 6= j ∨ C(i) 6= rxi,j = 0 ∨ xi,r = 0o lo mismo: xi,j = 1 ó xi,r = 1
xi,j ∨ xi,r = 1 ∀i, ∀j < r ⇒ D = 1
Finalmente como el coloreo es propio
∀il ∈ E Tenemos C(i) 6= C(l)i.e. ∀il ∈ E,@j : C(i) = C(l) = j⇒ ∀il ∈ E,∀j :(C(i) 6= j ó C(l) 6= (j)︸ ︷︷ ︸
xi,j=1 ó xi,r=1
93
∴ ∀il ∈ E,∀j : xi,j ∨ xi,r = 1⇒ F = 1
B = C ∧ D ∧ F = 1
Fin (⇒)
⇐ Ahora sabemos que existe xi,j con B = 1 y queremos ver que: χ(G) ≤ k
B = 1⇒
∣∣∣∣∣∣∣C = 1 ⇒ ∀i, ∃j : xi,j = 1 (?)
D = 1 ⇒ ∀i, ∃!j : xi,j = 1 definimos C(i) = el único j con xi,j = 1
F = 1 ⇒ ∀ij ∈ E,C(i) 6= C(l) ∴ C es propio? Cuento con la demostración de la ida.
Observación: Cook probó π ∈ NP ⇒ π ≤P SATCorolario: SAT ∈ P ⇒ P = NP
6.5. NP Completo
Definición: un problema τ es NP completo si:
1. τ ∈ NP
2. π ∈ NP ⇒ π ≤P τ
Un año después de Cook, Karp dió otros 23 problemas NP completos, en la actualidadhay más de 2000.
La clave es lo siguiente: Si τ ∈ NP Completo y τ ≤P τ ∗ : τ ∗ ∈ NPEntonces τ ∗ es NP Completo.La demostración sale del hecho que ≤P , es transitiva, ya que es una composición de
polinomios.
A continuación daremos algunos ejemplos NP completos.
6.5.1. 3-SAT es NP completo
3-SAT es como SAT pero en cada claúsula debe haber exactamente 3 literales distintos.
3-SAT es NP completo
Prueba: probaremos que SAT ≤P 3-SAT (por Cook).Es decir dada B en CNF debemos construir polinomialmente una B en CNF pero que
tenga exactamente 3 literales por claúsula y tal que B sea satisfactible ⇔ B′ lo es.Supongamos que B = D1 ∧ . . . ∧Dm : Di claúsulas.Variables de B = x1, . . . , xnDada una claúsula D arbitraria, definiremos una conjunción de claúsulas E (con más
variables), y luego tomaremos:
B′ = E1 ∧ E2 ∧ . . . ∧ Em donde Ei corresponde a Di.
94
Cada Ei crea sus propias variables extras.Construcción:
Si D tiene 3 literales: E =D
Si D tiene 2 literales : D = L1 ∨ L2
Tomamos una variable extra y 6∈ {x1, . . . , xn}.Tomamos E = (L1 ∨ L2 ∨ y) ∧ (L1 ∨ L2 ∨ y)
Claramente si L1 ∨ L2 = 1⇒ (L1 ∨ L2 ∨ y) ∧ (L1 ∨ L2 ∨ y) = 1
Viceversa:
Si ∃{x1, . . . , xn, y}
Tal que (L1 ∨ L2 ∨ y) ∧ (L1 ∨ L2 ∨ y) = 1
Entonces si:
• y = 0⇒ L1 ∨ L2 = 1
• y = 1⇒ L1 ∨ L2 = 1
Observación: probamos un poco más de lo que dijimos
∃~x : D(~x)
= 1⇔ ∃~y : E(~x, ~y)
= 1
Esto valdrá en todos los casos.
D tiene un literal: i.e. D = L
Tomamos:
E = (L ∨ y1 ∨ y2) ∧ (L ∨ y1 ∨ y2) ∧ (L ∨ y1 ∨ y2) ∧ (L ∨ y1 ∨ y2)
Y es casi obvio que:
L = 1⇔ E = 1 i.e. cualquier y1, y2
D tiene ≥ 4 literales.
D = L1 ∨ L2 ∨ . . . ∨ LkEntonces tomamos k − 3 variables nuevas: y1, y2, . . . , yk−3 polinomial en k
K >> 4:
E = (L1∨L2∨y1)∧(y1∨y2∨L3)∧(y2∨y3∨L4)∧. . .∧(yk−4∨yk−3∨Lk−2)∧(yk−3∨Lk−1∨Lk)
95
#claúsulas = k − 2 ∴ lineal en k.Supongamos ahora D = 1⇒ ∃j : Lj = 1Definamos:
y1 = y2 = . . . = yj−2 = 1
yj−1 = yj = . . . = yk−3 = 0
E =(L1 ∨ L2 ∨ y1︸︷︷︸=1
) ∧ (y1 ∨ y2︸︷︷︸=1
∨L3) ∧ . . . ∧ (yj−2 ∨ yj−1 ∨ Lj︸︷︷︸HIP=1
) ∧ (yj−1︸︷︷︸=1
∨yj ∨ Lj+1)
∧ . . . ∧ (yk−3︸︷︷︸=1
∨Lk−1 ∨ Lk)
∴ E = 1Veamos la vuelta: supongamos que E = 1Queremos ver que D = 1. Supongamos que no.D = 0⇒ L1 ∨ . . . ∨ Lk = 0 ⇒ Lr = 0 ∀rNos queda: E = y1 ∧
(y1 ∨ y2
)∧(y2 ∨ y3
)∧ . . . ∧
(yk−4 ∨ yk−3
)∧ yk−3
Como E = 1Tenemos:
y1 = 1
y1 ∨ y2 = 1
}⇒ y2 = 1
y2 ∨ y3 = 1
⇒ y3 = 1
y3 ∨ y4 = 1
. . .⇒ yk−4 = 1
. . . yk−4 ∨ yk−3 = 1
⇒ yk−3 = 1
yk−3 = 1
Absurdo
6.5.2. 3-color es NP completo
Teorema: 3-color es NP completoPrueba: veremos que 3-SAT ≤P 3-color.Es decir necesitamos : B(3-CNF )→ GSea B = D1 ∧ . . . ∧Dm con variables {x1, . . . , xn}.Dj = L1,j ∨ L2,j ∨ L3,j
Vamos a construir G = (V,E) con |V |, |E| polinomiales en n,mYa damos la construcción en general, primero un ejemplo.
96
6.5.3. Ejemplo 3-SAT ≤P3-color
B = (x1 ∨ x2 ∨ x3) ∧ (x2 ∨ x3 ∨ x4)
t
'
x1 _
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee x1
ffffffffffffffffffffffffffffffffff x2 _
nnnnnnnnnnnnnnnnx2
��������x3 _
????????x3
PPPPPPPPPPPPPPPPx4 _
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXx4
YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY
s
||||||||||||||||||||
mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
hhhhhhhhhhhhhhhhhhhhhhhh
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
e1,2
���������������e2,2
333333333333333
e1,1
,,,,,,,,,,,,,,,,,,,,,,e1,3
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuue2,1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAe2,3
�
i1,2
CCCCCCCC
{{{{{{{{
�
i2,2
CCCCCCCC
{{{{{{{{
�
i1,1
�
_i1,3
�
i2,1
�
i2,3
�
_
En general:
V = {s, t} ∪ {x1, . . . , xn, x1, . . . , xn} ∪ {W1, . . . ,Wm}
Con Wj = {ej,1, ej,2, ej,3, ij,1, ij,2, ij,3}
E = {st}∪{txk, txk, xkxk}nk=1∪T1∪. . .∪Tm∪E1∪. . .∪Em∪F1∪. . .∪Fm∪{sej,k}1 ≤ j ≤ mk = 1, 2, 3
Donde:Tj = {ij,1ij,2; ij,2ij,3; ij,3ij,1}
Ej = {ej,1ij,1; ej,2ij,2; ej,3ij,3}
Fj = {ej,1L1,j; ej,2L2,j; ej,3L3,j}
G tiene: 2 + 2n+ 6m vértices, polinomial.G tiene: 1 + 3n+ 3m+ 9m = 1 + 3n+ 12m lados, polinomial.
Hay que ver B satisfactible ⇔ χ(G) ≤ 3
(Como G tiene triángulos χ(G) ≤ 3⇔ χ(G) = 3)
97
Veamos ⇐ primero:Sea C un coloreo de G de 3 colores queremos dar un asignamiento de valores a las
variables tal que: B(~x) = 1Definamos:
xk =
{1 Si C(xk) = C(s)0 Sino
Queremos ver que B(~x) = 1
∴ ∀j basta ver: Dj(~x) = 1
∴ Hay que probar ∀j L1,j ∨ L2,j ∨ L3,j = 1Veamos como Tj es un triángulo entonces los 3 colores están representados.Entonces:
∃k : C(ij,k) = C(t)
ij,kej,k ∈ E ⇒ C(ej,k) 6= C(ij,k) = C(t)
sej,k ∈ E ⇒ C(ej,k) 6= C(s)
st ∈ E ⇒ C(s) 6= C(t)
C(ej,k) = “tercer color”
Como ej,kLj,k ∈ E ⇒ C(Lk,j) 6= “tercer color”tLk,j ∈ E ⇒ C(Lk,j) 6= C(t)
}⇒ C(Lk,j) = C(s)
Por definición Lk,j = 1 Fin ⇐⇒ Dado un asignamiento de valores ~x : B(~x) = 1 debemos construir un coloreo propio
con 3 colores.Definimos: C(s) = 1 , C(t) = 2⇒ st No Crea Problemas (NCP).Coloreamos:
C(xi) = xiC(xi) = 1⊕ xi
}⇒ xixi (NCP )
Además:C(xi), C(xi) ∈ {0, 1}
C(t) = 2
}⇒ txi, txi (NCP )
Como B(~x) = 1
⇒ Dj(~x) = 1 ∀j = 1, . . . ,m
i.e. L1,j ∨ L2,j ∨ L3,j = 1
⇒ ∀j,∃k : Lk,j = 1 (si hay más de uno elijo alguno)Coloreamos:
C(ej,k) = 0
Como Lk,j = 1⇒ C(Lk,j) = 1
}⇒ Lk,jej,k (NCP )
Y coloreo:C(ej,r) = 2 : r 6= kC(Lr,j) ∈ {0, 1}
}⇒ ej,rLr,j (NCP )
98
Como:C(ej,k) = 0C(ej,r) = 2C(s) = 1
⇒ sej,k y los sej,r (NCP )
Finalmente coloreamos:
C(ij,k) = 2C(ej,k) = 0
}⇒ ej,kij,k (NCP )
Y coloreamos: C(ij,r) = 0 ó 1 : r 6= k
∴ ij,r︸︷︷︸0 ó 1
ej,r︸︷︷︸=2
(NCP )
Finalmente el triángulo:ij,2
AAAAAAAA
}}}}}}}}
ij,1 _ij,3
Tiene un vértice de color 2 el (j, k) uno de color 0 y otro de color 1 (NCP )
99
6.5.4. 2-SAT ∈ P
D[j] = Claúsula j-ésima, un par de números (L,R).Registros x[0] , . . . , x[n-1] ; x[n] , . . . , x[2n-1]
Representan x1 , . . . , xn ; x1 , . . . , xn
2-SAT
1 V ariables : x0, . . . , xn−12 SETEAR(v) : //MACRO3 X[v] = 1;4 X[2n− 1− v] = 0;5 Q = Q ∪ P [v] ∪ P [2n− 1− v]6 N = { 0 , . . . , n−1} ; // Var iab l e s no se t eadas7 M = { 0 , . . . ,m−1} ; // Dis junc iones no s a t i s f e c h a s8 Q = ∅ ;9 for ( i = 0 , i < 2n , i++){10 x [ i ] = −1 ;11 P[ i ] = { j ∈ M : i aparece en D[ j ] } ;12 }13 for ( j = 0 , j < m, j++){ Sat [ j ] = 0 ; }14 while ( N 6= ∅)15 Tomar i ∈ N, SETEAR( i ) ;16 while (Q 6= ∅) {17 E l e j i r j ∈ Q;18 L ,R: D( j ) = {L ,R} ;19 i f ( ( x [L ] == 1) | | ( x [R] == 1) ) {20 Sat [ j ] = 1 ;21 Remover j de Q; //Pero no de M22 } else i f ( x [R]<0){23 SETEAR(R) ;24 /∗ Si X[R] < 0 , debe ser x [ i ] = 0 entonces debo as i gnar x [R]
= 1∗/25 } else i f ( x [ i ]<0){26 SETEAR(L)27 /∗Este es tado es cuando queda e l caso 00 , por l o tanto nos
equivocamos coon e l s e t eo de x [ i ]= 1 , por l o tanto hayque cambiar ∗/
28 } else i f ( x [ i ] == 1) { //Anular todos29 ∀t ∈ N, ∀s ∈M {30 SAT( s ) = 0 ;31 x [ t ] = x [ 2 n−1−t ] = −1;32 }33 Q = ∅ ;34 SETEAR[2n−1− i ]35 } else36 return "NO SAT"37 }38 ∀i ∈ N, ∀j : SAT [j] = 1{39 Borrar j de P[ i ] y P[ 2 n−1− i ]40 }41 }42 Return "SAT"
100
6.5.5. HORN-SAT
HORN-SAT es como CNF-SAT pero donde cada claúsula tiene a lo sumo un literal“positivo” : xi → “positivo” y xi → “negativo”
Teorema: HORN -SAT ∈ PPrueba:
x1 ∨ x2 ∨ . . . ∨ xk ∨ xk+1 ≡ x1 ∧ x2 ∧ . . . ∧ xk ∨ xk+1
≡ x1 ∧ x2 ∧ . . . ∧ xk ⇒ xk+1
El algoritmo empieza seteando todas las variables a false.Recordamos: true⇒ true ≡ trueFalse⇒ ? ≡ truetrue⇒ false ≡ falseEntonces todas las disjunciones de la forma:(
x1 ∧ x2 ∧ . . . ∧ xk︸ ︷︷ ︸false
⇒ xk+1︸︷︷︸false
)van a ser true
Las de la forma:
x1 ∨ x2 ∨ . . . ∨ xk ≡ x1 ∨ x2 ∨ . . . ∨ xk ∨ false≡ x1 ∧ x2 ∧ . . . ∧ xk︸ ︷︷ ︸
false
⇒ false
≡ true
El único problema son las disjunciones de la forma:
x ≡ true⇒ x︸︷︷︸false
≡ false
Si hay una de esas, listo.Si hay, seteamos estas variables a true (permanentemente).Luego de eso se hacen true todas las variables xk+1 que estén en una disjunción de la
forma: x1 ∧ . . . ∧ xk ⇒ xk+1
En donde x1, . . . , xk sean true.Si en algún momento se llega a una contradicción, no se puede satisfacer.La contradicción vendría de alguna de la forma:
x1 ∨ x2 ∨ . . . ∨ xk con todas las xi true
Ejemplo:(x ∨ y ∨ z ∨ w) ∧ (x ∨ y) ∧ (z ∨ w ∨ x) ∧ (x ∨ z) ∧ (y ∨ z) ∧ yy = 1⇒ z = 1⇒ x = 0, z = 0Pero supongamos que siguiera con . . . ∧ (y ∨ z ∨ U) ∧ (u ∨ x)
y = 1⇒ z = 1⇒ U = 1⇒ x = 0∴ No se puede resolver x ∨ y
101
7. Introducción a la Inteligencia Artificial
7.1. Hill Climbing
7.2. Simulated Annealing
7.3. Algoritmos Evolutivos
Tomar una población de posibles soluciones (por ejemplo una cadena de bits).
1. Elegir un miembro de la población.
2. Cambiar cada bit de ese miembro y evaluar si el cambio mejora la solución.
Nos quedamos con el mejor:
Si hay uno repetir 2.
Sino, guardar el individuo en un conjunto B, y repetir 1.
3. Finalmente elegir el mejor de B.
Este algoritmo es evolutivo pero no genético
7.4. Algoritmos Genéticos
Genético ⇒ Interacción entre individuos.
Los algoritmos genéticos34, se basan más o menos en la evolución biológica.Cada individuo, tiene cromosomas, que forman cadenas de ADN, se dividen en “Genes”
que codifican un aspecto del individo, por ejemplo el color de los ojos.El conjunto de cromosomas se llama “genotipo” y las características inducidas en el
individuo por la acción del genotipo y el medio ambiente es el “fenotipo”.También podemos distinguir entre especies haploides y diploides, (humanos).Los cromosomas vienen en pares con genes dominantes y recesivos.Haploide: los cromosomas no están emparejados.En la mayoría de los algoritmos genéticos los individuos son haploides y con un solo
cromosoma.A veces a los individuos se les llama “cromosomas”. Pero a veces el individuo tiene algo
más que cromosomas.Una parte importante de un AG es codificar el problema con cromosomas.Un cromosoma será una cadena de símbolos, usualmente bits o un vector de números.Ejemplos:
1. Maximizar una función en R3 la codificación puede ser una cadena de 3 números.
2. Hallar un recorrido de n ciudades que no repita ninguna y minimice la distancia(TSP)35. Codifica una cadena con el nombre de cada ciudad (sin repetir).
34AG.35Travel Salesman Problem.
102
En todo AG necesitamos una función a maximizar, llamada función de “Fitness36”.En los ejemplos anteriores:
1. f es la función.
2. Sería la f del costo del camino.
A veces como en TSP no toda cadena representa una solución, por ejemplo puede serque no haya camino entre las dos ciudades.
Generalmente se soluciona “creativamente”, por ejemplo en TSP, podemos suponer quehay ruta entre 2 ciudades cualesquiera, asignándole, un peso muy grande si no existe enla realidad. Pero en otros problemas esto es más delicado.∴ Es la primera característica de un AG.1) Una población de individuos con cromosomas y una función de fitness adecuada.Otra característica es:2) Selección de individuos a reproducirse mediante la fitness.Un AG tendrá lo que se llaman “Generaciones”.
Población Inicial (generación 0)⇓
Algo⇓
Población nueva (generación 1)⇓
Algo⇓
Población nueva (generación 2)
7.4.1. Selección
Los individuos a reproducirse se seleccionan de a pares y luego viene lo esencial:3) Los progenitores producen nuevos individuos (“offspring”) por medio del cruzamiento
(“crossover”) de genes.4) Los “offspring” son sometidos a mutaciones al azar. Operador mutación.Esto depende de una tasa de mutación, generalmente baja ≈ 0, 0015) Debe haber un operador de Selección entre Progenitor 1, Progenitor 2, offspring 1
y offspring 2. (es decir tengo que matar a 2).6) Debe haber una condición de terminación.Por ejemplo, un número máximo de generaciones.
7.5. Ejemplo de un AG
Problema: dado un número natural escribirlo como suma, resta, producto y divisiónde los dígitos: 0, 1, . . . , 9 quizás repetidos (asociando a izquierda).
36Adaptabilidad.
103
7.5.1. Codificación del ejemplo
Una posibilidad sería una cadena de símbolos del alfabeto A ={
0, . . . , 9,+, ∗, /}pero
que debe tener: N◦ Símbolo N◦.Problema: crossover y mutaciones se pueden complicar.Una posibilidad es hacer cadenas de pares (N◦,operador) u (operador, N◦) y suponer
que empezamos con 0.Otra posibilidad: simplemente usar cadenas de bits, entonces un gen serán 4bits.
0000→ 0 1011→ −0001→ 1 1100→ ∗... 1101→ /
1001→ 9 1110→ Nada
1010→ + 1111→ Nada
El cromosoma será el genotipo, el fenotipo en cambio tiene que ser una cadena:0 Símbolo N◦ Símbolo . . . que además no tenga “/0”.
Genotipo→ Fenotipo
Si es 14 ó 15 lo descartamos.
Si es N◦ y se requiere un Símbolo lo descartamos.
Si es un Símbolo y se requiere un N◦ lo descartamos.
Sino se usa.
Si tenemos un “/0” cambiar 0 por 1.
7.5.2. Fitness del ejemplo
Fitness será algo como : =
{ 1∑Fenotipo−31
si∑Fenotipo 6= 31
“∞” si∑Fenotipo = 31
7.5.3. Entrecruzamiento del ejemplo
Crossover: Singled Point CrossoverProgenitor 1: b1b2b3 . . . b400
Progenitor 2: b1b2b3 . . . b400
Elijo al azar un número x : 0 < x < 400 y obtengo:Por ejemplo x = 127Offspring 1: b1b2b3 . . . b127b128 . . . . . . b400
Offspring 2: b1b2b3 . . . b127b128 . . . . . . b400
7.5.4. Mutación del ejemplo
Para cada bit lo cambio con probabilidad p.
104
7.5.5. Selección del ejemplo
Mato a los padres, me quedo con los offsprings.
7.5.6. Operadores de Selección
Asumimos que cada individuo tiene una fitness Fi calculada.Queremos seleccionar de los n individuos, quiénes se van a reproducir, tomando, en
cuenta las Fi.Hay varios métodos, los más usados caen en un categoría llamada:
“Fitness Proportional Selection”
Sea F =
n∑i=1
Fi
nla fitness promedio.
Sea Ei = Fi
F= # esperado de veces que el individuo i, debería ser seleccionado de
acuerdo a su fitness.
Ei = n ∗ Fin∑j=1
Fj
Queremos seleccionar i con un método que lo elija cerca de Ei veces.El primer método propuesto por Holland, hace esto lo más cercano posible se llama
“Stochastic Sampling With Replaciment” (SSWR), o Ruleta.Elijo un número al azar y elijo ese número.Calculando las E ′is se toma un número al azar A entre 0 y n y se toma el primer
i :i∑
j=1
Ej > A
Ejemplo: 6 individuos.
“Fitnesses”F1 = 17,118F2 = 9,51F3 = 36,138F4 = 22,824F5 = 91,296F6 = 13,314
∴6∑j=1
Fj = 190, 200
Lo más simple es tomar un número al azar entre 0 y 1 que por ejemplo tomandor ∈ (0, 1) y calculo r ∗ 190, 2.
Para entender mejor otros conceptos, haremos el cálculo sin embargo con los E ′is
Ei =Fi
190, 2∗ 6⇒
E1 = 0, 54E2 = 0, 30E3 = 1, 14E4 = 0, 72E5 = 2, 88E6 = 0, 42
105
Ruleta: # al azar: entre 0 y 1:0, 15 0, 7 0, 22 0, 91 0, 46 0, 63Multiplico por n = 60, 90 4, 2 1, 32 5, 46 2, 76 3, 78
Ahora calculo:i∑
j=1
Ej ⇒
1→ 0, 542→ 0, 843→ 1, 98 1• 3•
4→ 2, 705→ 5, 58 2•, 4•, 5•, 6•
6→ 6Este método puede producir lo que se llama “Crowding” de la población por un
individuo o grupo de individuos y “convergencia temprana” a un máximo local, ademástiene otro problema.
Hay 3 medidas de un operador de selección:
Bias.
Spread.
Eficiencia computacional.
Bias: es la diferencia entre Fi
Fiy el valor esperado de veces que el individuo será selec-
cionado con el método propuesto.
Bias(Ruleta) = 0.
Spread: rango de offspring que un individuo puede tener:
Ruleta(Spread(i)) = [0, n].
Conclusión: ruleta tiene Bias = 0 y Spread Máximo (malo).Eficiencia: buena, pero se necesitan n randoms.Alternativa a Ruleta: “Stochastic Universal Sampling” (SUS), usa un sólo número al
azar, digamos r y toma los puntos: r, r + 1, r + 2, . . . , r + (n− 1).
En nuestro caso: r = 0, 150,15 1,15 2,15 3,15 4,15 5,15↓ ↓ ↓ ↓ ↓ ↓I1 I3 I4 I5 I5 I5
Entonces nos queda:1→ 1 (0, 54)2→ 0 (0, 34)3→ 1 (1, 14)4→ 1 (0, 72)5→ 3 (2, 88)6→ 0 (0, 42)
Bias = 0.
Pero Spread(i) = {bEic, dEie}.
Y un factor extra que tengo que elegir a quién reproduzco con quién.
106
7.5.7. Remainde Methods (Métodos del “Resto”)
El individuo, se selecciona determinísticamente.Se toma bEic veces.Los n−
n∑i=1
bEic posibles se llenan con algún otro método.
Por ejemplo se usan los restos: Ri = Ei − bEic y se distribuyan usando Ruleta o SUS.
Ejemplo:
bE1c = b0, 54c = 0 → R1 = 0, 54bE2c = b0, 30c = 0 → R2 = 0, 30
bE3c = b1, 14c = 1 → R3 = 0, 14bE4c = b0, 72c = 0 → R4 = 0, 72
bE5c = b2, 88c = 2 → R5 = 0, 88bE6c = b0, 42c = 0 → R6 = 0, 42
Entonces me quedan 3 slots, por ejemplo uso ruleta para asignarlos.Elijo 3 números al azar: r = 0, 15|0, 7|0, 22.
Multiplico por n = 30, 45 2, 1 0, 6↓ ↓ ↓I1 I5 I2
Orden0,54 0,540,30 0,840,14 0,980,72 1,70,88 2,580,42 3
El asignamiento final nos queda:
1→ 12→ 13→ 14→ 05→ 36→ 0
y luego apareo al azar.
7.5.8. Otros métodos Fitness Proportional
Los métodos que hemos visto con BIAS = 0 o casi pueden producir que al principiocuando hay gran disparidad de Fitness, un grupo de individuos con alta fitness relativa,cope la población.
Impidiendo una búsqueda exhaustiva, de todo el espacio de búsqueda, por otro lado,luego de que se estabilice la población es difícil para un individuo con mayor Fitnessinfluenciar la búsqueda produciendo un estancamiento.
Por esto se han propuesto alternativas.
107
7.5.9. Sigma Scaling
En este método se calculan las Ei en forma distinta Ei
Se define Ei =
{1 + Fi−F
2σσ 6= 0
1 σ = 0: σ = desvío estándar de los Fi.
Ventaja: al principio, σ suele se grande, entonces se evita “Crownding”, al final σ ≈ 0.Entonces el mejor individuo se va a reproducir mucho más.Ejemplo: con las Fitness de antes obtengo σ = 30, 627
Y voy calculando los Ei
Primero: E1 = 1 +17, 118− 31, 7
2σ= 0, 762
Eii∑
j=1
Ej
E1 = 0, 762 0, 762
E2 = 0, 638 1, 400
E3 = 1, 072 2, 472
E4 = 0, 855 3, 327
E5 = 1, 973 5, 3
E6 = 0, 700 6
Aplico RuletaElijo n = 6, números al azar
0, 15 0, 7 0, 22 0, 91 0, 46 0, 63Multiplico por n = 60, 90 4, 2 1, 32 5, 46 2, 76 3, 78I2 I5 I2 I6 I4 I5
Obtengo algo más balanceado.
Si hubiera aplicado SUS: con r = 0, 15
0, 15 1, 15 2, 15 3, 15 4, 15 5, 15I1 I2 I3 I4 I5 I5
Roletamiento
Ei = eFiT∑erjT
: T temperatura, inicialmente alta y luego se enfría
Otros métodos no usan Fitness ProporcionPor ejemplo: métodos de Rango, se usan las Fi para ordenar los individuos y luego se
elije por algún método.Basándonos sólo en la posición en ese ordenamiento.Otras Selecciones: no tan basadas en Fitness.
108
Métodos de rango: se usa la Fitness para ordenar la población y luego se usa unamedida que dependa sólo de la posición en esa población.
Lineal Ranking: LR(pos) = (2− SP ) + 2(SP − 1)(pos−1n−1
)SP parámetro en [1, 2]
SP es por “Selective Pressure”
Estas tomarían el lugar de los Eii.e. sería: Ei = LR(Pos(i))
Por ejemplo SP = 1⇒ LR(pos) = 1∀pos, no hay presión.SP = 2⇒ LR(pos) = 2
(pos−1n−1
)SP ∈ (1; 2), por ejemplo SP = 1, 2
LR(pos) = 0, 8 + 0, 4
(pos− 1
n− 1
)SP no tiene que ser fijo, podría ir aumentando para aumentar la presión.Ejemplo: con las Fitness del ejemplo anterior
F2 < F6 < F1 < F4 < F3 < F5
↓ ↓ ↓ ↓ ↓ ↓1 2 3 4 5 6
Tomando SP = 1, 2:
E1 = LR(3) = 0, 96 : 3 es la posiciónE2 = LR(1) = 0, 8E3 = LR(5) = 1, 12E4 = LR(4) = 1, 04E5 = LR(6) = 1, 2E6 = LR(2) = 0, 8 + 0,4
5= 0, 88
Selección “Torneo”Seleccionar k (usualmente 2) individuos y quedarse con el “mejor”, en un torneo de-
terminísticamente o probabilísticamente.
7.5.10. Crossover
SinglePoint
TwoPointCroospoint
Máscara Binaria
Supongo que tengo esta máscara, generada al azar: 1,0,0,1,1,0,1,0,1,1.
P1 = 2 9 7 2 5 3 1 6 5 8P2 = 4 2 3 6 6 3 9 8 0 9
109
Obtengo:
O1 = 2, 2, 3, 2, 5, 3, 1, 8, 5, 8O2 = 4, 9, 7, 6, 6, 3, 9, 6, 0, 9
Partial Map Crossover
¿Qué pasa con codificación del problema que depende de la posición?P1 = BIGAECJFDHP2 = DJBFECIGAHCorta en dos lugares:O1 = BIG|JECA|FDHO2 = DJB|FIEC|GAHTambién se puede hacer con máscaras. “Order Based”
Cyclic Crossover
VERRRRRRRRRRRRRRRR
7.5.11. Mutación
Strings de bits: cambiar cada bit con probabilidad p ≈ 0.
Strings de enteros o reales: también se puede hacer algo así, pero en el caso en quehaya “fronteras” se hace otra cosa.
Por ejemplo supongamos que la frontera es:
|Ii| ≤ 10 es ∀iI = 0, 5|7, 8|5
I = 0, 5|10|5
O bien: I = 0, 5∣∣10+7,8
2
∣∣ 57.5.12. Mutaciones con Permutaciones
Mutación para codificaciones basadas en posiciones TSP.
Permutar dos elementos al azar.
Elegir uno al azar y cambiarlo con un vecino
“Inversion Mutation”, elijo dos puntos al azar y cambio todos los lugares entre si:GRAFICO
Algunas otras arquitecturas
1. Elitismo (los mejores miembros permanecen). Graf
2. A veces la mutación no se aplica solo a los offsprings.
110
3. Steady State
4. Migraciones
Inundación: mato a los peores cada tanto, se usa mucho con restricciones muy cortas,cada tanto tengo una subpoblación no válida pero la penalizo, pero es muy buena, luegola mato.
7.6. No Free Lunch
Todos los algoritmos que optimizan37 en funciones se comportan, promediando sobretodos las funciones posibles, igual.
Referencias[1] Biggs: “Matematica Discreta”
[2] Roberts, “Applied Combinatorics”
[3] Tarjan: “Data Structures and Network Flows”
[4] BFS: http://en.wikipedia.org/wiki/Breadth-first_search
[5] DFS: http://en.wikipedia.org/wiki/Depth-first_search
[6] Árboles en Latex:
http://www.essex.ac.uk/linguistics/external/clmt/latex4ling/trees/pstrees/
[7] Código C en latex:
http://stackoverflow.com/questions/586572/make-code-in-latex-look-nice
37Por ejemplo calcular máximo
111