Algoritmos Combinatoriales

Facultad de Ciencias Fsicas y Matem
aticas
Universidad de Chile
MA3705. Algoritmos Combinatoriales. 2014.

Profesor: Jose Soto
Escriba(s): Crist
obal Rojas, Camilo Rojas y Cristian Tamblay.
Fecha: 28 de Julio de 2014.
C
atedra 1
1.
Introducci
on
1.1.
Problemas en Optimizaci
on Combinatorial
Se entiende por Optimizaci

on Combinatorial a la rama de la matematica enfocada en el dise
no y analisis de algoritmos
eficientes para encontrar objetos
optimos en conjuntos finitos. Mas formalmente se considera un conjunto finito DOM y
una funci
on f : DOM R, y se buscan los elementos x arg m
ax(f ) o x arg mn(f ).
Considerando problemas de la forma anterior, es claro que estos siempre tiene solucion dada la finitud del conjunto
DOM. Pese a esto, un problema clave que aparece es el hecho que |DOM| es enorme, por lo que son demasiadas opciones
a revisar, es por esto que interesa dise
nar un algoritmo que encuentre esta solucion eficientemente. El gran tama
no del
conjunto DOM nos llevar
a a describirlo de forma implcita.
A modo de motivaci
on se mostrar
an algunos ejemplos que se abordaran en este curso.
Ejemplo 1 (Problemas de emparejamiento o matching de cardinalidad maxima). De manera intuitiva se considera un
hotel con habitaciones
individuales y dobles y n huespedes, donde el conjunto de huespedes se denotara por P . Considerando el conjunto P2 de todas las parejas de personas. En este contexto se define el concepto de matching como sigue.
Definici
on 1 (Matching). En el contexto anterior, se dice que M
M es un conjunto de pares disjuntos de elementos de P .
P
2
= {(a, b) P 2 | a 6= b} es un matching en P ssi

Se considera el sub conjunto E P2 de las personas dispuestas a compartir pieza. Se puede plantear el problema de
encontrar un matching M E tal que |M | sea maximo, esto es resolver
m
ax
M matching, M E
|M |
Ejemplo 2. Considerando que el hotel solamente

posee n/2 habitaciones y la funcion de costo o incomodidad
de

emparejar a con b en la misma pieza w : P2 R+ positiva, esto es w({a, b}) 0 para todo {a, b} P2 . Se puede
plantear el problema de encontrar un matching de tama
no n/2 que minimice el costo total, esto es resolver
mn
M matching,|M |=n/2
w(M ),
donde se define la funci

on de peso total del matching M como
X
w(M ) =
w({i, j}).
{i,j}M
Ejemplo 3 (Problema del Vendedor Viajero). Intuitivamente se considera un conjunto de ciudades A Q2 . Adem
as, se
tiene a un vendedor, ubicado en alguna ciudad a0 A, que quiere visitar todas las ciudades al menos una vez y terminar
su viaje en a0 . Para ir desde la ciudad a a la ciudad b con a, b A, el vendedor debe recorrer una distancia d(a, b). Se
plantea el problema es encontrar el tour que cumpla los deseos del vendedor, de largo total mnimo.

aticas
Ejemplo 4 (Problema de Conectividad

de Costo Mnimo). Intuitivamente se considera un conjunto de servidores A, y

una funci
on de costos c : A2 R+ positiva. El objetivo del presente problema es encontrar una configuraci
on de cables
que contenga un camino entre cada par de servidores, de costo total mnimo.
Durante el curso se trabajar
a constantemente con uniones de conjuntos, intersecciones de conjuntos y otras operaciones
por lo cual resulta u
til introducir notaci
on abreviada.
Definici
on 2 (Notaci
on). Se expone a continuacion la notacion a usar durante el curso
1. [n] = {1, 2, . . . , n}.

2. X
k = {Y A | |Y | = k}.
3. Sea : V R
P
Si X V, (X) = xX (x)
4. A + x = A {x}.
5. A x = A\{x}.
1.2.
Fuerza Bruta
Se entiende por fuerza bruta al metodo de solucion de problemas que consiste en probar todas las posibles soluciones.
Si bien este metodo siempre se puede emplear para encontrar soluciones a los problemas de estudio, presenta claras dificultades en cuanto puede tardarse mucho tiempo en encontrar las soluciones, pues como se menciono anteriormente, los
conjuntos estudiados son en general de gran tama
no. Observemos este hecho con un par de ejemplos.
En el contexto del problema de emparejamiento de peso maximo Cuantos matching M en A con |M | = n existen?
Consideremos que |A| = 2n. Para codificar los matching podemos usar la siguiente representacion matricial

a1 a2 an
M=
.
b1 b2 bn
Existen (2n)! matrices de la forma anterior. Mas a
un cada matching se puede representar matricialmente de n! 2n
formas distintas, donde el factor n! emana de las posibles permutaciones entre columnas de la matriz, y el factor 2n emana
de las posibles permutaciones de elementos en una columna. Con esto el n
umero total de matchings es
(2n)(2n 1) (n + 1) n n
(2n)!
=
.
#matchings =
n! 2n
2n
2
En particular tomando n = 20 obtenemos que
#matchings 1020 .
Si revisamos 109 matchings por segundo nos demoraremos
T = 1011 seg 3000 a
nos.
Como segundo ejemplo, en el contexto del problema del vendedor viajero. Cuantos tour existen? Para responder esta
pregunta basta biyectar los posibles tours con las permutaciones de [n] con lo cual
#tours = n!
Esto siempre y cuando distingamos los tours por punto de inicio. Utilizando la aproximacion de Stirling para valores
grandes de n dada por
n n
n! 2n
e
obtenemos que para n = 22 el n
umero total de posibles tours es
#tours 1020 .
2

aticas
1.3.
Programaci
on Lineal y Relajaci
on
Otra forma de abordar los problemas de Optimizacion Combinatorial es transformar estos problemas a problemas de
programaci
on lineal entera equivalentes y aplicar relajaciones posteriores al problema obtenido. Sin embargo, las relajaciones aplicadas pueden introducir distorciones en cuanto las soluciones obtenidas no cumplen con la restricciones naturales
de ciertas variables que deben tomar valores enteros. Se expone a continuacion un ejemplo de este procedimiento y de los
problemas que puede surgir al aplicarlo.
Ejemplo 5 (Planteamiento del Problema de Matching
como PL). Se propone plantear el problema de matching como

un PL equivalente. Para esto se considera E A2 y nuestro objetivo es encontrar un matching M E con |M | m
aximo.
Definamos entonces para cada {a, b} M la indicatriz

1
si {a, b} M ,
X{a,b} =
0
si {a, b}
/M
Luego se plantea el problema lineal entero equivalente
X
(P )
m
ax
X{a,b}
X{a,b} RE
s.a
{a,b}E
(a A)
X{a,b} 1
b6=a
({a, b} E) : X{a,b} {0, 1}

Donde la primera restricci
on representa el hecho que todo elemento de A puede estar apareado con un u
nico elemento,
distinto de el en el matching y la segunda restriccion representa el hecho de que la indicatriz de un elemento de E pueda
tomar s
olo los valores 0
o 1. Es conocido que la resolucion de problemas enteros es compleja, por lo que se propone relajar
el problema para obtener un problema continuo cambiando la u
ltima restriccion por
({a, b} E) : X{a,b} [0, 1].
Si bien esta relajaci
on puede resultar u
til, existen casos patologicos donde las soluciones obtenidas no tienen sentido en
el contexto original del problema. Como ejemplo consideremos la representacion para un problema de Matching en base
a la figura expuesta m
as abajo, donde los nodos corresponden a los huespedes.
Figura 1: Representacion de Problema de Matching

En este contexto es f
acil notar que cualquier solucion optima de emparejamiento, para el problema entero original es
igual a 2. Pese a esto, una soluci
on del problema relajado consiste en dar valor 12 a cada una de las variables X{a,b} para
pares que est
an conectados. En este caso se obtiene un optimo de 2,5; mejorando la solucion anterior. Pese a ello, esta
soluci
on carece de sentido en el problema original pues las variables X{a,b} deben tomar valores 0 o 1.
3

aticas
2.
Grafos
2.1.
Definiciones
Antes de comenzar a trabajar se formalizan las estructuras que se manejaran en el curso.

Definici
on 3 (Grafo simple). Un grafo simple G es un par (V, E), donde E V2 = {{u, v} : u, v V, u 6= v}.
Los elementos v V se denominan vertices y los e E aristas. Denotando una arista por e = {u, v} o bien e = uv = vu.
Adem
as diremos que los vertices u y v de una arista e se denominan extremos de e.
v
e = vw
w
Figura 2: Un grafo simple
De manera natural se extiende esta definici
on a un contexto mas general.
Definici
on 4 (Multigrafo).
Un grafo G es un par (V, E), donde a cada arista e E se le asigna un conjunto de extremos
que puede ser {u, v} V2 o un sngleton {v}, con v V .
Las aristas de un solo extremo ser
an llamadas bucles o loops y las aristas con extremos iguales se denominar
an paralelas.
Por comodidad, pero abusando de la notaci
on, se escribe e = {u} para el bucle de extremo u y e = uv para una arista de
extremos u y v.
Observaci
on 1. Un grafo sin bucles ni aristas paralelas es un grafo simple.
Dado un grafo G se asocian los siguientes conceptos a el:
Una arista e es incidente a un vertice v, si v es extremo de e.
Dos aristas son adyacentes si son incidentes a un vertice com
un.
Dos vertices u y v son adyacentes o vecinos si existe una arista de extremos u y v.
El orden de un grafo es |V | y solemos denotar por n = |V |.
El tama
no de un grafo es |E| y solemos denotar por m = |E|.
Antes de continuar es necesario establecer algunas convenciones que se utilizaran a lo largo del curso.
A no ser que se diga lo contrario, cuando se dice grafo se refiere a un grafo simple. Por otra parte, si G = (V, E) se
escribe V = V (G) y E = E(G), por lo que se dice que G es un grafo con vertices en V y aristas en E. Finalmente dentro
del contexto que nos interesa estudiar, se supondra que |E|, |V | < +.
A continuaci
on se listan una serie de ejemplos para clarificar la idea de grafo.
Ejemplo 6.
El grafo vaco: (, )

El grafo completo: Kn = [n],

[n]
2
= ({1, . . . , n}, {ij : i < j}) .
El complemento del grafo completo: Kn = ([n], ).

Dada una relaci
on simetrica en V , podemos definir:
G = (V, {uv : u 6= v, u v}) .
4

aticas
Figura 3: El grafo completo K5
2.2.
Conjuntos notables en un grafo
En lo que sigue definiremos algunos conjuntos especiales que surgen al estudiar los grafos y que nos ser
an de gran
utilidad.
Definici
on 5. Dados U, W V , U W = , F E podemos se define:
F [U, W ] = {e = uv F : u U, v W }.
Definici
on 6. Si v V, U V y F E se definen:
Corte de v en F : F (v) = {e F : e es incidente a v} = F [{v}, V \{v}].
Corte de U en F : F (U ) = {e F : e es incidente a alg
un v U y a alg
un v
/ U } = F [U, V \U ].
Vecinos v en F : NF (v) = {w V \{v} : e F, e = vw}.
Vecinos U en F : NF (U ) = {w V \U : v U, e F, e = vw}.
Grado de v: la cantidad d(v) = |(v)| = |N (v)|.
Cuando F = E omitiremos el subndice en las definiciones anteriores.
Definici
on 7 (Subgrafo). Un grafo G0 = (V 0 , E 0 ) es subgrafo de G = (V, E) si V 0 V y E 0 E. En tal caso escribiremos
0
G G.
0
Observaci
on 2. Como G0 es grafo, se deduce tambien que E 0 E V2 .
Definici
on 8. Dado U V , el subgrafo de G inducido por U , es el grafo dado por:
G[U ] = (U, {e = uv E : u, v U }) .
Definici
on 9. Dado F E, el grafo obtenido al borrar F de G es:
G\F = (V, E\F ) .
De manera similar, dado U V , el grafo obtenido al borrar U de V es:
G\U = G[V \U ].
2.3.
Paseos, caminos y ciclos
Definici
on 10. Un paseo es una secuencia:
P = v 0 e 1 v1 e 2 v2 e 3 v3 e k vk ,
donde vi V, ei E, ei = vi1 vi . Diremos que el largo del paseo es el n
umero de aristas que este contiene.
Observaci
on 3. Un paseo se dice arista-simple si todas las aristas que contiene son distintas.

aticas
Definici
on 11 (Camino/ciclo). Dado un paseo P , si todos los vertices vi que lo componen son distintos, entonces se dice
que P es un camino entre v0 y vk . En el caso en que son distintos salvo sus extremos, es decir v0 = vk , diremos que P es
un ciclo.
Observaci
on 4. Por abuso de notaci
on, al conjunto
{ei }ki=1 tambien se le llama camino o ciclo. De la misma manera,

k
k
llamamos camino o ciclo al grafo {vi }i=0 , {ei }i=1 .
Figura 4: Un ciclo de largo 8

aticas

Profesor: Jose Soto
Escriba(s): Matas Alvarado, Felipe Arbul
u y Cristobal Parraguez.
Fecha: 01 de Agosto 2014 .
C
atedra 2
Dado el grafo G = (V, E), se defini
o previamente:
Paseo: Secuencia de vertices v1 v2 . . . vk con vi vi+1 E, i {1, 2, . . . , k 1}.
Paseo Arista-Simple: Paseo v1 v2 . . . vk donde todas las aristas ei = vi vi+1 , i {1, 2, . . . , k 1} son distintas.
Camino: Es un paseo que no repite vertices. Notar que como no repite vertices, no repite aristas. Luego todo camino
es un paseo arista-simple.
Ciclo: Es un paseo v1 v2 . . . vk que no repite vertices excepto que v1 = vk .
Grafo Conexo: Diremos que G es conexo si u, v V existe un u-v camino.
Grado de un vertice: Definimos el grado del vertice v V como d(v) = |(v)|.
Vertice Aislado: v V se dice aislado si d(v) = 0 i.e., no existen aristas de G incidentes a v.
Hasta ahora cada paseo lo hemos denotado por sus vertices. Tambien podemos denotar cada paseo (y por ende, cada
camino y ciclo) por la secuencia de aristas como lo muestra el siguiente ejemplo:
v5
e6
v1
e1
e4
v2
e2
e5
v3
v6
v4
e3
Figura 1: ({v1 , v2 , v3 , v4 }, {e1 , e2 , e3 , e4 }) es un ciclo.

Proposici
on 1. Si u-v es un paseo en G, entonces existe un u-v camino en G.
Demostraci
on. Como sabemos que el grafo es finito y existe un u-v paseo, elijamos el u-v paseo mas corto. Este paseo
debe ser claramente un u-v camino (Verificar!).
Definici
on 1. Si G = (V, E), en V se define la relacion E de ((estar conectados)) como
u E v existe un u-v camino con aristas en E
Se puede verificar que esta relaci
on es de equivalencia.
Definici
on 2 (Componentes Conexas). Sea G = (V, E) un grafo. Las componentes conexas son las clases de equivalencia
de la relaci
on E .
Por ejemplo, el siguiente grafo tiene exactamente tres componentes conexas

aticas
Figura 2: Grafo con tres componentes conexas

Alternativamente: W es componente conexa si W V es un conjunto maximal de vertices con G[W ] conexo. (Verificar!)
Definici
on 3. Dado G = (V, E) un grafo, definimos cc(G) como el n
umero de componentes conexas de G.
Si G es conexo, entonces claramente cc(G) = 1.
Lema 1. Sea G = (V, E) un grafo. Si G es acclico (i.e., no hay ciclos en G) entonces cc(G) = |V | |E|.
Demostraci
on. Por inducci
on sobre |E|.
Si |E| = 0, entonces cc(G) = |V | (cada vertice es componente conexa) y se cumple la proposicion.
Si |E| 1, sea e = uv una arista y K la componente conexa que contiene a u y v. Al borrar e, K debe dividirse en dos
componentes conexas, pues de lo contrario en G e = (V, E e) existe un u-v camino P , pero P + e es un ciclo, lo que
es una contradicci
on (en rigor debieramos verificar que K no se divide en mas de dos componentes conexas, pero esto es
directo de que todo vertice sigue conectado a u o a v). De esto se deduce que cc(G) = cc(G e) 1, y por la hip
otesis
inductiva, cc(G) = |V | (|E| 1) 1 = |V | |E|.
Por inducci
on, hemos demostrado lo que se quera.
Corolario 1. Si G es un grafo acclico y conexo, tenemos 1 = cc(G) = |V | |E| |E| = |V | 1.
Definici
on 4 (Arbol).
G se dice
arbol si es acclico y conexo.
La figura muestra el ejemplo de un
arbol
Figura 3: Arbol
Definici
on 5 (Bosque). Si G es acclico se dice bosque. Claramente un bosque debe componerse de uno o m
as
arboles de
vertices disjuntos entre s.
Definici
on 6 (Hoja). Un vertice v se dice hoja si d(v) = 1.
Lema 2. Si T es
arbol con n = |V | 2 entonces T tiene al menos dos hojas.
Demostraci
on. Sea uw1 w2 . . . wk v el camino maximal en T para la inclusion. Si d(u) 2, entonces existe w V adyacente
a u distinto de w1 . Si w es alguno de w2 , . . . wk , v entonces existe un ciclo en T , lo que es una contradicci
on. Entonces
wuw1 w2 . . . wk v es un camino m
as largo que uw1 w2 . . . wk v, lo que contradice nuestro supuesto inicial. Luego d(u) = 1,
an
alogamente d(v) = 1 y as u, v son hojas de T .

Definici
on 7. Sea G = (V, E) grafo, e V2 , F E. Decimos que F ((genera e)) si existe un camino con aristas en F
que conecte los extremos de e. Tambien decimos que G0 = (V, F ) genera e.

aticas
Por ejemplo, en la figura, F genera e.
Figura 4: En este caso e

/ E pero F genera e
Finalmente, si H es un subgrafo de G, decimos que H genera G, si H genera todas las aristas de G.
Problema 1 (Problema del subgrafo generador de costo mnimo). Dado G = (V, E) y una funcion de costo c : E R+ ,
encontrar un subgrafo (V, F ) de G que genere G a costo mnimo.
Lema 3. e = uv E es una arista de un ciclo C de G G e genera e.
Demostraci
on.
Sea C = uw1 w2 wk vu un ciclo en G, tomando P = uw1 w2 wk v = C e, P es un u-v camino en G e; luego
como P E e E e genera e, en otras palabras G e genera e.
Sea P un u-v camino en G e P + e = C es un ciclo en G que contiene a e.
Corolario 2. Si G0 G es un subgrafo de G tal que genera G y e pertenece a un ciclo de G0 G0 e genera G.

Demostraci
on. G0 e genera G0 y G0 genera G, por lo tanto, G0 e genera G.
Como consecuencia del hecho que c 0 tenemos que el ((Problema del subgrafo generador de costo mnimo)) admite
soluciones que son bosques. En el caso en que G es conexo, el problema tambien se conoce como arbol generador de costo
minimo o
arbol cubridor.
Definici
on 8 (Algoritmo). Secuencia finita y ordenada de instrucciones para resolver un problema.
Por ejemplo, veamos un algoritmo generico para encontrar un arbol generador.
Dado G = (V, E), sin funci
on de costo y conexo.
Algoritmo 1: Buscar
arbol generador
Elegir r V ;
U {r}; // Nodos visitados
F ; // Aristas de soluci
on
while (U ) 6= do
Elegir e (U ), e = uv, u U , v
/ U;
U U + v;
F F + e;
end
return (U, F )

aticas
Para analizar la correctitud del algoritmo probaremos:

1. El algoritmo termina.
2. En cada iteraci
on T = (U, F ) es un
arbol.
3. Al final T es generador.
Demostraci
on.
1. El algoritmo termina a lo mas en n iteraciones.
2. Inicialmente (U, F ) = ({r}, ) que es un
arbol. Sea (U, F ) el arbol al principio de una iteracion.
En dicha iteraci
on T cambia a T 0 = (U + v, F + uv). T 0 es conexo pues v F +e u y u F w ; w U .
Si T 0 tuviera un ciclo, este ciclo C debe usar e, pero C e T es un camino de u a v, lo que es una contradicci
on,
pues T no contiene caminos de u a v. Luego T es un arbol.
Para probar que G es generador usaremos el siguiente teorema:
Teorema 1 (Conexidad). G = (V, E) es conexo U V ; U 6= ; U 6= V : (U ) 6= .
Demostraci
on.
Sea U 6= con U V , consideremos u U y v
/ U ; como G es conexo existe un u-v camino en G, digamos P .
U
w2
w1
wi
wi+1
wk1
Figura 5: Camino P .
P = uw1 ...wk1 v, con w0 = u U y wk = v
/ U . Sea wi el u
ltimo vertice tal que w0 w1 ...wi estan todos en U .
Luego wi+1
/ U ; de donde wi wi+1 (U ).
Por contradicci
on. Si G no es conexo, sea U una componente conexa de G, luego =
6 U 6= V , entonces (U ) = ,
lo que es una contradicci
on.
3. Al final del algoritmo, sabemos que T = (U, F ) es un arbol y se sale del while, luego (U ) = ; como G es conexo,
debe ser U = o U = V . Pero U 6= pues r U . Se concluye que U = V . Asi T es un arbol que contiene todos los
vertices de V . Luego, hay un camino entre cada par de vertices de G. Es decir, T genera G

aticas
Casos especiales del algoritmo gen

erico
Algoritmo 2: BFS (Breadth First Search o B
usqueda en amplitud)
Elegir r V ;
F ;
Aux ;
Agregar al final de Aux todas las aristas de (r);
while Aux 6= do
Extraer PRIMERA arista e = vw de Aux;
if e contiene un extremo no visitado, digamos w
/ U then
U U + w;
F F + e;
Agregar al final de Aux todas las aristas de (w);
end
end
return T = (U, F )
Algoritmo 3: DFS (Depth First Search o B

usqueda en profundidad)
Elegir r V ;
F ;
Aux ;
while Aux 6= do
Extraer ULTIMA
arista e = vw de Aux;
/ U then
U U + w;
F F + e;
Agregar al final de Aux todas las aristas de (w);
end
end
return T = (U, F )

aticas

Profesor: Jose Soto
Escriba(s): Enzo Aljovin, Christopher Cabezas y Valentina Toro.
C
atedra 3
1.
Previo
En la clase pasada se plante
o el siguiente problema:
(Arbol
cobertor de costo mnimo) Dado un grafo G = (V, E) y una funcion peso c : E R+ , encontrar un
subgrafo generador de costo mnimo.
Una primera manera de abordarlo fue considerando las hipotesis extras de que no exista una funcion de costos (o
equivalentemente, una funci
on de costo que asigna a todas las aristas el mismo peso), y que el grafo G era conexo. Pa
son:
ra este caso, se mostro
o un algoritmo generico y se dieron dos casos especiales, que analizaremos durante el curso. Estos
Algoritmo 1: BFS (Breath First Search o B

usqueda
en amplitud)
Algoritmo 2: DFS (Depth First Search o B

usqueda
en amplitud)
Elegir r V ;
on
Aux ;
while Aux 6= do
Extraer PRIMERA arista e = vw de Aux;
if e contiene un extremo no visitado, digamos
w
/ U then
U U + w;
F F + e;
Agregar al final de Aux todas las aristas de
(w);
end
end
return T = (U, F )
Elegir r V ;
on
Aux ;
while Aux 6= do
Extraer ULTIMA
arista e = vw de Aux;
if e contiene un extremo no visitado, digamos
w
/ U then
U U + w;
F F + e;
Agregar al final de Aux todas las aristas de
(w);
end
end
return T = (U, F )
Observaci
on 1.
En el
arbol obtenido a partir de BFS, cada vertice est
a unido a la raz por un camino de largo mnimo. Esto fue
probado en la primera clase auxiliar.
El algoritmo DFS trata de llegar a una hoja lo m
as r
apido posible.
Una manera de familiarizarse con dichos algoritmos, es visualizar paso a
paso la ejecuci
on de estos con un grafo en particular. Para este proposito, en
la secci
on Anexo se desarrollan ambos algoritmos utilizando el grafo mostrado en la figura 1 (Ejemplo de BFS - figura 2; ejemplo de DFS - figura
3).
En general, la decisi
on de optar por uno de estos algoritmos vendra dada
por el problema en que se quiera aplicar y/o resolver, o las caractersticas que
1
8
1
2
5
Figura 1: Grafo de ejemplo

aticas
busquemos en el
arbol resultante. Es importante mencionar que en terminos
de complejidad ambos algoritmos son pr
acticamente iguales. Pero donde s hay que tener cuidado es en el tipo de estructura
de dato con que se implementa cada algoritmo, puesto que esto podra causar una diferencia no menor en el an
alisis de
complejidad. Sin embargo, este an
alisis queda para un curso de estructura de datos y/o complejidad computacional y
escapa a los contenidos del curso.
2.
Complejidad de un Algoritmo
Al momento de analizar y comparar algoritmos, surgen interrogantes naturales como: Que algoritmo es m
as r
apido?
Cu
al realiza menor cantidad de operaciones? Son estas mismas preguntas, las que motivan estudiar la complejidad de un
algoritmo y, de esta manera, poder establecer cuan rapido es un algoritmo.
Definici
on 1 (Tiempo(ALG, ENTRADA)). Corresponde al n
umero de operaciones basicas que realiza ALG en ENTRADA, antes de terminar.
Al ver esta definici
on, nos preguntamos que se considera una operacion basica. En general, dependera del modelo que
se este utilizando. Sin embargo, aqu consideraremos que las siguientes operaciones corresponden a operaciones b
asicas:
Sumar y restar
Multiplicar y dividir*
Comparar
Acceder
Copiar
Nos interesaremos en operaciones que dependan de un parametro, por ejemplo n sumas o n2 sumas. Un caso que
no consideraremos es 4 sumas.
Hay que considerar adem
as que una entrada se puede codificar como cierto n
umero de bits por registro.
Definici
on 2 (Complejidad de un algoritmo). Sea ALG un algoritmo. Consideramos su complejidad como la funci
on
f (N ) = m
ax {T iempo(ALG, EN T ) | N (EN T ) = N }
donde N (EN T ) corresponde al tama
no de la entrada EN T .
Observaci
on 2. En general, dado un algoritmo, no nos preocuparemos de calcular de manera explcita su funci
on complejidad, sino que nos interesar
a ver c
omo crece y su comportamiento de manera asint
otica.
Ejemplo 1. Supongamos que se tiene un algoritmo ALG, cuya funci
on de complejidad es
T (N ) = 30N 5 + 12N + 10blog N c.
En este caso se tendr
a que T = O(N 5 ). Esto significa que T no crece m
as r
apido que N 5 .
En el caso de algoritmos de grafos, se prefiere dejar la complejidad expresada en terminos de parametros del grafo
(como por ejemplo, la cantidad de vertices y/o aristas).

aticas
2.1.
An
alisis de los algoritmos DFS/BFS
2.1.1.
Representaciones de un grafo
Para realizar el an
alisis, primero veamos c
omo se representa un grafo. En general, existen dos maneras cl
asicas de
codificar un grafo.
Matriz de Adyacencia
En este caso, dado un grafo G = (V, E), se ordenan los vertices y se construye la matriz cuadrada A tal que si
v, w V

1 si vw E
Avw =
0 si vw
/E
Es f
acil notar que la matriz A, en el caso de un grafo no dirigido,sera simetrica.
Lista de Adyancencia
A cada vertice se le asocia una lista. Los elementos de esta lista pueden corresponder a los vecinos del vertice o a
las aristas incidentes.
Ambas formas para escribir grafos poseen ventajas y desventajas. Por ejemplo, en la matriz de adyacencia se detecta
inmediatamente si una arista existe o no, pero el precio que se paga por esto es el espacio utilizado (cantidad cuadr
atica
con respecto al n
umero de vertices). En este sentido, la lista de adyacencia es menos eficiente. Por otra parte, en la lista
es m
as f
acil ver los vecinos de un vertice.
Para este curso, consideraremos que manejamos ambas formas de representacion.
2.1.2.
An
alisis de los algoritmos DFS/BFS
En el siguiente algoritmo aparece el orden de cada una de las acciones que se realizan, donde |V | = n y |E| = m:
Algoritmo 3: DFS/BFS
Elegir r V ; O(1)
U {r}; O(1)
F ; O(1)
Agregar al final de Aux todas las aristas de (r); O(1)
while Aux 6= do
Extraer PRIMERA/ULTIMA
arista e = vw de Aux; O(1)
/ U O(1)
then
U U + w;
F F + e;
Agregar al final de Aux todas las aristas de (w); O(n)
end
end
return T = (U, F )
Realicemos un primer an
alisis, considerando que realizamos el trabajo dentro del while una vez por cada arista
del grafo. Se obtiene que los algoritmos BFS/DFS son de orden O(mn). Si consideramos ademas que en la clase anterior
se obtuvo un resultado para grafos conexos, que estableca que en un grafo conexo acclico (i.e un arbol) m = n 1,
obtenemos para estos algoritmos una cota inferior de m2 (en el caso del arbol). Por ejemplo, si tuvieramos un grafo con
20 nodos y 20 aristas, y luego se aumentara a 40 el n
umero de aristas, el algoritmo se demorara 4 veces m
as que en el
anterior, pero en la realidad estos algoritmos son bastante mas rapidos. De esta manera queda plasmado que al realizar
estimaciones poco finas nos puede llevar a cotas no muy u
tiles ni cercanas a la realidad.
Siendo un poco m
as precavido y fino a la hora de analizar, notamos que donde se realiza trabajo es cada vez que
una arista entra o sale de Aux. Por otra parte, se tiene que cada una de ellas puede entrar o salir a lo mas 2 veces. Por lo
3

aticas
tanto, se realiza una cantidad constante de trabajo cada vez que una arista entra o sale de Aux. Esto nos lleva a que en
el peor de los casos se tendr
a que el algoritmo estara dominado por m.
En estricto rigor, se debera considerar en el algoritmo el hecho que al recibir una entrada se debe chequear que en
efecto corresponde a un grafo. Dado esto, se tendra que al menos se debera leer una vez cada vertice del grafo. Esto nos
lleva a incluir otro termino en la complejidad del algoritmo. En virtud de lo antes mencionado se tiene que los algoritmos
BFS/DFS son O(n + m), donde el termino n viene del hecho de leer la entrada y el termino m del analisis antes hecho.
2.2.
Algoritmo de PRIM
Algoritmo 4: Algoritmo de Prim (Prim 1957 - Jarnk 1930)

Elegir r V ;
U {r}
F
while (U ) 6= do
Sea e = uv (U ), u U, v
/ U tal que e es la arista de menor peso en (U )
U U + w;
F F + e;
end
return T = (U, F )
Para analizar la correctitud del algoritmo recien expuesto, dado que ya se ha verificado que este algoritmo devuelve
un
arbol, la demostraci
on se centrar
a en ver que en efecto este arbol corresponde a uno de costo mnimo. Para ello, se
introducir
an definiciones y lemas previos, los cuales nos permitiran concluir.
Definici
on 3 (Conjunto de aristas extendible). Sea G = (V, E) un grafo conexo y w : E R+ una funci
on peso. Se
dir
a que un conjunto de aristas E 0 E es extendible, si existe un arbol generador de peso mnimo T = (V, F ), con E 0 F .
Lema 1. Sea G = (V, E) un grafo conexo, E 0 extendible y e E \ E 0 , entonces
E 0 + e es extendible
U V, con ( U ( V :
E 0 (U ) = , pero e es de peso mnimo en (U )
Demostraci
on Veamos la doble implicancia.
(=) Se tiene E 0 extensible, e E \ E 0 y sea U V tal que ( U ( V .
Como E 0 es extendible, se tiene que existe un arbol optimo T = (V, F ) con
E 0 F . Analicemos dos casos
e F:
En este caso, se tiene directo que E 0 +e F y por tanto, E 0 +e es extensible.
e
e
/ F:
En el caso que e
/ F , se tendr
a que F + e tendra un u
nico ciclo C. Como
F es conexo (por la propiedad demostrada en la catedra 2): (U ) F 6= .
Sea f (U ) C, f 6= e. Considerando e = uv con u U, v V \ U (ya
que e
/ F ). Sea P el camino que une u con v en F (notar que dicho camino
es u
nico), de esto sigue que C = P + e. Luego, P contiene arista f (U )
y adem
as E 0 + e F .

aticas
(=) Si E 0 + e es extendible, existe F

arbol
optimo tal que E 0 + e F .
Notemos que F e desconecta el grafo en dos conjuntos. Sea U uno de ellos. Veamos que e (U ) es de peso mnimo.
Si f (U ) con w(f ) < w(e). Luego, el
arbol
F0 = F e + f
es tal que w(F 0 ) < w(F ), lo que contradice que F sea un arbol optimo.

aticas
3.
3.1.
Anexo
Ejemplo BFS
8
1
8
1
Aux =
Aux = {1, 2}
n
o
1
, 2, 3
Aux =
n
o
1
, 2
, 3, 4, 5, 6, 7
Aux =
n
o
1
, 2, 3, 4, 5, 6, 7
Aux =
n
o
1
, 2, 3, 4, 5
, 6, 7
6
3
8
8
1
Aux =
n
o
1, 2, 3, 4, 5, 6, 7, 8
Aux =
8
1
o
n
1
, 2, 3, 4, 5
8
1
Aux =
8
1
8
1
n
o
1, 2, 3, 4, 5, 6, 7, 8
Figura 2: EJEMPLO BFS
Aux =
n
o
1, 2, 3, 4, 5, 6, 7, 8

aticas
3.2.
Ejemplo DFS
Aux =
Aux = {1, 2}
1,
2, 4, 5
Aux =
5, 3, 6, 7
4,
2,
1,
7, 8
5, 3, 6,
4,
2,
1,
Aux =
Aux =
8, 6
7,
5, 3, 6,
4,
2,
1,
1, 2
, 4
, 5
, 3, 6
, 7
, 8
, 6

Aux =
1,
2, 4,
5
Aux =
Aux =
1, 2
, 4, 5, 3, 6, 7, 8, 6, 1
Figura 3: EJEMPLO DFS
Aux =
n
o
1
, 2, 4, 5, 3, 6, 7
, 8
, 6
, 1


aticas

Profesor: Jose Soto
Escriba(s): Daniel Castro, Camila Fern
andez y Sebastian Tapia.
C
atedra 4
En la siguiente clase, presentaremos criterios que nos resultaran comodos a la hora de analizar la complejidad y
eficiencia de un algoritmo, lo que concierne tanto al costo temporal como computacional que tiene llevarlo a cabo y al final
presentaremos como ejemplo el an
alisis del algoritmo PRIM. Para esto, comenzaremos con la llamada notacion asint
otica.
1.
Notaci
on asint
otica.
Para evitar las diferencias entre distintas formas de medir la complejidad de un algoritmo usaremos notacion asint
otica,
para lo cual ser
an necesarias las siguientes definiciones, en las que f y g son funciones que van de N a R, sin embargo, la
notaci
on es v
alida para funciones con dominios mas complicados, por ejemplo, permitimos que f o g tengan una cantidad
finita de puntos donde se indefinen.
Definici
on 1. (O(g)) Decimos que:
f O(g) n0 N c > 0, x n0 |f (x)| c|g(x)|.
Se suele decir que f es O-grande de g o es orden g, lo que significa que f crece a lo mas tan rapido como g.
Definici
on 2. (o(g)) Decimos que:
f o(g) > 0 no N, x n0 |f (x)| |g(x)|.
Se dice que f es o-chica de g, lo que significa que f crece estrictamente mas lento que g.
Definici
on 3. ((g)) Decimos que:
f (g) g O(f ) n0 N M > 0, x n0 |f (x)| M |g(x)|.
Se dice que f es Omega-grande de g, lo que significa que f crece a lo menos tan rapido como g.
Definici
f (g) g o(f ) M > 0 no N, x n0 |f (x)| M |g(x)|.
Se dice que f es omega-chica de g, lo que significa que f crece estrictamente mas rapido que g.
Definici
f (g) f O(g) (g).
Se dice que f es Theta de g, lo que significa que f crece del mismo modo que g.
Se puede notar tambien que las primeras cuatro definiciones se pueden reformular de la siguiente manera pidiendole
una condici
on extra a g.
Proposici
on 1. Sean f, g : N R, con g tal que su conjunto de ceros es finito. Las siguientes sentencias son verdaderas.

f (x)
< +.
1. f O(g) lm supx
g(x)
1

aticas

f (x)

= 0.
2. f o(g) lmx
g(x)

f (x)
> 0.
3. f (g) lm inf x
g(x)

f (x)
= +.
4. f (g) lmx
g(x)
Observaci
on: Esta notaci
on esconde constantes multiplicativas y sumas de funciones de menor orden, tal como se
muestra a continuaci
on:
1.1.
Ejemplos.
1. 5n2 + 2n4 O(n5 ).

2. 2n o(n log(n)).
3. log(n!) (n log(n)).
4. 2n (n1000000 ).
5. logk (n) (log(n))
1.2.
k N.
Abuso de notaci
on.
La O-notac
on resulta ser muy c
omoda, pero dada la tradicion en su uso, existe abuso de notacion, el cual ser
a explicado
a continuaci
on:
Signo = en vez de : En vez de escribir f O(g), escribiremos f = O(g), esto es como el significado computacional
que tiene el signo = y su sentido de asignacion ( tal como cuando escribimos n = n + 1). Para recalcar m
as a
un
su sentido, al signo = lo leemos como es, as que se utilizara como en el ejemplo: un pajaro es un animal, pero un
animal no es un p
ajaro. Ahora llevado a la O-notacion:
n log(n) = O(n2 ) = O(n3 ) 6= O(n2 ).
A modo de otro ejemplo: n3 + 5n2 + 40n1,5 = n3 + O(n2 ) = O(n3 ).
2.
Eficiencia o Complejidad de un Algoritmo.
Todo algoritmo recibe una entrada que pueden ser N n

umeros enteros (en una lista por ejemplo) los que, como informaci
on, se codifican usando S bits. Al analizar un algoritmo, se busca dar buenas cotas superiores para su complejidad
(lo m
as ajustadas posible). En an
alisis te
orico un algoritmo se considera eficiente cuando su complejidad esta acotada por
un polinomio.
Definici
on 6. (Algoritmo polinomial o debilmente polinomial) Si un algoritmo tiene complejidad T (S) = O(S k ) para
alg
un k fijo, decimos que el algoritmo es polinomial o debilmente polinomial.
Definici
on 7. (Algoritmo fuertemente polinomial) Si un algoritmo tiene complejidad T (N ) = O(N k ), donde N representa
el n
umero de datos que le entregamos, para alg
un k fijo, decimos que el algoritmo es fuertemente polinomial.
Donde notamos de estas definiciones que todo algoritmo fuertemente polinomial es debilmente polinomial, ya que
N = O(S).
2

aticas
2.1.
Ejemplos
1. Algoritmo BFS: La entrada de BFS es la representacion de un grafo, el cual se puede llevar a cabo de las siguientes
dos maneras (por lo menos):
a) Matriz de adyacencia: Esta es una matriz de n n donde cada fila (respectiva columna) representa un vertice
y cada coordena le corresponde un 1 o un 0, donde 1 significa que existe una arista entre ambos, y 0 que no.
Entonces ocuparemos n2 n
umeros (donde n = |V |). Tambien cabe destacar que si usamos matriz de adyacencia
para codificar un grafo, tanto N (el n
umero de datos) como S (el n
umero de bits) son (n2 ).
b) Lista de incidencia: Esta es una lista enlazada de tama
no n, cada espacio representa un vertice, donde tiene
enlazada otras lista con los vertices incidentes correspondientes. Entonces ocuparemos O(n + m) n
umeros
(donde m = |E|). Tambien cabe destacar que si usamos lista de incidencia N es (n + m), mientras que S es
((n + m) log(n)), pues los n
umeros involucrados tienen magnitud entre 1 y n.
Tambien, la clase anterior demostramos que la complejidad de BFS es O(n + m), lo cual en ambas representaciones
es fuertemente polinomial. Como regla general, todo algoritmo sobre grafos cuya complejidad esta acotada por un
polinomio en n y en m es fuermente polinomial.
2. Tenemos un problema que involucra N datos.
Si un algoritmo demora T (N ) en resolver el problema y duplican el n
umero de datos (2N datos), entonces demorar
a T (2N ).
Si T es fuertemente polinomial, es decir, T (N ) = O(N k ), entonces:
T (2N ) = O((2N )k ) = O(2k N k ) = O(N k )
El tiempo necesario para resolver el problema grande se multiplica por una constante, en este caso 2k .
3. Si ahora el algoritmo demora T (N ) = 2N , entonces:
T (2N ) = 22N = (2N )2
El que ya no es una multiplicaci
on por una constante, por tanto ya no es polinomial.
Comentario: Si suponemos cierta la Ley de Moore que sostiene que la capacidad de procesamiento de las computadoras
se duplica cada 18 meses, entonces con los algoritmos polinomiales podramos, cada 18 meses, resolver problemas el doble
de grandes en la misma cantidad de tiempo que hace 18 meses atras.
3.
An
alisis del algoritmo PRIM
Recordemos el algoritmo PRIM de la clase anterior:
Algoritmo 1: Algoritmo de Prim (Prim 1957 - Jarnk 1930)

Elegir r V ;
U {r}
F
while (U ) 6= do
U U + w;
F F + e;
end
return T = (U, F )
Vamos a mostrar la implementaci
on de PRIM de dos formas distintas, pero antes nos haremos dos preguntas que nos
ayudaran en nuestro prop
osito:

aticas
1. Cu
al es la complejidad de ordenar N n
umeros?
(N log(N ))
va mergesort, por ejemplo.
2. Complejidad de encontrar el mnimo en una lista?

Sin ordenar
Ordenada
3.1.
1.
O(N )
O(1)
Implementaci
on
Algoritmo 2: 1ra implementaci
on del Algoritmo Prim
Elegir r V ;
U {r}
F
while (U ) 6= do
(Revisar todas las aristas y marcar aquellas que estan en (U ))
(sin haber ordenado previamente a (U ))
U U + v;
F F + e;
end
return T = (U, F )
Est
a implementaci
on, por los comentarios hechos en parentesis, se puede concluir facilmente que es de orden O(m2 ),
donde el algoritmo recibe un grafo G = (V, E), m = |E| y n = |V |.
En la siguiente implementaci
on, se ocupar
a la funcion cand(), la que toma un vertice y calcula la arsta incidente a
el m
as liviana.
2.
Algoritmo 3: 2da implementaci

on del Algoritmo Prim
Elegir r V ;
U {r}
F
v V calcular cand(v) for i = 1, ..., n do
Elegir el mejor candidato en arg mnvU cand(v).
e = uv con u U y v V ; U U + v;
F F + e;
Recalcular w
/ U cand(w)
end
return T = (U, F )
Para analizar esta implementaci
on, la divideremos en fuera y dentro del for.
Fuera del for:
a)Para calcular por primera vez cand(v) para todo vertice v, solo debemos mirar las aristas incidentes a r, lo que
toma O(n + deg(r)) = O(n).
Dentro del for:
b) Elegir el mejor candidato toma O(n), pues es el mnimo entre a lo mas n n
umeros.
c) Por u
ltimo, recalcular candidato para un w toma tiempo constante, ya que es solo reemplazar el antiguo cand(w)
por el mejor entre cand(w) y el peso de la arista vw (si es que existe), donde v es el vertice que acaba de entrar a
U. Como esto lo haremos a lo m
as n veces, el trabajo es de O(n).

aticas
Juntando todo lo anterior, el trabajo fuera del for es de O(n), el trabajo adentro del for es de O(n), repetido O(n)
veces, por lo que el trabajo total es O(n2 ).
Usando estructuras de datos m
as avanzadas (colas de prioridad llamadas Heaps), al algoritmo Prim se puede implementar m
as r
apido, como muestran los siguientes ejemplos.
3. Usando Heaps binarios, se puede hacer una implementacion de orden O((n + m) log(n)).
4. Usando Heaps de Fibonacci, se puede hacer una implementacion de orden O(m + n log(n)),
4.
Pr
oxima Clase.
En la pr
oxima sesi
on, se estudiar
an los algoritmos denominados Algoritmos Glotones (o Avaros). Estos corresponden a
algoritmos que en cada decisi
on incorpora a la solucion el objeto mas barato. Un ejemplo de algoritmo gloton para calcular
bosques generadores de peso mnimo es el algoritmo de Kruskal, que expondremos a continuacion.
La entrada del algoritmo, es un grafo G = (V, E) y w : E R, una funcion que respresenta al peso asignado a cada
arista.
Algoritmo 4: Algoritmo de Kruskal
Ordenar todas las aristas en orden creciente w(e1 ) w(e2 ) w(en )
F
for i = 1, ..., n do
if F + ei es acclico then
F F + ei
end
end
return T = (V, F )

aticas

Profesor: Jose Soto
Escriba(s): Manuel C
aceres, Camilo G
omez y Sebastian Mu
noz.
C
atedra 5
1.
Recuerdo del algoritmo de KRUSKAL
La clase anterior se describi

o el algoritmo de Prim, el cual a traves de la formacion de una u
nica componente conexa,
encuentra un
arbol cobertor de peso mnimo de un grafo conexo. Se describieron ademas diferentes implementaciones y se
analizaron las complejidades de las mismas.
Por u
ltimo, se describi
o una forma alternativa de enfrentar el problema del arbol cobertor de peso mnimo que consiste
en ir agregando en cada iteraci
on la arista de menor coste mientras esta no forme un ciclo1 .Esta forma corresponde al
algoritmo de Kruskal, que se recuerda a continuacion :
Algoritmo 1: Algoritmo de Kruskal
Entrada: G = (V, E) conexo
T
while T no es generador do
Sea e E \ T de peso mnimo, tal que T + e no tiene ciclos
T T +e
end
return (V, T )
1.1.
Correctitud del algoritmo
Veamos primero que Kruskal encuentra un

arbol cubridor.
Por un lado, es simple notar que el resultado del algoritmo corresponde a un grafo accliclo, dado que al agregar aristas
al resultado se exige que estas no formen ciclos. Por otro lado, supongamos por contradiccion que existen dos vertices u
y v que no est
an contectados a traves de T , no obstante como G es conexo, existe un camino entre u y v. De este camino
consideremos la primera arista e que tiene como incidente un vertice x que no esta en la misma componente conexa de u.
Con respecto a esta arista (dado que fue procesada por el algoritmo en su momento) se puede razonar que T + e forma
un ciclo, pero esto es contradictorio con el hecho de que u y v no estan conectado a traves de T .
Veamos ahora que el
arbol corresponde a uno de peso mnimo.
Para esto tomemos T el
arbol cubridor entregado por el algoritmo de Kruskal y T 0 alg
un otro arbol cubridor del
grafo G, consideremos que sus aristas son {e1 , . . . , en1 } y {e01 , . . . , e0n1 } respectivamente y que estan ordenadas en orden
creciente seg
un sus pesos.
Como se quiere mostrar que T es de peso mnimo, supongamos por contradiccion que existe un par ei , e0i , tales que el
peso del primero es estrictamente mayor que el peso del segundo y supongamos sin perdida de generalidad que este i es
el mnimo ndice que cumple la condici
on anterior.
Consideremos por u
ltimo los conjuntos de aristas E 0 = {e1 , . . . , ei1 }, E 00 = {e01 , . . . , e0i } y los conjuntos de vertices
V1 . . . Vs correspondientes a las componentes conexas del grafo (V, E 0 ).
Veamos ahora que dado que las s componentes conexas cumplen que

Vj
0
|E
| |Vj |1
2
1 Es
importante notar que ha diferencia del algoritmo de Prim, Kruskal no mantiene una gran componente conexa durante su aplicaci
on.

aticas
y por lo tanto se tiene que |E 0 | n s. Por otro lado, como E 00 no tiene ciclos, se tiene que :

Vj
00
|E
| |Vj |1
2
y por lo tanto las aristas de E 00 contenidas en las componentes Vj son a lo mas n s, y finalmente recordando que
|E 0 | = |E 00 | 1, podemos afirmar que existe por lo menos una arista e E 00 tal que conecta dos componentes conexas de
E 0 . Finalmente como las aristas de E est
an enumeradas en orden creciente de pesos, el peso de e debe ser menor o igual
que el peso de ei , pero, recordando nuestra hip
otesis de contradiccion se tiene que el peso de ei es estrictamente mayor
que el de e0i y por lo tanto, mayor que el de e.
Resumiendo lo anterior, tenemos una arista e que conecta componentes conexas de E 0 = {e1 , . . . , ei1 }(y por lo tanto no
formara ciclo el agregarla) y tal que su peso es estrictamente menor que el de ei , pero el algoritmo opta por ei , lo que es
una contradicci
on.2
1.2.
An
alisis de complejidad
El an
alisis de complejidad de este algoritmo se hara en base una implementacion mejor en terminos de complejidad
descrita a continuaci
on :
Algoritmo 2: Algoritmo de Kruskal(segunda implementacion)
Entrada: G = (V, E)
Ordenar E = {e1 , . . . , em } de menor a mayor peso
T
for i = 1 . . . m do
if T + ei es acclico then
T T + ei
end
end
return (V, T )
Se nota que esta implementaci
on factoriza el trabajo de estar buscando cada vez la arista de menor peso, y en vez de eso
primero ordena las arista en orden ascendente lo que toma O(m log m) = O(m log n), para luego hacer O(n) repeticiones
en las que comprueba si al a
nadir la siguiente arista se forma alg
un ciclo.
El trabajo de verificar si al agregar una arista se forma alg
un ciclo, se puede hacer comprobando si los vertices incidentes a la arista a agregar se encuentran en la misma componente conexa, si es as, la arista forma un ciclo y esta no
debe ser agregada. Este trabajo se puede realizar con alguno de los algoritmos de b
usqueda en grafos vistos anteriormente
(BFS o DFS modificados para tal fin) y por lo tanto toma O(|V | + |T |) = O(n).
Finalmente se concluye que esta implementacion de Kruskal toma O(m log n + n2 ).
1.3.
Observaciones
El problema de averiguar cuando dos vertices pertenecen a la misma componente conexa de manera eficiente es
conocido como Union-Find. Las mejores implementaciones de Union-Find se han hecho en O((n)), donde
corresponde a la inversa de la funci
on de Ackermann, la cual crece extremadamente lento, esta es incluso O(log (n))3 .
Por lo tanto la mejor implementaci
on de Kruskal tarda O(m(n)).
El algoritmo de Kruskal se puede aplicar en un grafo no conexo, en el cual retorna un bosque generador de peso
mnimo, conservando las complejidades antes mencionadas.
2 Veremos
3 log (n)
una demostraci
on alternativa de la correctitud de Kruskal cuando veamos algoritmos glotones en matroides.
corresponde al n
umero de veces que hay que aplicar logartmo a n para que el resultado sea 1.

aticas
2.
Algoritmos Glotones
2.1.
Introducci
on a Algoritmos Glotones
El algoritmo de Kruskal pertenece a una familia de algoritmos llamados algoritmos glotones o codiciosos. En general,
este tipo de algoritmos siguen una estrategia que intentan ganar tanto como sea posible en cada momento y no contempla
las desventajas que estas elecciones podran acarrear en el futuro.
Para el estudio de este tipo de algoritmos se presentaran algunas definiciones y luego se introducira el concepto de
Matroides.
Definici
on 1 (Par Hereditario). Sea E un conjunto finito e I 2E . El par ordenado (E, I) se dice hereditario si:
I=
6 .
Si J I e I J = I I.
Observaci
on 1. Los elementos (conjuntos) de I se llaman conjuntos independientes de (E, I).
Ejemplo 1 (Pares Hereditarios).
(i) Sea E un conjunto finito cualquiera, si consideramos I = 2E , se tiene que (E, I) es hereditario.
(ii) Sea G = (V, E) un grafo, si consideramos I = {F E : F acclico}, se sique que (E, I) es hereditario.
(iii) Sea E conj. finito, entonces (E, I ) = (E, {X E : |X| 7}) es par hereditario.
(iv) Dado w : E R+ , (E, {X E : w(X) c}) es par hereditario, donde c R.
Definici
on 2 (Bases). Sea (E, I) un par hereditario. Los conjuntos independientes de (E, I) que son maximales para la
inclusi
on se llaman Bases.
Ejemplo 2 (Importante). Sea el siguiente par hereditario (E, I), donde E es un conjunto de vectores de Rn ( Fn , con F
cuerpo4 ) e I contiene los conjuntos de E que son linealmente independiente.
Veamos el siguiente ejemplo particular en R2 :

1
0
1
0
Si consideramos el siguiente conjunto de vectores en R2 , E =
,
,
,
,
0
1
1
( 0 )
1
0
1
1
0
1
1
0
1
entonces I =
,
,
,
,
,
,
,
,
.
0
1
1
0
1
0
1
1
1
2.2.
Resoluci
on de Problemas
Dados (E, I) hereditario, w : E R, queremos estudiar los siguientes problemas:

1. Encontrar un conjunto independiente de cardinalidad maxima.
2. Encontrar conjunto independiente de peso maximo.
3. Encontrar una base de peso m
aximo.
Para cada uno de estos problemas propondremos un algoritmo gloton que lo resuelve bajo ciertas condiciones.
4 En
general, se puede en cualquier cuerpo F.

aticas
2.2.1.
Problema de Cardinalidad
Para el primer problema se propondr

a un algoritmo que va agregando elementos e E a un conjunto I, en la medida
que I contin
ue siendo independiente. Esta idea se concretiza en el algoritmo Glot
on-Cardinalidad.
Algoritmo 3: Glot
on-Cardinalidad
Entrada: (E = {e1 , ..., em }, I) hereditario.
I
for i = 1 . . . m do
if I + ei I then
I I + ei
end
end
return I
Proposici
on 1. Si todas las bases tienen el mismo cardinal, el algoritmo Glot
on-Cardinalidad resuelve el problema de
cardinalidad.
Sin embargo, como veremos m
as adelante, esto no es cierto para el algoritmo Glot
on-Base(max).
2.2.2.
Problema del Independiente de peso M

aximo
Para resolver este problema la idea es ir agregando en cada paso elementos de peso positivo que tengan el peso
m
aximo entre los elementos candidatos a ser agregados.
Algoritmo 4: Glot
on-Independiente(max)
Entrada: (E, I) hereditario, w : E R .
Tomar E + E, los objetos de peso positivo de E.
Ordenar E + = {e1 , ..., em } de mayor a menor peso.
I
for i = 1 : m do
if I + ei I then
I I + ei
end
end
return I
2.2.3.
Problema de la Base de peso M

aximo
Para este problema, la idea es an

aloga a la del algoritmo Glot
on-Independiente(max), pero considerando todos los
elementos de E (los que tienen peso positivo como los que no).
Algoritmo 5: Glot
on-Base(max)
Entrada: G = (E, I) hereditario, w : E R .
Ordenar E = {e1 , ..., em } de mayor a menor peso.
I
for i = 1 . . . m do
if I + ei I then
I I + ei
end
end
return I
Para estos dos algoritmos se podra pensar que una condicion suficiente para que resuelvan el problema es que las bases
tengan igual cardinal, sin embargo, el siguiente ejemplo ilustra una complicacion adicional.
4

aticas
Ejemplo 3 (Falla algoritmo Glot

on-Base(max)). Notemos que las bases tengan igual cardinal, se cumple en la figura
1. Adem
as (A B, I) hereditario para I = 2A 2B . Glot
on devuelve {a, b} de peso 3, pero la mejor base es {c, d} de peso
4. Observemos que (A B, I) tiene solo 2 bases.
a b
c d
B
Figura 1
Antes de dar la condici

on suficiente para que Glot
on-Base(max) funcione, veamos la siguiente definici
on:
Definici
on 3 (Base de un conjunto). Sea (E, I) un par hereditario. Dado X E,
decimos que B es base de X ssi B I ( Y I) ( B Y Y X = B = Y )
Luego una condici
on suficiente para que el algoritmo Glot
on-Base(max) funcione es:
X E las bases de X tienen el mismo cardinal.
Para establecer condiciones para que estos algoritmos funcionen, se introducira el concepto de Matroide.
2.3.
Matroides
Definici
on 4 (Matroide). Es un par hereditario M = (E, I) que satisface el siguiente axioma:
(Aumento) Si I, J I con |I| < |J|, entonces existe e J \ I tal que I + e I.
Lema 1 (Equivalencias con el axioma de (Aumento)). El axioma de (Aumento) es equivalente a cualquiera de los
siguientes axiomas:
(Aumento d
ebil) Si I, J I, |J \ I| = 2, |I \ J| = 1, entonces existe e J \ I tal que I + e I.
(Cardinalidad de las Bases) F E las bases de F tienen el mismo cardinal.
Demostraci
on (Pendiente)
2.4.
Ejemplos de Matroides
2.4.1.
Matroides Lineales/Representables
Sea E un conjunto de vectores en un espacio vectorial (Fn , con F un cuerpo).

X I X es linealmente independiente.
Tpicamente las matroides lineales se representan mediante una matriz A cuyas columnas son los vectores de E.
Decimos en ese caso que la matroide est
a representada por A, o que es representable en el cuerpo F.
2.4.2.
Matroides Gr
aficas
M = (E, I)5 donde existe un grafo G = (V, E) tal que F I F no tiene ciclos en G.
5 Se
dice que M = (E, I) es una Matroide Gr

afica.

aticas
Observaci
on 2. Grafos distintos pueden tener igual matroide gr
afica, como en el siguiente ejemplo:
1
3
5
5
6
Figura 2
2.4.3.
Matroide de Partici
on
Sea E =
k
[
Ei donde {Ei }ki=1 es disjunta a pares, tal que |Ei | ci N, i = 1, . . . , k.
i=1
La Matroide de Partici
on asociada (E, I) es tal que
X I i {1, . . . , k} : |X Ei | ci
Verifiquemos que las Matroides de Partici
on son matroides.
Sk
Demostraci
on Sea (E, I) una matroide de particion, tal que E = i=1 Ei disjunta. Sean I, J I, |I| < |J|. Como (E, I)
es matroide de partici
on, i {1, . . . , k} : |I Ei | ci |J Ei | ci . Dado que |J| > |I|, se tiene que existe j {1, . . . , k}
tal que cj |J Ej | > |I Ej |. Luego, existe x (J Ej ) \ I, luego I + x es independiente. Por lo tanto, (E, I) satisface
el axioma de Aumento, es decir, es Matroide.
Teorema Algoritmo Glot

on-Base
Teorema 1. Si M = (E, I) es matroide, entonces el algoritmo Glot
on-Base(max) devuelve una base de peso m
aximo.
Demostraci
on
Sea S el conjunto devuelto por Glot
on-Base y sea T una base de peso maximo. Notemos que S es una base (esto es
consecuencia de que M en particular es hereditario), luego por axioma de Cardinalidad de la Bases, se sique que S
y T por ser bases, tienen el mismo cardinal, digamos |S| = |T | = l. Sean
S = {s1 , s2 , ..., sl },
T = {t1 , t2 , ..., tl },
ordenados de mayor a menor peso, es decir, w(t1 ) w(t2 ) . . . w(tl ), lo mismo para S.
Queremos demostrar que S es base de peso maximo, procedamos por contradiccion, supongamos que S no tiene peso
m
aximo, es decir, w(T ) > w(S). Luego k {1, . . . , l} tal que w(tk ) > w(sk ), dado que en particular existe al menos
un ndice con esta propiedad, lo podemos tomar como el mas peque
no. Sea S 0 el conjunto S en el momento en que el
algoritmo revisa a tk . Notemos que el algoritmo revisa a tk antes que sk . Sean S 0 = {s1 , s2 , . . . , sk1 } y T 0 = {t1 , t2 , . . . , tk }.
Dado que S 0 , T 0 I (pues, I es hereditario), se tiene por axioma de Aumento, como |S 0 | < |T 0 |, ti T 0 \ S 0 tal
que S 0 + ti I.
Adem
as, como ti T 0 , w(ti ) w(tk ) > w(sk ). Luego, el algoritmo reviso a ti antes que sk , en un momento en que
tiene a alg
un S 00 S 0 . Como S 00 + ti S 0 + ti y S 0 + ti I, se sigue que S 00 + ti I, por lo que el algoritmo debi
o haber
agregado a ti , lo cual no ocurri
o, ya que ti
/ S 0 (lo cual nos lleva a una contradiccion).

aticas

Profesor: Jose Soto
Escriba(s): David Cares, Obed Ulloa y Yasser Nanjari.
C
atedra 6
1.
Recuerdo de Matroides
La noci
on de matroide, ser
a de mucha utilidad para el estudio de grafos y algoritmos, pues nos permitira definir nuevos
algoritmos como el glot
on-base, y asegurar el funcionamiento de estos.
Recordemos la definici
on de una matroide:
Definici
on 1 (Matroide). Una matroide es un par hereditario M = (E, I), donde I P(E) es el conjunto de los
independientes, esto es, tal que cumple:
(i) I =
6 (dado el punto (ii) esto es equivalente a: I).
(ii) X I, Y X = Y I.
Y adem
as satisface cualquiera de los siguientes axiomas equivalentes:
(Aumento) X, Y I, |X| < |Y | = z Y \ X tal que X + z I.
(Aumento debil): X, Y I, |Y \ X| = 2, |X \ Y | = 1 = z Y \ X tal que X + z I.
(Cardinalidad de las Bases): F E, las bases de F tienen el mismo cardinal.
El siguiente lema, tendr
a una especial utilidad en las primeras partes de los contenidos del curso, en lo que respecta al
uso de matroides, pues ser
a necesario probar que ciertos conjuntos seran o no matroides, para lo cual, tanto el Aumento
debil y La cardinalidad de las bases nos ser
an muy u
tiles.
A continuaci
on demostraremos la equivalencia de estos tres axiomas.
Lema 1. (Aumento) (Cardinalidad de las Bases) (Aumento debil).
Dem.
(Aumento)= (Cardinalidad de las Bases). Por contradiccion: Sea F tal que X, Y son bases de distinto cardinal,
supongamos sin perdida de generalidad que |X| < |Y |. Luego, por (Aumento), z Y \ X tal que X + z I pero,
X + z F , lo que contradice el hecho que X es base de F .
(Cardinalidad de las Bases)= (Aumento Debil). Sean I, J I tales que:
|I \ J| = 1, |J \ I| = 2
Si I J I = cualquier z J \ I es tal que I + z I.
Si I J 6 I = J es base de I J por lo tanto todas las bases de I J tienen cardinal |J|. Como I I, I
esta incluido en alguna base de I J.
Recordando que |I| = |J| 1, pues |I \ J| = 1.
Tenemos que existe un elemento z (I J) \ J = J \ I, que podemos agregar a I para que, en particular, sea
base I + z.
I + z I.
(Aumento Debil)= (Aumento). Esta demostracion quedo pendiente en clases, pero el profesor la public
o en Ucursos.
Sean I, J conjuntos independientes tales que |I| < |J|.
Aplicaremos inducci
on sobre k = |I \ J| (en clase se uso |J \ I|).
Si k = 0. Directo, pues |I \ J| = 0 = I J
1

aticas
Si k 1. Sea x I, por inducci

on en I x y J se tiene que existe z J \ (I x) = J \ I, tal que I x + z es
independiente, luego usando nuevamente la hipotesis de induccion en I x + z, pues |I + x z \ J| = k 1,
existe w J \ (I x + z) que hace a K = I x + z + w independiente.
Se tiene que |K \ I| = 2 y |I \ K| = 1. Usando aumento debil existe y K \ I = {x, w} tal que K + y es
independiente.
La clase pasada se demostr
o que si M es matroide, entonces Gloton-base encuentra una base de peso m
aximo (para
toda funci
on w : E R de peso). Esto, de hecho, es una doble implicancia (si y solo si), como lo muestra el siguiente
teorema.
Teorema 1. Si M = (E, I) es un par hereditario que no es matroide, entonces existe una funci
on de peso w : E R tal
que Glot
on-base no devuelve una base de peso m
aximo de E (i.e. Glot
on-base falla).
Observaci
on 1. Tambien se puede decir que todo par hereditario (E, I) que no es matroide, posee una funci
on de peso
para la cual Glot
on-base falla.
Dem. Como M no es matroide, entonces I, J, |I| < |J| tales que z J \ I, I + z
/ I (ya que al no ser matroide,
no se cumple el Ax. de Aumento). Luego, sean a, b R, con 0 < b < a, se define w : E R de la siguente forma:
/ I J
0 si e
a si e I
w(e) =
b si e J \ I
As, Glot
on devuelve I uni
on de elementos de peso 0; luego el peso del conjunto obtenido es w(I) = a|I|.
Si b = a , con suficientemente peque
no, podemos obtener que:
w(J) = a|J I| + b|J \ I| = a|J I| + (a )|J \ I| = a|J| |J \ I| > w(I).
Por lo tanto; Glot
on-Base entrega una base de peso no maximo, por lo que falla.
Teorema 2. Las matroides son exactamente aquellas estructuras donde Glot
on-base funciona.
2.
Notaci
on
Sea M = (E, I) matroide
Independiente: X I
Dependiente: X
/I
Base: I F E tal que I es subconjunto maximal y I I
Circuito: C E minimamente dependiente (C 6 I y J ( C, J I).
X E (X P(E)), se definen:
rango de X: r(X) = M ax {|I| : I X, I I} N
S
generado por X: spanM (X) = {Y X : r(Y ) = r(X)}
Observaci
on 2. la definici
on de span(X) es equivalente a: e span(X) ((e X) (r(X + e) = r(X)))
Ejemplo 1. Si en el grafo a continuaci

on, X 2E corresponde a las aristas rojas, tenemos que span(X) = X + 3

aticas
3
2
Figura 1: span(X) = X + 3
Observaci
on 3. Tras lo visto, el algoritmo Gloton-Base se puede escribir de la siguente forma:
Algoritmo 1: Glot
on-Base(max)
Entrada: G = (E, I) hereditario, w : E R .
Ordenar E = {e1 , ..., em } de mayor a menor peso.
F
for i = 1 . . . m do
if ei
/ span({e1 , ..., ei1 }) then
F F + ei
end
end
return F
Observaci
on 4. La condici
on ei
/ span({e1 , ..., ei1 }) es equivalente a:
ei
/ span(F )
F + ei I (F I)
(esto es, bajo el supuesto que notando que se satisface el invariante que al principio de la iteracion i, F es base de
{e1 , . . . , ei1 }).
Ejemplo 2. Sea un grafo como el que se muestra a continuacion, con los respectivos pesos de cada arista:
4
10
13
10
13
20
11
14
20
11
14
100
12
100
12
5
9
Figura 2
Luego de aplicar el algoritmo, las aristas que este agrega son las marcadas en verde en la figura. Podemos ver que, por
ejemplo, la arista de peso 20 no es agregada pues es generada por las aristas de peso 10 y 13; ya que, para ser agregado
por el algoritmo, el peso de la artista no puede ser generado por aristas de peso menor. En el mismo ejemplo, ahora si
agregamos una arista e, como se ve en la figura, el peso de esta debe ser menor estricto que 12 o menor o igual que 12
(pues las aristas 3,5,12,11 y 10 generan la arista e).

aticas
4
10
13
20
11
14
100
12
3
5
9
Figura 3
3.
Operaciones en Matroides
En este secci
on introduciremos las siguientes operaciones con matroides, las cuales nos serviran en muchos casos para
las previa demostraci
on de si un par hereditario es o no matroide y nos permitiran ademas construir nuevos tipos de
matroides.Estas operaciones son:
1. Truncaci
on a tama
no t N: sea M = (E, I) una matroide. Se define la truncacion de M a tama
no t como
M t = (E, I t ),
donde I t = {X I : |X| t }.
Proposici
on 1. M t es matroide.
Dem. Es f
acil ver que (E, I t ) es un par hereditario, pues I t I y (E, I) es par hereditario. Sean ahora I, J I t
tales que |I| < |J|. Como I, J I t I, e J \ I tal que I + e I. Como |I| < |J| t, |I + e| = |I| + 1 t. Luego
I + e I t , con lo cual se satisface (Aumento).
Ejemplo 3. Sea M una matroide de particion, con (E1 , . . . , Ek ) las partes y (c1 , . . . , ck ) las cotas. Luego:
I(Mt ) = {X E : |X Ei | ci i = 1, . . . , k, |X| t}.
2. Uni
on disjunta o suma directa: sean M1 = (E1 , I1 ) y M2 = (E2 , I2 ) dos matroides tales que E1 E2 = . Se define
la suma directa de M1 y M2 como
M1 M2 = (E1 E2 , I12 ),
donde I12 = {I E1 E2 : I E1 I1 , I E2 I2 }.
Observaci
on 5. Notar que, en general, I12 6= I1 I2
Proposici
on 2. M1 M2 = (E1 E2 , I12 ) es matroide.
Dem. Propuesto.
Definici
on 2 (Matroide laminar). Una matroide laminar es aquella matroide que se obtiene de sumas directas y
truncaciones de matroides uniformes (I = {X E : |X| t}).
Observaci
on 6. Las matroides uniformes se pueden ver como las matroides de particion con una parte, o bien como
truncaciones de las matroides triviales (I = P(E)).
3. Borrado de Matroides: sea M = (E, I) matroide, X E. Se define la Matroide borrando X como
M \ X = (E \ X, {I I : I E \ X}).
Proposici
on 3. M \ X es matroide.
4

aticas
Dem. Propuesto.
4. Contracci
on de Matroides: sea M = (E, I) matroide, X E. Se define la contraccion
M/X = (E \ X, IM/X ),
donde IM/X se calcula de la siguiente forma:
elegir B una base cualquiera de X.
IM/X = {J E \ X : J B I}.
Proposici
on 4. M/X es matroide.
Dem. Propuesto.
Ejemplo 4. Sea G un grafo, X un ciclo de G y B una base de X, como se muestra en la figura ??. Sea M la
matroide gr
afica asociada a G. Luego los conjuntos independientes de M/X seran todos los conjuntos J tales que
J B no tiene ciclos. Es f
acil notar de la figura que J = {1} y J 0 = {1, 2} son independientes de la contracci
on
M/X.
G
1
2
X
Figura 4: X es un ciclo del grafo G (representado con aristas rojas) y B es una base de X (aristas verdes).

aticas

Profesor: Jose Soto
Escriba(s): Francisco Fern
andez, Emilien Garcia y Nicolas Troncoso.
C
atedra 7
1.
Dualidad de matroides
En la clases anteriores, vimos la utilidad de estudiar matroides, ya que en estas el algoritmo Gloton-Base funciona sin
falla. Tambien vimos algunas operaciones sobre matroides que permiten obtener nuevas matroides a partir de las originales.
Despues de repasar las operaciones vistas en la u
ltima clase, vamos a definir una nueva operacion sobre matroides.
1. Truncaci
on a tama
no t N: sea M = (E, I) una matroide. Se define la truncaci
on de M a tama
no t como
M t = (E, I t ),
donde I t = {I I : |I| t}.
2. Uni
on disjunta o suma directa: sean M1 = (E1 , I1 ) y M2 = (E2 , I2 ) dos matroides tales que E1 E2 = . Se define
la suma directa de M1 y M2 como:
M1 M2 = (E1 E2 , I12 ),
donde I12 ={I E1 E2 : I E1 I1 , I E2 I2 }.
3. Borrado de Matroides: sea M = (E, I) matroide, X E. Se define la matroide borrando X como:
M \ X = (E \ X, {I I : I E \ X}).
4. Contracci
on de Matroides: sea M = (E, I) matroide, X E. Se define la contracci
on:
M/X = (E \ X, IM/X ),
donde IM/X se calcula de la siguiente forma:
Elegir B una base cualquiera de X.
IM/X = {J E \ X : J B I}.
Definici
on 1 (Generador de E). Sea M = (E, I) matroide.
F E es generador de E F contiene una base de E ( SpanM (F ) = E)
Definici
on 2 (Dual de una Matroide). Sea M = (E, I) matroide. Se define el dual de M como M = (E, I ), donde:
I = {I E : E \ I es generador en M }.
Ejemplo 1. Sea G = (V, E) grafo o multigrafo. Si M es la matroide grafica de G entonces:
I I E \ I es generador en M
(E \ I) contiene una base de M (i.e. un arbol generador de M )
las componentes conexas de (G \ I) son las mismas que las de G.
En el caso conexo:
I I (G \ I) es conexo.

aticas
Figura 1: G = (V, E) siendo el grafo de la izquierda, en cada grafo que sigue se definen los conjuntos Ii como los conjuntos de
las aristas rojas. En los dos primeros casos, las aristas negras generan a E, por lo tanto I1 e I2 son conjuntos independientes
de M ; sin embargo, el tercer conjunto de aristas negras no es un subgrafo generador de E, por lo tanto I3
/ I .
Definici
on 3 (Cogr
afico). La matroide dual M de una matroide grafica se llama cogr
afica.
Proposici
on 1. Los siguientes son equivalentes:
B es base de M .
(E \ B) es generador de M de cardinalidad m
axima.
(E \ B) es base de M .
Corolario 1. (M ) = M .
Ejercicio 1. (Propuesto) Encontrar la matroide dual de una matroide vectorial (o matroide de representables).
Lema 1. Sea M = (E, I) matroide. M el dual de M es matroide.
Dem. Veamos que M es matroide.
I , pues E = E \ genera a E.
Sean J I , I J. Como J I se tiene que (E \ J) genera a E. (E \ I) (E \ J) luego (E \ I) tambien genera a
E, es decir I I .
(Aumento) Sean I, J I con |I| < |J|. Sea B baseM de E, con B (E \ J). Como (B \ I) B I tenemos que
(B \ I) I. Adem
as I I , por lo que B0 (E \ I) baseM de E. Se tiene que (B \ I) I y mediante aumento
en M se puede hacer crecer (B \ I) a una baseM B de E a
nadiendole elementos de B0 baseM de E. Llamemos B 0
0
al resultado de este proceso. B cumple:
(B \ I) B 0 (E \ I).
Obs: Como |B 0 | = |B| (pues ambos son basesM ), se agregaron a la base la misma cantidad de elementos que se
quitaron al principio, es decir:
|B 0 \ (B \ I)| = |B I| 6 |I \ J| < |J \ I|.
Luego B 0 = (B \ I) (B 0 \ (B \ I)) (los elementos que se quitaron mas los elementos agregados). Como los elementos
agregados son menos que |J \ I|, se tiene que z J \ I que no fue agregado, es decir z (J \ I) \ B 0 tal que
B 0 E \ (I + z) y as I + z I .

aticas
Figura 2: Esquema para ilustrar la manera de construir la base B 0 de E a fuera de I J. Empezamos con elementos de
la base B (que est
a a fuera de J), y le sacamos todos sus elementos que estan tambien en I. Luego, usando aumento en
la matroide, le agregamos los elementos necesarios para obtener B 0 .
Observaci
on 1. Si dos matroides M = (E, I) y M 0 = (E, I 0 ) cumplen cualquiera de las siguientes afirmaciones:
1. I = I 0 .
2. B es base en M B es base en M 0 .
3. C es circuito en M C es circuito en M 0 .
4. X E , SpanM (X) = SpanM 0 (X).
5. X E , rM (X) = rM 0 (X).
Entonces son iguales (M = M 0 ).
Dem. Con I = I 0 , se tiene el resultado, luego basta escribir el conjunto de independientes en funcion de uno de
los criterios anteriores para demostrar la igualdad de matroides. Aqu se presentan algunas caracterizaciones a modo de
demostraci
on.
I = {F E : B base tal que F B}.
I = {F E : F no contiene ningun circuito C}.
I = {F E : rM (F ) = |F |}.
I = {F E : x F, Span(F ) ) Span(F x)}.

aticas
2.
Operaci
on Con Dualidad
Lema 2. Se tienen las siguentes identidades con la funci

on rango:
1. rM (X) = |X| + rM (E \ X) rM (E).
2. r[M \F ] (X) = rM (F X) rM (F ).
3. rM/F (X) = rM (F X) rM (F ).
Dem.
1. Por definici
on de matroide dual:
rM (X) = m
ax{|X B| : B es base de M }
= m
ax{|X \ B| : B es base de M }
= |X| mn{|X B| : B es base de M }
= |X| mn{|B| |B \ X| : B es base de M }
= |X| |B| + m
ax{|B \ X| : B es base de M }.
Sabemos que todas las bases tienen el mismo cardinal dado por rM (E), luego:
rM (X) = |X| rM (E) + m
ax{|B (E \ X)| : B es base de M }
= |X| rM (E) + rM (E \ X).
2. Utilizando la identidad anterior:
r[M \F ] (X) = |X| rM \F (E \ F ) + rM \F ((E \ F ) \ X)
= |X| rM (E \ F ) + rM ((E \ (F X))

= |X| |E \ F | rM (E) + rM (F ) + |E \ (F X)| rM (E) + rM (F X)
= rM (F ) + rM (F X).
En esto u
ltimo se ocup
o que |X| |E \ F | + |E \ (F X)| = 0.
3. Sea A un conjunto independiente de (M \ F ) maximal dentro de X:
rM/F (X) = |A| = |BF A| |BF |
= rM (F A) rM (F )
= rM (F X) rM (F ).
Lema 3. Si M = (E, I) matroide, F E, M/F = (M \ F ) .
Dem. Demostremos este lema utilizando el rango. De las partes 2 y 3 del lema anterior:
rM/F (X) = rM (F X) rM (F ) = r[M \F ] (X).
Luego rM/F (X) = r[M \F ] (X) y por observaci
on 1, son iguales.

aticas
3.
Matroide Gr
afica
Proposici
on 2. Sean M = (E, I) matroide, F1 , F2 E, F1 F2 = :
(M/F1 ) \ F2 = (M \ F2 )/F1 .
M \ (F1 F2 ) = (M \ F1 ) \ F2 .
M/(F1 F2 ) = (M/F1 )/F2 .
Dem. Ejercicio.
Que significa la contracci
on en una matroide grafica? Sea G un multigrafo cualquiera.
De la Figura 3 podemos observar que hay dos casos:
Si e no es loop:
M/e = (E e, {F E e : F + e I})
G/e = ((V \ {u, v}) + wuv , E 0 /e).
Donde f E e con f = ab definimos f 0
0
f =
E 0 como sigue:
ab
wuv b
wuv a
wuv wuv
si {a, b} =
6 {u, v}
si a {u, v} y b
/ {u, v}
si b {u, v} y a
/ {u, v}
si a {u, v}, b {u, v}
Si e es loop M/e = M \ e, es decir, basta borrarla para obtener la contraccion.
Figura 3: A la izquierda est

a la matroide M original, con colores distintos para cada arista incidente a u o v, y de hecho
se puede notar mejor lo que les ocurre durante la contraccion de M . En rojo estan la arista e que vamos a sacar de M y
sus vertices. A la derecha se encuentra la matroide M/e contraida. De esta manera se puede notar bien porque se llama
contracci
on de una matroide.

aticas
Profesor: Jose Soto
Escriba(s): Juan Marshall, Rodrigo Moreno y Benjamn Ruiz.
C
atedra 8
1.
Complementos sobre Matroides

Revisaremos en algunas otras definiciones y propiedades de matroides para luego pasar a los problemas de largo mnimo.
Definici
on 1 (Menor de una matroide). Sean M1 , M2 matroides. M1 se dice menor de M2 cuando la primera se puede
obtener a partir de las operaciones de borrado y contraccion sobre la u
ltima. Veamos un ejemplo de esto con matroides
gr
aficas.
En la figura a continuaci
on se muestran los grafos G1 y G2 , donde G1 se obtiene de borrar y/o contraer las aristas
marcadas en el sentido de multigrafo usando que para todo multigrafo G y toda arista e de G, se tiene M (G)e = M (Ge)
y que M (G/e) = M (G)/e, concluimos que M (G1 ) es menor de M (G2 ). Esto permite extender la definicion para menor
en grafos tambien.
G2
G1
Figura 1: G1 es menor de G2
La discusi
on anterior muestra que la siguiente propiedad de matroides graficas se .
Proposici
on 1 (Las matroides gr
aficas son cerradas para menores.). Una matroide menor de una matroide gr
afica es
tambien una matroide gr
afica.
Uno de los problemas que qued
o pendiente de las u
ltimas clases fue encontrar las condiciones suficientes y necesarias
para que el algortimo Glot
on-Independiente funcionara. Esto se resuelve con el siguiente teorema:
Teorema 1 (Correctitud Glot
on-Independiente). Glot
on-Independiente devuelve un conjunto independiente de peso m
aximo.
Demostraci
on. Glot
on-Independiente es equivalente a Gloton-Base en la matroide M+ = M \(E\E + ),con E + los elementos
de E de peso positivo. La correctitud sigue de la de este u
ltimo algoritmo.
1.1.
Dibujos de un (multi)grafo
Pasemos ahora a estudiar la noci

on de dibujo de un (multi)grafo. Comenzamos con la deficion formal de los que es un
dibujo.
= (V , E)
de una asignaci
Definici
on 2 (Dibujo). Un dibujo de un de un (multi)grafo G = (V, E) es la imagen G
on que
satisface:
v V 7 v R2 , inyectiva.

aticas
e E 7 e R2 , con e una curva homeomorfa al intervalo (0, 1) con los mismos extremos que los asociados a
extremos de e.
Veamos algunos ejemplos de dibujos.
Figura 2: Multigrafo
Como vemos en la figura, algunos dibujos admiten que las imagenes de sus aristas sean disjuntas. Estos se llaman
dibujos planos y motivan la siguiente definici
on.
Definici
on 3 ((Multi)Grafo Planar). Un (Multi)Grafo se dice planar si este admite un dibujo plano.
Figura 3: Ejemplo de grafo planar: K4 .
Figura 4: Ejemplo de grafo que no admite dibujo plano: K5 .

Obs 1. Habitualmente denotamos al conjunto de caras como F .
con V = {
= {
Al borrar de R2 todos los puntos de V E
v | v V }, E
e | e E} obtenemos regiones que llamamos
caras del dibujo G = (V , E). Estas regiones (marcadas con una cruz en la figura anterior) nos permitiran hablar del dibujo
dual que definiremos a continuaci
on.
= (V , E)
un dibujo plano de G = (V, E), realizamos los siguiente:
Definici
on 4 (Dibujo Dual). Dado G
Elegir un punto v de cada cara f F .
Para cada e E dibujar una arista e conectando los puntos elegidos en el paso anterior en las caras a ambos lados
de de modo que e intersecte solo a e.
= (V , E
) de un (multi)grafo G = (V , E )
Obtenemos un dibujo G
A continuaci
on damos un ejemplo de un dibujo dual de un dibujo plano, aqu los vertices del dibujo dual est
an marcados
con un cuadrado rojo y sus aristas las lineas segmentadas, el resto corresponde al dibujo plano original.
2

aticas
Figura 5: Ejemplo de dibujo dual.

Obs 2. El (multi)grafo del dibujo obtenido resulta ser un dual del grafo original, este no necesariamente es u
nico y va a
depender de c
omo se dibuja el grafo original, como vemos en el siguiente ejemplo, tenemos la misma figura anterior pero
dibujada en el plano de una manera diferente, este dibujo produce un dual distinto al anteriomente obtenido.
Figura 6: Ejemplo de que el dibujo dual no es u

nico.
Notamos que el grafo dual resultante tiene grado maximo 5, a diferencia de la figura anterior, en donde el grafo tena
grado m
aximo 6, luego no pueden ser isomorfos.
Proposici
on 2. Sea G un grafo y G un dual (plano). Entonces M (G) y M (G ), las matroides asociadas, son duales.
Demostraci
on. I es independiente en M (G ) E \I es generador de M (G ) cc(G \ I ) = cc(G ) I no contiene
un ciclo en G I es independiente en M (G).

aticas
Figura 7: Representaci
on: Un corte en G contiene un ciclo en el grafo original G.
on: Los complementos de las base del grafo original son bases del grafo dual.
2.
Problema del (Di)Camino de Largo Mnimo
Ahora comenzaremos a ver el problema de encontrar un camino de costo mnimo en un grafo dirigido. Nos interesa,
por ejemplo, encontrar un camino que tome el menor tiempo posible, para ir desde un lugar a otro. El tipo de algoritmo
que veremos lo utilizan aplicaciones como waze o google maps.
Definici
on 5. Digrafo, o grafo dirigido.
Un digrafo o grafo dirigido corresponde a una tupla G = (V, E), donde:
V y E son conjuntos finitos.
Los elementos de V se llaman vertices.
Los elementos de E se llaman arcos.
Cada e E tiene asociado un nodo de cola t(e) V y un nodo cabeza h(e) V (que podran ser iguales).
Un arco es representado con una flecha donde la punta de la flecha corresponde a la cabeza del arco.
Dos arcos con igual cola y cabeza se llaman paralelos.
Dos arcos se dicen antiparalelos si la cabeza de uno es la cola del otro y viceversa.
Un arco se dice loop cuando tiene igual cola y cabeza.
Cuando no hay arcos paralelos, el digrafo se dice simple, en tal caso e = (t(e), h(e)) V V, E V V.
Se definen an
alogamente a grafos dipaseo, dicamino y diciclo, donde la condicion extra es que siempre se sigue la
direcci
on del arco.

aticas
A continuaci
on algunos ejemplos de digrafos.
1
Figura 9: (1) Arcos antiparalelos, (2) un loop y (3) arcos paralelos.
(a)
1
(b)
6
2
7
3
4
8
(c)
(d)
(e)
Figura 10: (a) Dipaseo, (b) dicamino, (c) no es dicamino, (d) diciclo, (e) no es diciclo.
Problema del dicamino de largo mnimo

Dado G = (V, E) grafo dirigido, l : E R funcion de largo, encontrar un dicamino P de s a t de largo mnimo. Esto es
k1
X
l(P ) = mn{l(Q) : Q es dicamino de s a t}, donde el largo de un paseo Q = v1 v2 . . . vk , es l(Q) =
l(vi , vi+1 ) (Q podra
i=1
repetir aristas).
Obs 3. En general, encontrar dicaminos de largo mnimo es complicado, de hecho este problema es NP-completo. Esta
noci
on se estudia m
as a fondo en cursos de complejidad.
Veamos primero unos casos simples:
(1) Encontrar un (s, t)-dipaseo de largo mnimo, cuando los acros pesan lo mismo
Si l(e) = 1 e E, se puede resolver con una version dirigida de BFS donde en lugar de ver el corte, vemos las aristas
que salen. Naturalmente aparecen
arboles dirigidos, a estos les llamamos arborescencias, ver el ejemplo a continuaci
on.
Figura 11: Representacion: Arborescencia.

aticas
Figura 12: Camino mnimo entre s y t, cuando los arcos tienen el mismo peso usando BFS dirigido a partir de s.
Notaci
on: W=k (u, v) : Conjunto de todos los (u, v)-dipaseos con exactamente k arcos.
(2) Encontrar un (s, t)-dipaseo de largo mnimo, que use exactamente k arcos
Consideremos ahora problema de encontrar un (s, t)-dipaseo de largo mnimo, que use exactamente k arcos. Es decir
encontrar P W=k (u, v) tal que l(P ) = mn{l(Q) : Q W=k (u, v)} =: D(u, v; k), los casos bases son:
Si k = 0
0,
,
l((u, v)),
,
D(u, v; 0) =
Si k = 1
D(u, v; 1) =
si u = v.
.
si no.
si (u, v) E.
.
si no.
Obs 4. Si se tiene interes en un (u, v)-dipaseo de cardinalidad k, Como se puede encontrar en terminos de paseos de
menor cardinalidad?
Proposici
on 3. Sea P W=k (u, v) de largo mnimo, k 1 sea e = (w, v) el u
ltimo arco. Entonces P 0 = P e
W=k1 (u, v) es de largo mnimo en W=k1 (u, v).
Demostraci
on. Sea R W=k1 (u, w) de largo mnimo, luego R + e W=k (u, v) y entonces l(R + e) l(P ). Por otro lado
l(P 0 ) = l(P ) l(e) l(R + e) l(e) = l(R) y como tenemos que P 0 W=k1 (u, w), entonces l(P 0 ) = l(P ) y por tanto P 0
es optimo.
Figura 13: Si P = (u, v)-dicamino es de largo mnimo entonces P e, con e = wv es (u, w)-dicamino de largo mnimo.
Notaci
on:
N + (v) = {w V : (v, w) E}.
N (v) = {w V : (w, v) E}.
Una idea para encontrar el dipaseo de largo mnimo de cardinalidad k es ir mirando todos los vecinos, para ser m
as
precisos:
Proposici
on 4. D(u, v; k) = mn{D(u, w; k 1) + l((w, v)) : w N (v)}.
6

aticas
Demostraci
on.
() Se tiene pues D(u, v; k) es
optimo.
() Por proposici
on anterior.
Por lo que hemos hecho, conviene calcular la distancia de s a todos los v V , y no solo a t. As se har
a un
algoritmo basado en programaci
on din
amica, cuyo espritu es, mas o menos, ir guardando datos en tablas, y utiliz
andolos
iterativamente.
Algoritmo 1: Paseos mnimos desde s.

0,
si u = v.
Primero calculamos D(s, v; 0) =
.
, si no.
for j {1, ..., k} do
for v V do
D(s, v; j) = mn{D(s, w; j 1) + l(w, v) : w N (v)}.
(s, v; j) = argmn{D(s, w; j 1) + l(w, v) : w N (v)} (null si no existe).
end
end
Obs 5. Notamos que guarda los precursores, de modo que el pen
ultimo nodo del (s, t)-camino encontrado por el algoritmo
es vk := (s, t, k), el anterior a ese es vk1 = (s, t; k 1) y en general el i-esimo nodo del camino es vi = (s, t; i).

aticas

Profesor: Jose Soto
Escribas: Catalina Pesce e Ian Vidal
Fecha: 29 de Agosto 2014.
C
atedra 9
1.
Recuerdo de la clase pasada
En la clase anterior describimos el algoritmo de paseo de largo mnimo desde un vertice s, utilizando k arcos. Volveremos a plantear este algoritmo para estudiar su correctitud y complejidad.
Algoritmo 1: Algoritmo de paseo mnimo desde s hasta un vertice v V con k arcos.
Entrada: G = (V, E); l : E R.
for v V do
0
si v = s,
D(s, v; 0) =
+ si v 6= s.
end
for j = 1 . . . k do
for v V do
D(s, v; j) = mn
{D(s, w; j 1) + l(w, v)}.
wN (v)
(s, v; j) = argmn {D(s, w; j 1) + l(w, v)}.

wN (v)
end
end
1.1.
Correctitud del algoritmo 1
Primero, notemos que el algoritmo opera sobre un n

umero finito de nodos una cantidad finita de veces sin entrar en
ciclos, por lo que el algoritmo termina. Ahora, veamos que cumple con nuestra definicion de distancia, es decir, que si
consideramos D(s, v; j) el valor del paseo mnimo entre s y v con j arcos, el valor calculado por el algoritmo es realmente
el que deseamos, para ello lo probaremos a traves de una doble desigualdad.
(6) Basta notar que si R es un paseo mnimo desde s hasta w con j 1 arcos, con w N (v), esto nos asegura
que R + (w, v) es un paseo de j arcos desde s hasta v. Por lo que de nuestra definicion de D(s, v; j) se obtiene la
desigualdad deseada.
(>) Sea P un s-v camino con j arcos tal que l(P ) = D(s, v; j). Suponiendo que D(s, v; j) es finito, este pase existe
pues es el mnimo de un conjunto finito, entonces P = u1 u2 . . . un1 un ; u1 = s, un = v, notando que:
l(P ) = l(u1 . . . un1 ) + l(un1 un )
l(P ) >
l(P ) >
D(s, v; j) >
(D(u1 , un 1; j 1) + l(un1 , un ))
mn
un1 N (un )
mn
(D(s, un 1; j 1) + l(un1 , v))
un1 N (v)
mn (D(s, w; j 1) + l(uw , v))
wN (v)
(1)
(1): La demostraci
on anterior tambien vale si no existe paseo desde s a v con j arcos.En dicho caso tanto como el
lado izquerdo de nuestra ecuaci
on vale +.

aticas
1.2.
Complejidad del algoritmo 1
Estudiemos ahora la complejidad del algoritmo de paseos mnimos. Consideremos n = |V |, m = |E|, entonces tenemos
lo siguiente:
Asignar las distancias de s a v con j = 0 es O(n).
Dado j [k], v V , asignar el valor a D(s, v; j) es O(n).
Esto se realiza para cada v en V y cada j [k], se tiene un total de O(kn2 ) operaciones. Luego la complejidad total es
O(n) + O(kn2 ) = O(kn2 ). Ahora bien, podemos analizar en mayor profundidad este resultado para llegar a una cota m
as
fina, como O(k(n + m)) = O(kn + km), d
onde O(kn) viene de llenar la tabla y O(km) es el calculo de los mnimos, ya
que cada termino que aparece en alg
un mnimo se puede poner en correspondencia con un arco del digrafo.
Propuesto 1. Modifique el algoritmo anterior para calcular un paseo mnimo con k arcos, par (u, v) V V . Esto se
puede lograr en O(kn3 ) O(k(n2 + mn)).
Ejemplo 1. Veamos la relaci
on entre encontrar un paseo mnimo y un camino mnimo del vertice s al vertice t, sin
restringir la cantidad de arcos a usar. En el siguiente ejemplo (Figura 1.) hay un ciclo negativo, si buscamos el paseo de
largo mnimo podramos pasar infinitas veces por el ciclo para obtener un paseo de largo . En cambio, cuando buscamos
un camino entre v1 y v2 no se pueden repetir vertices, por lo que no se puede entrar al ciclo, eliminando la posibilidad
de sumar largos negativos indefinidamente. Entonces el camino Pv1 -v2 de largo mnimo sera {v1 , u1 , v2 } con l(Pv1 -v2 ) = 2,
mientras el paseo Wv1 -v2 de largo mnimo tendr
a infinitas repeticiones del ciclo y su largo sera l(Wv1 -v2 ) =
Figura 1.
2.
Sobre paseos mnimos con l conservativa
Definici
on 1 (Funci
on conservativa). Sea l : E R una funcion de largos, se dice conservativa si el digrafo G = (V, E)
no tiene diciclos negativos.
A continuaci
on veremos varios resultados aplicados a funciones de largo conservativas, lo cual nos permitir
a presentar
al final de la clase el algoritmo de Bellman-F ord que entrega un camino de largo mnimo en un grafo dirigido.
Teorema 1. Sea l : E R una funci
on de largos conservativa, entonces
mn
P Wk (u,v)
l(P ) =
con:
Wk (u, v) el conjunto de paseos de u a v con a lo m
as k arcos.
Pk (u, v) el conjunto de caminos de u a v con a lo m
as k arcos.
Demostraci
on.
() Ya que Pk (u, v) Wk (u, v), pues todo camino es un paseo, luego se tiene:
mn
P Wk (u,v)
l(P )
mn
W Pk (u,v)
l(P ) .
mn
P Pk (u,v)
l(P )

aticas
() Sea P Wk (u, v) un mnimo con la menor cantidad de arcos. Demostraremos que P es un camino: Si P no es
un camino, entonces P = v1 v2 . . . vi1 vi vi+1 . . . vj1 vj vj+1 . . . vk , con vi = vj , i 6= j.
Notemos que C = vi . . . vj es un ciclo, pues es un paseo que empieza y termina en el mismo nodo, por lo que l(C) > 0.
Consideremos el paseo P 0 = v1 v2 . . . vi1 vi vj+1 . . . vk , luego
l(P 0 ) = l(P ) l(C) 6 l(P ) .
Como se tena que P era un paseo mnimo, P 0 tambien lo es, contradiciendo la minimalidad (en el sentido del n
umero
de arcos).
Luego, como se tiene (6) y (>) se cumple la igualdad deseada.
Definici
on 2. Sea G = (V, E) digrafo, l : E R conservativo. Se definen:
d(u, v) =
mn
P P(u,v)
dk (u, v) =
mn
l(P ) =
P Pk (u,v)
mn
P W(u,v)
l(P ) =
l(P ) .
mn
P Wk (u,v)
l(P ) .
Observaci
on 1. De la definici
on anterior podemos pensar que d(, ) es una distancia con signo, pero:
Debido a que estamos trabajando con caminos dirigidos podemos tener un camino de u a v pero ninguno de v a u,
por lo que d(u, v) < + y d(v, u) = +. Por lo tanto, d(, ) no cumple con la simetra, es decir, d(v, u) 6= d(v, u).
d(u, v) no es necesariamente positiva como una distancia, podemos tener aristas de largo negativo.
Sin embargo, d(, ) satisface la desigualdad triangular, enunciemos esto en forma de proposicion.
Proposici
on 1. Sea d(, ) la funci
on de la Definicion 2., entonces u, v, w V se tiene d(u, v) d(u, w) + d(w, v).
Demostraci
on. Tenemos dos casos, si el lado derecho de la desigualdad es + entonces se tiene directamente la desigualdad. Si esto no sucede, tomamos Q un u-w camino con l(Q) = d(u, w) y R un w-v camino con l(R) = d(w, v), entonces
Q+R es un u-v paseo de largo d(u, w)+d(w, v) = d(u, v) l(R+Q) = d(u, w)+d(w, v), con lo que se tiene lo pedido.
Corolario 1. Sea l : E R una funci
on de largos conservativa, W(u, v) el conjunto de todos los paseos de u a v, P(u, v)
el conjunto de todos los caminos de u a v y d(u, v) la distancia mnima de u a v. Entonces:
d(u, v) =
mn
P W(u,v)
l(P ) =
mn
P P(u,v)
l(P ) .
Demostraci
on. Es una consecuencia directa del teorema anterior cuando k y de nuestra definicion de d(u, v).
Teorema 2. Sea l : E R una funci
on de largos conservativa, k > 1, P Pk (u, v) de largo mnimo y e = (w, v) el
u
ltimo arco de P . Entonces:
P 0 = P Pk1 (u, w) es de largo mnimo.
Demostraci
on. Sea R Pk1 (u, v) de largo mnimo. Consideremos:
(Caso 1 ) Si R + e es un camino, la demostracion es identica al teorema de la clase anterior.

aticas
(Caso 2 ) Si R+e es un paseo (contiene un ciclo) procedemos de la siguiente manera. Como R Pk1 (u, v) entonces
R no tiene ciclos, luego R + e posee un u
nico ciclo y se cumple que v R. Sea Q el subcamino de R que conecta u
y v, sea C el ciclo de R + e (ver Figura 2.), entonces:
l(R + e) = l(Q) + L(C)
0 6 l(C) = l(R + e) L(Q)
(2)
6 l(R + e) l(P )
(3)
= l(R) l(P e) 6 0 .
(4)
(2) : l es conservativa
(3) : Recordar que P Pk (u, v), por lo que l(Q) > l(P )
(4) : (P e) Pk1 (u, v), y R es el camino de largo mnimo de Pk1
l(R) = l(P e) = (P 0 ) .
Figura 2.
Teorema 3 (Criterio de optimalidad de Bellman). Sea l una funci
on de largo conservativa. Si P es un u-v camino de
largo mnimo (con k arcos) y Q es un subdicamino (un subcamino dirigido) de P , digamos de a a b con t arcos. Entonces
Q es un dicamino de largo mnimo (de entre aquellos con t arcos) de a a b.
Demostraci
on. Se obtiene directamente del Teorema 2., removiendo arcos al principio y al final de P .
Proposici
on 2. Sea l conservativa. Entonces
d(u, v) =
mn
wN (v)
d(u, w) + d(w, v) ,
(5)
Adem
as, para k 1 se tiene

dk (u, v) = mn

mn
{dk1 (u, w) + l(w, v)}, dk1 (u, v)
(6)
wN (v)
Demostraci
on. Primero demostremos (5).
() Notemos que cada termino del lado derecho es el largo de un u-v paseo, dado que l es conservativa, entonces el
mnimo paseo/camino tiene largo menor que cualquier otro paseo. Por lo tanto se tiene la desigualdad.
() Debido al criterio de Bellman tenemos que si d(u, w) es el largo de un u-w camino mnimo, entonces d(u, w) +
l(w, v), tomando aquel w que tenga l(w, v) mnimo, sera el largo de un u-v camino mnimo. Por lo que se tiene la
otra desigualdad. Concluimos, entonces, que la la igualdad es cierta.
La demostraci
on de (6) es an
aloga.
Observaci
on 2. La f
ormula (5), en general, no sirve para hacer un algoritmo de programacion dinamica donde calculemos
la tabla con los valores de la distancia d(, ). En cambio, la formula (6) s lo permite.
4

aticas
3.
Algoritmo de Bellman-Ford
Finalmente, podemos introducir el algoritmo de Bellman-Ford (Schimbel 1955, Ford (1956), Bellman (1958), Moore
(1959)), que entrega un s-v camino de largo mnimo en un grafo dirigido, para todo v V . A continuacion se presenta el
pseudo-codigo del algoritmo, lo estudiaremos en profundidad la proxima clase.
Algoritmo 2: Algoritmo de Bellman-Ford
Entrada: G = (V, E) digrafo; l : E R conservativa; s V .
for v V do
0
si v = s,
d0 (s, v) =
+ si v 6= s.
end
for i = 1 . . . n 1 do
for v V do
A = mn {di1 (s, w) + l(w, v)}.
wN (v)
w = argmn {di1 (s, w) + l(w, v)}, si no existe w =null.

wN (v)
end
if A < di1 (s, v) then
di (s, v) = A.
i (v) = w .
end
else
di (s, v) = di1 (s, v).
i (v) = i1 (v).
end
end

aticas

Profesor: Jose Soto
Escriba(s): Piero Zanoco, Felipe Garrido, Guido Besomi
Fecha: 01 de Septiembre 2014
C
atedra 10
1.
Recuerdo
Estamos estudiando el problema de encontrar caminos y paseos de costo mnimo en grafos dirigidos. Formalmente,
dado un digrafo G = (V, E) y una funci
on de largo l : E R, definimos:
Pi (u, v) = {u-v caminos con i arcos}.
Wi (u, v) = {u-v paseos con i arcos}.
di (u, v) :=
mn
P Wi (u,v)
l(P ).
Introduciremos ahora la noci

on de funci
on de largo conservativa y veremos como se relaciona con la definici
on de
distancia recien presentada:
Definici
on 1. La funci
on de largo l se dice conservativa si y solo si @ ciclo C con l(C) < 0.
Proposici
on 1. Si la funci
on de largo l es conservativa, entonces di (s, v) =
mn
P Pi (u.v)
l(P ).
Proposici
on 2. Sea l conservativo o no (no importa). Entonces
di (s, v) =
mn
wN (v)+v
{di1 (s, w) + l(w, v)} , donde abusando de notacion suponemos l(v, v) = 0.
o bien,
di (s, v) = mn{ mn {di1 (s, w) + l(w, v)}, di1 (s, v)}.
wN (v)
Observaci
on 1. Si di (s, v) < , definimos w = arg mnwN (v)+v {di1 (s, w) + l(w, v)}. Entonces, w es predecesor
de v en alg
un s-v paseo de Wi (s, v) mnimo. Si di (s, v) = , entonces v no se puede alcanzar desde s con i arcos.
Principio de optimalidad de Bellman (para l conservativo). Si P es u-v camino mnimo, Q subcamino de P
(entre x e y), entonces Q es x-y camino mnimo.

aticas
2.
Algoritmo de Bellman - Ford

Algoritmo Bellman-Ford.
Algoritmo 1: Algoritmo Bellman-Ford

Input: G = (V, E), l : E R (no necesariamente conservativo), s V .
Output: Si l es conservativo, entonces devuelve una arborescencia de caminos mnimos desde s. Si l no es
conservativo y existe un ciclo negativo alcanzable desde s, entonces el algoritmo lo reporta.
for v V do
0
s=v
d0 (s, v) =
+ s 6= v
end
for i = 1, ..., n 1 do
for v V do
di (s, v) di1 (s, v)
end
for e = (w, v) E do
if di (s, v) > di1 (s, w) + l(w, v) then
di (s, v) di1 (s, w) + l(w, v)
(v) w
end
end
end
Dejamos pendiente hasta el final de la clase como se revisa la existencia de un ciclo negativo alcanzable desde s.
Complejidad: O(n(n + m))
Correctitud
Teorema 1. Al final de la iteraci
on i {0, ..., n 1}. Sean
Ri = {v V : (x) est
a definido} {s}.
Fi = {((v), v) : v Ri s}.
Hi = (Ri , Fi ).
Entonces se tiene que:
(1) Para todo (w, v) Fi , di (s, v) di (s, w) + l(w, v)
(2) Si Hi tiene un ciclo C, entonces l(C) < 0.
(3) Si l es conservativa, entonces Hi es una arborescencia con raz s.
Antes de demostrar el teorema, recordemos la definicion de arborescencia:
Definici
on (Arborescencia): Un digrafo H = (R, F ) es una arborescencia si satisface:
1. Su grafo subyacente es
arbol.
2. v R, el u
nico s-v camino en el
arbol subyacente esta dirigido de s a v.
Demostraci
on del teorema 1. El caso i = 0 es f
acil de probar.
Sea i 1. Probemos (1): Sea e = (w, v) Fi . Por la definicion de Fi , w = (v). Esto quiere decir que en alguna
iteraci
on j i el algoritmo fij
o (v) w, y de ah en adelante se mantuvo. En ese momento:

aticas
dj (s, v) > dj1 (s, w) + l(w, v) se cambio a dj (s, v) = dj1 (s, w) + l(s, w).
En los pasos siguientes, di (s, v) = dk (s, v), k entre j e i, si no, hubiese cambiado . Ademas, dj1 (s, w) di (s, w)
pues di (s, ) es decreciente en i. Luego,
di (s, v) = dj (s, v) di (s, w) + l(w, v)
di (s, v) di (s, w) + l(w, v)
Probemos ahora (2): Sea C el ciclo de Fi y sea (w, v) el arco que entro u
ltimo a Fi de C, digamos en la j-esima
iteraci
on. Justo antes de entrar, tenamos que:
dj (s, v) > dj1 (s, w) + l(w, v) dj (s, w) + l(w, v)
dj (s, w) > dj (s, v0 ) + l(w, v)
Por lo tanto
(1)
donde v0 corresponde a w.
Por la parte uno, se tiene que para todo k, dj (s, vk+1 ) dj (s, vk ) + l(vk , vk+1 ). Sumando esta desigualdad sobre todo
k y luego sum
andola a (1) se obtiene:
X
X
X
dj (s, vk ) +
l(vk , vk+1 )
dj (s, vk+1 ) >
vk V (C)
vk V (C)
{z
S1
{z
S2
vk V (C)
{z
l(C)
Notando que S1 = S2 se concluye que l(C) < 0.
Probemos (3): Por la parte anterior, Hi no tiene ciclos dirigidos. Ademas, cada vertice en Ri s posee degH
(v) = 1
i
(n
umero de arcos entrantes a v en Hi ). Luego, ning
un vertice tiene dos arcos entrantes. Por lo tanto, en Hi tampoco
podemos encontrar ciclos no dirigidos.
Luego, el grafo subyacente es acclico. Adem

as, como degH
(v) = 1, v Ri s y degH
(s) = 0, al partir de v, podemos
i
i
devolvernos a (v), luego a ((v)) y asi, hasta llegar a s, del cual no se puede seguir pues no tiene vecinos entrantes.
Hi es arboresencia con raz s.
Volvemos al estudio de la correctitud de Bellman-Ford.
Si l es conservativo, el u
nico s-v camino (v Rn1 ) en Hn1 es un camino en Pi (s, v) de largo mnimo. Probemoslo:
Por la parte (1) del teorema anterior, dn1 (s, vk ) dn1 (s, vk1 ) + l(vk1 , vk ), pero el camino mas largo es de n 1
pasos, luego dn1 (s, vk ) = d(s, vk ) (largo del camino mnimo entre s y vk ).
d(s, vk ) d(s, vk1 ) + l(vk1 , vk ) d(s, vk1 ) + d(vk1 , vk ),
pero por desigualdad triangular; d(vk1 , vk ) + d(s, vk1 ) d(s, vk ), entonces dn1 (s, vk ) = dn1 (s, vk1 ) + l(vk , vk1 ).
t
P
Por lo tanto dn1 (s, v) =
l(vk1 , vk ), es decir, el camino de s a v en Hi es el camino mnimo y se conlcuye la
k=1
correctitud. Hemos probado el siguiente teorema.

Teorema 2. Si l es conservativo, H = (Rn1 , Fn1 ) es una arborescencia que codifica caminos mnimos de s a todo nodo.
Surge la pregunta de, en caso que exista un ciclo dirigido, cual es la mejor forma de encontrarlo.
Teorema 3. Sea l funci
on de largos arbitraria. Existir
a C ciclo negativo alcanzable desde s ssi v tal que dn (s, v) <
dn1 (s, v) y para encontrarlo, basta realizar el for por una unidad m
as i = n.
Luego, para:
(i) Revisar si existe ciclo negativo alcanzable desde s se revisa si dn (s, ) = dn1 (s, ) (si son distintos, existe ciclo
negativo alcanzable desde s).
(ii) Devolver ciclo negativo, se revisa cada Hi , i = {1, ..., n}. Si en alg
un momento se crea un ciclo, parar y devolver (se
utiliza BFS para encontrarlo).
Observaci
on 1. Es f
acil verificar que incluso con estas operaciones extras, el algoritmo tiene complejidad O(n(n + m)).
3

aticas
Observaci
on 2. Es posible determinar si l es conservativa en tiempo O(n2 (n + m)) aplicando Bellman-Ford desde cada
nodo. Existen formas m
as r
apidas. Una de ella es usar el algoritmo de Floyd-Warshall que se ve mas adelante en el curso
para detectar si las matrices dn (, ) y dn1 (, ) son distintas.

aticas

Profesor: Jose Soto
Escriba(s): David Cares, Obed Ulloa e Ian Vidal.
Fecha: 5 de Septiembre 2014 .
C
atedra 11
1.
Recuerdo C
atedra Anterior
De los metodos vistos en clases anteriores, tenemos para un digrafo G = (V, E), con funcion de largo ` : E R, los
siguientes algoritmos:
Paseo de n
umero fijo de arcos (k arcos), que es de complejidad O(k(n + m)).
Caminos/Paseos:
con ` constante mayor o igual a cero, cuya complejidad es O(n + m).
con ` conservsativo, de complejidad O(n(n+m)) y aplicando Bellmand-Ford se lograba una complejidad O(nm).
con ` programaci
on din
amica sobre orden topologico y G acclico, y en este caso la complejidad es O(n + m)
(visto en clase auxiliar).
Para todo par de vertices y l conservativo, tenemos, con sus respectivas complejidades:
Bellman-Ford iterado, O(n2 m).
Multiplicaci
on de Matrices(
algebra tropical), O(n3 log(n)) (visto en clase auxiliar).
Floyd-Warshall, O(n3 ) (que veremos a continuacion).
2.
M
etodo de Floyd-Warshall
En esta secci
on introduciremos un metodo para encontrar los caminos mnimos entre dos nodos. Este metodo se conoce
como metodo de Floyd-Warshall. Dado un digrafo G = (V, E) y ` : E R conservativo, queremos calcular la matriz
M (v, w) = d(v, w), matriz de las distancias entre dos nodos del digrafo.
Observaci
on 1. Si conocemos M es f
acil calcular los caminos.
Propuesto: Dado M , calcule un s-t-camino mnimo.
La idea tras el metodo de Floyd-Warshall es numerar los nodos v1 , v2 , . . . , vn y definir:
i (u, v) = mn{`(P ) : P u-v-paseo | V (P ) \ {u, v} {v1 , . . . , vn }}.1
|
{z
}
nodos internos
Si supieramos i i, entonces s
olo basta considerar d(u, v) = n (u, v).Esto se debe a que si ` es conservativo, los paseos
mnimos y los caminos mnimos tienen igual largo,por esto, nos preguntamos como podemos calcular i en funci
on de
i1 . Pues bien, notemos que:

0
si u = v.
0 (u, v) =
+ si u 6= v.

`(P ) : u-v-paseo con nodos internos en {v1 , . . . , vi } que tenga a vi como nodo interno.
i (u, v) =
`(P ) : u-v-paseo con nodos internos en {v1 , . . . , vi } que no tenga a vi como nodo interno.
Luego,
i (u, v) = mn{i1 (u, vi ) + i1 (vi , v), i1 (u, v)}.
1 si
bien es cierto en clase hablamos de caminos es m

as f
acil argumentar en t
erminos de paseos.

aticas
Consideremos un u-v-paseo
optimo P cuyos nodos internos estan en {v1 , v2 , . . . , vi } y que pase por vi . Sean P1 y P2 subpaseos de P tal que P1 es un u-vi -paseo y P2 un vi -v-paseo. Luego es claro que i1 (u, vi ) `(P1 ) i1 (vi , v) `(P2 )
pues los i1 son
optimos. Podemos entonces enunciar y demostrar el siguiente lema.
Lema 1. `(P ) = i1 (u, vi ) + i1 (vi , v)
Dem.
: pues i1 (u, vi ) + i1 (vi , v) es el largo de un paseo de u a v que pasa por vi cuyos nodos internos est
an en
{v1 , . . . , vi }.
: pues `(P ) `(P1 ) + `(P2 ) i1 (u, vi ) + i1 (vi , v).
3.
Algoritmo Floyd-Warshall
A partir de lo que definimos en la secci

on anterior, se presenta a continuacion el algoritmo Floyd-Warshall. Luego
mostraremos la correctitud y la complejidad del mismo.
Algoritmo 1: Algoritmo Floyd-Warshall
INPUT: G = (V, E) digrafo, ` : E R conservativo.
for u V, v
V do
0
si u = v.
0 (u, v) =
+ si u 6= v.
end
for i = 1, . . . , n do
for u V, v V do
i (u, v) = mn{i1 (u, vi ) + i1 (vi , v), i1 (u, v)}.
end
end
return d = n
Correctitud: Es f
acil ver que el algoritmo funciona gracias a la demostracion del lema 1. Es importante observar que
funciona si ` es conservativo.
Complejidad: El segundo ciclo for del algoritmo realiza n iteraciones, mientras que el for anidado debe recorrer dos
veces los nodos de V , con lo cual se tiene una complejidad de O(n3 ).
Que sucede ahora si ` 0? La siguiente seccion responde esta pregunta.
4.
Algoritmo Dijkstra
Dijkstra se aprovecha de los largos mayores o iguales que cero para dise
nar un algoritmo casi-gloton (no podemos
hablar de un algoritmo glot
on propiamente tal ya que Dijkstra involucra programacion dinamica en cada paso). Dikjstra
no funciona con largos negativos, como otros algoritmos de caminos/paseos de costo mnimo en digrafos, por las razones
que ya se han mencionado en los algoritmos anteriores.
La idea de Dijkstra, es que el algoritmos comienza desde un nodo raz s y va eligiendo (y agregando) los nodos que se
encuentren a distancia minima de s en cada paso, manteniendo siempre una arborecencia de caminos mnimos desde la
raz s a los nodos ya agregados. A continuaci
on se encuentra el pseudocodigo del algoritmo, el cual emplea de las funciones
D[v] y [v] para vertices v, las cuales son como se detalla dentro del mismo algoritmo:

aticas
Algoritmo 2: Algoritmo Dijkstra

INPUT: G = (V, E) digrafo, ` : E R+ .
for v V do
0
si v = s.
l(s, v) si (s, v) E.
D[v] =
+ si no.
si v = s.
s si (s, v) E.
[v] =
si no.
end
U = s.
F = .
while U 6= V do
if D[w] = + w V \ U then
U V .
end
Elegir u U \ V con D[u ] mnimo.
U U + u .
F F + ((u ), u ).
for w V \ U, con (u , w) E do
if D[w] > D[u ] + l(u , w) then
D[w] D[u ] + l(u , w).
[w] u .
end
end
end
return H = (U, F )
Teorema 1. Dijkstra mantiene lo siguiente en cada iteraci
on:
(1) H = (U, F ) es una arborecencia con raz en s, tal que para todo nodo u en U , el u
nico camino de s a u en H,
denotado por (sHu) es de largo mnimo en G.
(2) u U, D[u] = l(sHu) = d(s, u).
(3) u V \ U, D[u] = mn{l(P ) : P es s-u dicamino en G tal que V (P ) u U }
de hecho, si w = [u] U (y D[u] < ), entonces: D[u] = l(sHwu)
Observaci
on 2. Dijkstra es glot
on pues agrega de todos los vertices de V \ U a aquel que esta mas cerca. Puesto que
lo que trata de hacer Dijkstra es agregar un vertice fuera de los que ya tiene (en la arborescencia de caminos mnimos)
tal que minimiza la distancia.
Demostraci
on. Inducci
on en i = |U |
i = 1: en este caso el algoritmo avanza s
olo hasta el tercer paso. Luego se mantienen en cada paso:
(1) Como s
olo se ha llegado hasta el paso 3, es trivial que es arborecencia, puesto que solo se habr
an agregado
arcos que salen de s, por lo que o son nodos vecinos de s, por lo que el largo del camino entre estos nodos y s
ser
a el largo de la arista que los une a s, que sera trivialmente mnimo; o es el mismo s, y en ese caso es cero;
o si no es ninguno de los dos casos anteriores, entonces la distancia es infinita.
(2) En U , s
olo habr
a nodos u vecinos a s, y por construccion D[u] = l(sHu) = d(s, u).
(3) Se tiene por (1) y (2).
i 2: sean D0 , 0 los vectores D y y sea H justo antes de que |U | = i:
(1) H = H 0 agregando el nodo u y el arco ((u ), u )(donde (u ) U ), luego H es arborecencia.
3

aticas
(2) Cuando |U| = i 1:

D0 [u] = l(sH 0 u) = d(s, u) u U 0
D0 [u] = D[u] y l(sH 0 u) = l(sHu) D[u] = l(sH 0 u)
Por lo que s
olo debemos revisar u :
0
D[u ] = D [u ] = l(sH 0 wu), donde w = (u) y la igualdad con l(sH 0 wu) se tiene por induccion.
sabemos que:
D[u ] = l(sHu ) (sHu = sH 0 wu )
Si D[u ] 6= dist(s, u ): camino P de s a u tal que l(P ) < D[u ]
si este camino es tal que V (P ) U p(P ) = D[u ]
luego debe existir z
/ U en V (P ).
En la siguente imagen se puede ver un ejemplo de como es lo que se tiene en cada paso de Dijkstra:
Figura 1.
Sea z V \ U el primer nodo P en V \ U :
D0 [z] =largo del camino m
as corto de s a z que pasa solo por nodos de u.
D0 [z] l(sP z) l(P ) < D[u ] = D0 [u ].
Donde l(sP z) es el largo del subcamino P entre s y z que es menor que l(P ) puesto que se consideran largos
positivos, pero esto contradice la eleccion de u .
D[u ] = d(s, u)
(3) Sea u V \ U ,con D[u] el largo mnimo de s a u que usa solo nodos de U . Tenemos de esta froma dos casos:
Si el camino mnimo que usa nodos de U no toca u , entonces se tiene que D[u] = D0 [u].
si no: D[u] = D[[u]] + l([v], u).
Para visualizar c
omo es U , U 0 y u , se puede ilustrar de la siguiente manera:

aticas
Figura 2.
La demostraci
on de los hechos del punto 3 se probaran en la siguiente clase.

aticas

Profesor: Jose Soto
Escriba(s): Pedro Espinoza, Felipe Salas y Pablo Ugalde
Fecha: 22 de Septiembre de 2014.
C
atedra 12
Algorithm 1 Algoritmo Dijkstra
INPUT: G = (V, E) digrafo, ` : E R+
for v V do
0
si v = s.
`(s, v) si (s, v) E.
D[v] =
+ si no.
si v = s.
s si (s, v) E.
[v] =
si no.
end
U = s.
F = .
while U 6= V do
if D[w] = + w V \ U then
U V .
end
Elegir u U \ V con D[u ] mnimo.
U U + u .
F F + ((u ), u ).
for w V \ U, (u , w) E do
if D[w] > D[u ] + `(u , w) then
D[w] D[u ] + `(u , w).
[w] u .
end
end
end
return H = (U, F ).
Notaci
on. Si T es un digrafo que contiene un u
nico a-b dicamino, entonces denotamos a tal dicamino como aT b.
Teorema 1. En cada paso:
(i) H = (U, F ) es una arborecencia con raz en s, tal que para todo nodo v en U , el u
nico camino de s a v H, denotado
por (sHv) es de largo mnimo en G.
(ii) v U, D[v] = `(sHv) = d(s, v).
(iii) v U, D[v] = mn{`(P ) : P es s-v camino en G con V (P ) v U }
(de hecho, si w =[v] U (y D[v] < ), entonces: D[v] = `(sHwv))
Observaci
on. La clase pasada probamos (i) y (ii) por inducci
on en i = |U |.
Probemos (iii), el caso i = 1 es trivial.

aticas
i 2: Sea u el i-esimo nodo que Dijkstra elige

Llamemos U , D, H, a los objetos al final de la iteracion en la
que u es agregado a U , y llamemos U 0 , D0 , H 0 , 0 a los objetos en
la iteraci
on anterior. En particular, U = U 0 + u .
Sea v V \U, consideremos P un s-v camino con V (P ) v U de
largo mnimo.
Observaci
on. De todos los P posibles, elijamos uno donde u
aparece lo m
as tarde posible (o no aparece).
Figura 1: P donde u aparece lo m
as tarde
posible.
Afirmaci
on. Si u est
a en P , entonces u es el pen
ultimo nodo de P .
Demostraci
on. Si no fuera el pen
ultimo nodo de P :
Sea w el sucesor de u en P . Como P es mnimo, sP w es de largo mnimo en G.
Como w U 0 , `(sP w) = d(s, w) = `(sH 0 w) (por (ii)). Concatenando sH 0 w con
wP u, tenemos un paseo Q con V (Q) v U 0 (todos los vertices de Q contenidos en
U 0 ).
Luego Q contiene un s-v camino Q0 con todos sus vertices (excepto v) en U 0 donde
u no aparece, y `(Q0 ) `(P ), es decir, encontramos un s-v camino mas corto, lo
que contradice el hecho de que P es de largo mnimo.
Figura 2: P con w sucesor de u .
Usemos la afirmaci
on para probar (iii):
Demostraci
on. (iii): Cuando u entra a U , D[v] = min{D0 [v], D0 [v] + `(u , v)}.
Si P no toca a u , por inducci
on, `(P ) = D0 [v].
Si P toca a u ; `(P ) = `(sP u ) + `(u , v) = D0 [v] + `(U , v).

Por lo tanto, D[v] = `(P ).
Probamos as que el algoritmo de Dijkstra es correcto, es decir que devuelve las distancias mnimas y los caminos m
as
cortos de s a todos los nodos.
Corolario 1. Dijkstra funciona y encuentra los caminos m
as cortos de s a todos los dem
as nodos.

aticas
Una peque
na intuici
on sobre c
omo funciona Dijkstra en
cada paso:
1. Para todo v V \U , calcular:
D[v] := min = `(sHx) + `(xv).
xU
2. Elegir el mnimo D[v] y agregarlo a H.

Figura 3: Caminos de s a v.
Complejidad
Analicemos la complejidad del algoritmo de Dijkstra.
Inicializacio
n : O(n) pues se calcula el par (D[v], [v]) para cada nodo.
Desde linea 4 a linea 8: Calcular el mnimo toma O(n).
Desde linea 9 a linea 14: Actualizar los valores toma O(|N + (u )|).
P
Por lo tanto, en total la complejidad es
O(n + |N + (u )|) = O(n2 + m).
vV
Es interesante notar que existen otras implementaciones de este mismo algoritmo que permiten mejorar la complejidad.
Definici
on. Llamaremos cola de prioridad a una estructura de datos en la que se pueden realizar las siguientes operaciones:
Agregar un par (etiqueta, valor).
Extraer mnimo.
Cambiar el valor de alguna etiqueta.
Usando estas estructuras se puede reducir considerablemente la complejidad de este algoritmo, algunas implementaciones
que se destacan son mediante Heaps Binarios, con la cual el algoritmo Dijkstra tiene complejidad O(m log n) y mediante
Heaps de Fibonacci que logra una complejidad O(m + n log n).
Observaci
on. En la practica usar Heaps binarios es mucho m
as conveniente que usar Heaps de Fibonacci, debido a su
f
acil implementaci
on y adem
as garantiza O(log n) para todas las operaciones de cola de prioridad.
Observaci
on. Para encontrar caminos mnimos desde s, usando colas de prioridad se tiene que:
Dijkstra es O(m + n log n).
Bellman-Ford es O(n(m + n)).
Observaci
on. Si quisieramos calcular las distancias entre todos los pares, se tiene que:
Dijkstra desde todos los nodos es O(nm + n2 log n).
Floyd-Warshall es O(n3 ).
Observaci
on. Si G no tiene ciclos (dirigidos), Orden topol
ogico (visto en auxiliar) es:
O(n + m) desde alg
un s.
O(n2 + mn) entre todos los pares.
Observaci
on. Dijkstra funciona tambien en grafos no dirigidos con largos positivos. Para aplicar Dijkstra en estos grafos,
basta reemplazar cada arista e = {u, v} E por dos arcos antiparalelos (u, v) y (v, u) y asignarles `(e) a ambos arcos. Para
encontrar caminos mnimos en el grafo original, basta encontrar caminos dirigidos mnimos en el grafo dirigido auxiliar.
3

aticas
Finalmente, es bueno notar que si todos los arcos (o aristas) tienen el mismo largo, digamos igual a 1, entonces podemos
encontrar un
arbol de caminos de costo mnimo a partir de s calculando simplemente un arbol de b
usqueda horizontal
(BFS). Como consecuencia, calcular caminos mnimos con respecto al n
umero de arcos (o aristas), se puede hacer en
tiempo O(n + m), lo cual es incluso m
as r
apido que Dijkstra.
III. Matching
Comenzaremos recordando la definici
on de matching en un grafo no dirigido:
Definici
on. Sea G = (V, E) un grafo no dirigido. Se dice que M E es un matching en G si @ e, f M con e 6= f , tal
que son incidentes en un mismo v V , o equivalentemente e, f M e f = .
Motivaci
on. Un ejemplo en donde se necesita encontrar un matching de cardinalidad maxima es el siguiente.
Consideremos un grafo cuyos vertices son todos los estudiantes y las

universidades, y las postulaciones de un estudiante a una universidad
son sus aristas. El objetivo es encontrar el matching que encuentre la
combinaci
on con m
as postulaciones, dependiendo del cupo de cada
universidad
Notemos que hay muchos problemas similares a este.
En el contexto del problema de matching de cardinalidad maxima surgen dos preguntas: Dado un matching M de un grafo
G,
1. C
omo certificar que M no es de cardinalidad maxima?
2. C
omo certificar que M es de cardinalidad maxima?
En respuesta a la primera pregunta bastara encontrar otro matching mas grande. La respuesta a la segunda pregunta es
en general un problema difcil al cual se le intentara dar una respuesta.
Definici
on. Dado M matching, v V se dice M -cubierto si e M tal que e es incidente en v. En caso contrario v se
dice M -expuesto.
Definici
on. Dado un camino simple P = e1 e2 . . . el , donde ei E, diremos que P es M -alternante en G si: ei M
ei+1
/ M, i {1, . . . , l 1}.
Observaci
on. Se define un ciclo alternante de forma an
aloga.
Definici
on. Se dice que un camino P M -alternante es M -aumentante si los vertices extremos de P estan M -expuestos.
Observaci
on. Si P es M -aumentante, entonces: |P \ M | = |P M | + 1.
Ahora nuestro problema a resolver ser
a el de encontrar un matching de cardinal maximo, para esto nos sera u
til el siguiente
teorema:
Teorema 2. M es maching de cardinal m
aximo @ un camino M -aumentante.
Antes de probar el teorema estudiemos un lema que nos ayudara en la demostracion de este:
Lema 1. Dado M matching. Si P es M -aumentante M 0 = M P es un matching tal que |M 0 | = |M | + 1.
4

aticas
Demostraci
on. Tenemos que |M 0 | = |M | + 1, pues |P \ M | = |P M | + 1. Ademas M 0 es matching, ya que si no lo
fuera, tomando e, f M 0 , e 6= f y ambos incidentes en v, por la alternancia de P tenemos que sin perdida de generalidad
e M \ P f P \ M . Luego, como P es M -aumentante, g M incidente en v, con g 6= e, lo cual es una contradicci
on
con que M sea matching. Por lo tanto M 0 es matching.
Ahora probemos el teorema que enunciamos anteriormente:
Demostraci
on.
Directo del lema pues si existiese un camino M -aumentante, en virtud de lo probado, M 0 es un matching de cardinal
mayor estricto que M .
Por contradicci
on supongamos que M 0 es matching tal que |M 0 | > |M |. Entonces dado N = M 0 M tendremos que
en cada vertice de G inciden a lo m
as dos aristas de N , de esta forma nos damos cuenta de que N es una colecci
on
de caminos o ciclos disjuntos que alternan sus aristas entre M y M 0 . Finalmente tendremos que como |M 0 | > |M |,
entonces existe un camino P en M 0 M tal que |M 0 P | > |M P |. De aqu se deduce que P es M -aumentante,
llegando as a una contradicci
on.

aticas

Profesor: Jose Soto
Escriba(s): Ian Letter, Obed Ulloa e Ian Vidal.
C
atedra 13
1.
Recuerdo C
atedra Anterior
Teorema 1. Un matching M es de tama

no m
aximo en G G no posee caminos M -aumentantes.
Observaci
on 1. No es trivial verificar si un matching posee o no caminos M -aumentantes.
Ejemplo 1. En este caso dada la cantidad de aristas es dificil identificar si un matching es de tama
no m
aximo. Para
facilitar la tarea definiremos lo que es un cubrimiento.
Figura 1. El conjunto {A, F, G, H} es un cubrimiento.

Definici
on 1. Sea G = (V, E) grafo. Sea C V . Diremos que C es cubrimiento (por vertices) si toda arista e E incide
en C (es decir, es incidente a algun vertice de C).
Teorema 2. Sea M matching de G, C cubrimiento de G. Luego |M | |C|.
Demostraci
on. Cada arista de M requiere un vertice distinto de C para ser cubierto (pues las aristas de M son disjuntas).
Cada vertice de C cubre a lo m
as una arista de M |M | |C|.
Observaci
on 2. Esto es u
til para demostrar que un matching no puede ser mas que grande que cierta cota. Se puede
observar que en el ejemplo 1 |C| = 4 |M | 4.
Corolario 1. :
m
ax
M,matching
|M |
mn
C,cubrimiento
|C|.
Observaci
on 3. No es siempre posible obtener la igualdad.
Ejemplo 2.
Figura 2. El cubrimiento mnimo tiene tama
no 2, mientras que el matching maximo tiene tama
no 1.
En este caso se observa que trivialmente |M | = 1, pero se tiene que |C| = 2.

aticas
Observaci
on 4. : Si hay igualdad es posible crear un matching de tama
no maximo. Ahora bien, no es facil verificar si
se puede obtener la igualdad o no. El caso particular en el que nos enfocaremos en lo que sigue es cuando G es un grafo
bipartito.
Definici
on 2. G es bipartito ssi L, R V ; L R = L R = V t.q: e E, e = uw, u L, w R, es decir, toda
arista tiene un extremo en L y otro en R. El grafo G = (V, E) tambien se denotara como G = (L, R; E).Adem
as las aristas
uw E se identificar
an como el par ordenado (u, w) L R.
Observaci
on 5. Lo anterior es equivalente a decir que G no tiene ciclos de largo impar.
Teorema 3. K
onig: Sea G grafo bipartito. Luego:
m
ax
M,matching
|M | =
mn
C,cubrimiento
|C|
Demostraci
on 1. Esta demostraci
on se har
a algoritmicamente. Para ello crearemos una rutina que dado M matching,
encuentre un camino M -aumentante (y as podemos encontrar un matching mayor) o reporte un cubrimiento de C con
|C| = |M |. Notemos que si este procedimiento siempre se puede llevar a cabo, entonces se obtiene el resultado.
Con lo anterior podemos partir de M = y en cada iteracion aumentar el matching con el camino M -aumentante,
luego cuando no se pueda aumentar comprobamos que |M | = |C|.
Luego sea G = (L, R; E). Llamaremos A a los vertices M -expuestos en L y B a los M -expuestos en R. Por simplicidad
del algoritmo, creamos el siguiente digrafo auxiliar D(G, M ).
Figura 3.
O sea, dirigimos la arista e de L a R si e no esta en el matching, y de R a L si lo esta. Ademas, agregamos s un nodo
auxiliar que esta conectado con un arista con todos los nodos en A. Este grafo tiene por nodos {s} V y los arcos de
D(G, M ) son de 3 tipos:
{sv; v A} (Aristas dirigidas de s a los nodos de A)
{vw; v L, w R, vw E/M } (Aristas que no estan en el matching dirigidas de L a R)
{wv; v L, w R, vw M } (Aristas que si estan en el matching dirigidas de R a L)
Necesitaremos el siguiente resultado:
Lema 1. Todo s-w dicamino en D(G, M ) con w B est
a en correspondencia con un camino M -aumentante.
Demostraci
on 2. Esto se har
a por construcci
on. En primer lugar; Como encontramos un s-w dicamino? Para esto
usamos BFS desde s, cuando encuentre w paramos; y as obtenemos el dicamino.
Luego, para encontrar el camino M -aumentante en G utilizaremos el siguente algoritmo:

aticas
Algoritmo 1: Algoritmo para encontrar camino M -aumentante en G

Construir D(G, M )
BFS desde s
T {nodos alvanzables desde s por BFS}
if w T B then
Return Camino M aumentante asociado al s w dicamino.
end
else
Return Cubrimiento C = (L \ T ) (R T )
end
Lo anterior ser
a suficiente para concluir el resultado, ya que el C retornado en la parte anterior, sera el cubrimiento
que buscamos. Para ello demostraremos lo siguiente:
Teorema 4. Si M es m
aximo el conjunto C = (L \ T ) (R T ) es un cubrimiento que cumple |C| = |M |.
Demostraci
on. Hay que ver primero que C es cubrimiento y luego que |M | = |C|.
C es cubrimiento de G: supongamos e = vw E no cubierto por C. s.p.g. v L, w R. Luego v LT w R\T.,
ya que si no e estara cubierto por C.
Figura 4.
Si e no est
a en el matching, entonces por construccion, se dirige de L a R. En ese caso conecta a v, que est
a en
T y por tanto es alcanzable, con w, que no esta en T . As se obtiene una contradiccion ya que conecta a un
alcanzable con un no alcanzable.
Si e est
a en el matching, entonces se dirige de R a L. Con esto sabemos que v no esta en A, pues e M incide
en v (y A corresponde a los M -expuestos de L).
Con esto, adem
as se deduce que deg (v) = 1, pues esta cubierto por el matching (Ya que la u
nica forma de
entrar a v es mediante M ).
Lo u
ltimo implica que C = (L \ T ) (R T ) como v T entonces es alcanzable solo por e. Osea, si v es
alcanzable en alg
un momento se ha pasado por w uno no alcanzable. Contradiccion.
Con eso ya tenemos que C es cubrimiento.
Ahora veamos que |M | = |C|.
Sabemos por K
onig que |M | |C|. Luego solo falta ver que |C| |M |. Para esto contruiremos una inyecci
on de C
a M , sea:
:CM
v 7 ev
3

aticas
donde ev es la nica arista de M incidente a v. Falta ver que esto siempre existe, es decir, que esta bien definido, y
que es inyecci
on.
Para lo primero, (recordar que C = (L \ T ) (R T ) ) sea v L \ T . Si v fuese M -expuesto entonces v A T , lo
que es una contradicci
on. Luego v es M -cubierto.
Luego sea w R T . Si w fuese M -expuesto entonces w B. Pero C fue construido por el algoritmo anterior, y
si w hubiese estado en B este hubiese reportado un camino M -aumentante. Esto es una contradiccion ya que M es
m
aximo. Por lo tanto w es M -cubierto. Luego todo nodo en C es M cubierto, por lo tanto existe una u
nica arista
incidente a el (por ser M -matching). Por lo tanto, la funcion anterior esta bien definida.
Falta ver que es inyecci
on. Supongamos que no; luego v L \ T ; w R T t.q: vw M (Notemos que definimos
que la funcion que entregaba la arista incidente a v. Luego si no existe arista del tipo anterior y por ser M matching
la funcion ser
a inyectiva). Por construcci
on del digrafo entonces e va de w a v. Lo que es una contradicci
on, pues
w T y v T c . Es decir, v no es alcanzable y el u
nico arco que entra a v viene desde un vertice alcanzable. Con
esto, se tiene que la funci
on es una inyecci
on.
Sintetizando, el algoritmo para encontrar M de tama

no maximo es:
Algoritmo 2: Algoritmo para encontrar M de tama
no maximo
M
while True do
Usar la rutina anterior
if camino M -aumentante then
Aumentar M con el camino
end
else
Return M y C
end
end
Teorema 5. El algoritmo anterior es correcto y resuelve el problema de atching m
aximo M y cubrimiento mnimo C
en O(n(m + n)).
Demostraci
on. La demostraci
on de por que es correcta se deduce del teorema 4. Para el orden, notemos lo siguiente; el
While se hace a lo mas |M | veces. Donde M es el matching de tama
no maximo. por otro lado,dentro de cada iteraci
on la
rutina demora O(n + m) (Para ello notar que es hecha en base a BFS). Notando que |M | n se concluye el resultado.
Observaci
on 6. El mejor algoritmo para el problema anterior es el de Hopcroft-Kar, que es O(m n). A grandes rasgos,
este funciona encontrado en cada paso una coleccion de caminos M -aumentante disjuntos.
Ejemplo 3. Veremos una aplicaci
on de problema de cubrimiento mnimo. En un museo, cual es la menor cantidad de
guardias,que debemos ubicar en las esquinas, para cuidar cada pasillo?.
Figura 5.
4

aticas
Es claro que la soluci

on para esto es la de cubrimiento mnimo.
Corolario 2. Teorema de K
onig es cierto.
Esto se deduce de la construcci
on ya hecha. El siguiente resultado es interesante.
Corolario 3. Teorema del matrimonio de Hall.
Sea G un grafo bipartito, con bipartici
on L y R. Entonces M matching que cubre a todo L (es decir, cubre todos los
vertices de L ) A L; |N (A)| |A|, y al ser bipartito el Matching es m
aximo.
Ejemplo 4. Una aplicaci
on curiosa es la siguiente:
Sea M una Matriz con coeficientes en {0, 1}. Definimos transversal como un conjunto de 1 t.q. no hay dos en la misma
fila o columna. Luego existe una transversal que toca a todas las filas de M A f ilas(M ) la cantidad de 1 de
A |A|.
Demostraci
on. (De Hall) Primero, la implicancia hacia la derecha. A cada v A asociamos Mv el u
nico vertice emperajado
por M en N (A). Luego |N (A)| |A|, ya que construimos una inyeccion de A a N (A).
Ahora la implicancia hacia la izquierda. Sea G un grafo t.q |N (A)| |A|A L. Sea C un cubrimiento mnimo; luego
C toca algunos nodos de la bipartici
on izquierda y otros de la derecha. Por Konig
|M | = |C| = |C L| + |C R| |C L| + |N (L \ C)|
.
En lo anterior hemos usado adem
as que toda arista de L/C llega C R, pues C es cubrimiento. Finalmente, por la
hip
otesis
|C L| + |N (L/C)| |C L| + |L/C| = |L|
.
As concluimos que el matching cubre todo L y tenemos asi lo deseado.

aticas

Profesor: Jose Soto
andez y Emilien Garcia.
C
atedra 14
1.
Emparejamiento con Peso Mnimo en Grafos Bipartitos
En las clases anteriores estudiamos problemas de emparejamientos (o matchings). Vimos algunos resultados muy
importantes para resolverlos, en particular vimos condiciones para encontrar un matching M de cardinalidad m
axima
(usando caminos M-aumentantes o cubrimientos), y tambien vimos resultados mas fuertes que se tienen en el caso de un
grafo bipartito (entre ellos el teorema de K
onig). Recordemos algunos de estos resultados antes de desarrollar el tema de
los emparejamientos con peso mnimo en grafos bipartitos.
En los recordatorios que siguen, denotaremos por G = (V, E) un grafo.
Recordatorio 1 (Matching). M E es un matching ssi e, f M, e f = .
Recordatorio 2 (Cubrimiento). C V es un cubrimiento (por vertices) ssi toda arista de E es incidente a alg
un vertice
de C.
Recordatorio 3 (Grafo Bipartito). G es un grafo bipartito ssi L, R con L R = , L R = V tales que toda arista de
E tiene un extremo en L y uno en R.
Recordatorio 4 (Teorema de K
onig). Si G es un grafo bipartito, entonces m
ax {|M | : M matching} = mn {|C| : C cubrimiento}.
Recordatorio 5 (Teorema). Si M es un matching maximo, entonces C = (L \ T ) (R T ) es un cubrimiento con
|C| = |M |, donde T es el conjunto de nodos alcanzables desde el vertice s del digrafo auxiliar D(G, M ).
Definici
on 1 (Matching Perfecto). Un matching M se dice perfecto ssi todo vertice del grafo esta cubierto por una arista
del matching.
Ahora que terminamos con los recordatorios u
tiles para lo que sigue, plantearemos tres tipos de problemas de emparejamiento con peso mnimo en un grafo bipartito. De ahora en adelante consideraremos el grafo bipartito G = (L, R; E),
sobre el cual resolveremos los siguientes problemas:
1. Dada una funci
on de peso w : E R encontrar M matching de peso maximo.
2. Dada una funci
on de peso w : E R y un k N encontrar M matching de peso maximo sujeto a |M | = k
3. Problema de asignaci
on. Sea c : E R y G un grafo bipartito completo simetrico, es decir:
|L| = |R| y E = {ij : (i, j) L R}.
Dado todo esto, encontrar una asignaci
on : L R biyectiva de costo mnimo, o equivalentemente, un matching
M perfecto de costo mnimo.
Observaci
on 1. En realidad, el tercer problema permite resolver tambien los dos anteriores. No demostraremos que el
problema 3 resuelve el problema 1, esto queda como problema propuesto (mas a
un controlable). Sin embargo, probemos
ahora que el problema 3 resuelve el problema 2, demostracion mas sencilla que la anterior :
Dem. Procedamos por etapas. Supongamos, para dar sentido a la demostracion, que existe matching de tama
no k. Luego
|L|, |R| k. A continuaci
on:
1. Creemos el conjunto de vertices L0 , a
nadiendo al conjunto L, |R| k vertices fantasmas.
2. Creemos el conjunto de vertices R0 , a
nadiendo al conjunto R, |L| k vertices fantasmas.
3. Ahora que L0 y R0 tienen igual n
umero de vertices, creemos el conjunto de aristas E 0 = L0 R0 .
1

aticas
4. Definamos nuestra funci

on de costo c a partir de la funcion de peso w del problema 2, eligiendo un n
umero N N
muy grande (mayor que el m
aximo de |w|) :
si e (L (R0 \ R)) ((L0 \ L) R)
w(e) si
eE
c(e) =
+N
si
e (L0 \ L) (R0 \ R)
De esta manera queda definido un grafo bipartito completo simetrico y una funcion de peso cuyo mnimo se alcanza
s
olo cuando se ocupan k aristas de L a R. Luego, solucionando este problema de asignacion se obtiene una soluci
on del
problema 2 original.
Figura 1: Dibujo que ilustra el desarrollo anterior.

aticas
2.
Problema de Asignaci
on
En esta secci
on resolveremos el problema de asignacion enunciado en lo anterior. Sea G = (L, R; E) un grafo bipartito
completo y c : E R una funci
on de costo. Modelemos el problema y reduzcamoslo a un problema de optimizaci
on lineal.
Buscamos M matching perfecto de peso mnimo, esto se puede reescribir de la siguiente manera:
X
X
mn c(M ) =
mn
c(e) =
mn
c(e)1M (e).
M perf ecto
M perf ecto
M perf ecto
eM
eE
Si definimos ce = c(e) y xe = 1M (e) nos queda:

mn
M perf ecto
c(e) =
mn
M perf ecto
ce x e .
eE
La condici
on M matching perfecto es equivalente a que para todo vertice v, existe un u
nico e que contenga a v tal que
xe = 1. Es decir:
X
X
i L,
xij = 1 y j R,
xij = 1.
jR
iL
Luego el problema se puede modelar por el siguiente Programa Lineal Entero:

X
X
X
(P LE) : mn
ce xe sujeto a xe {0, 1}; i L
xij = 1 y j R
xij = 1
eE
jR
iL
Relajemos este Programa Lineal Entero a un Programa Lineal, permitiendo xe [0, 1]. Como ya se tiene la restricci
on
que la suma sea igual a uno, la segunda cota es innecesaria, luego en el programa lineal se tiene simplemente que xe 0.
Adem
as como el grafo es bipartito completo, podemos escribir E = {ij : (i, j) L R}. Luego el problema queda reescrito
como:
X
X
X
(P L) : mn
cij xij sujeto a xij 0 i L
xij = 1 y j R
xij = 1
iL, jR
Tomemos el Dual de (PL). Sea yi =
jR
(D) : m
ax
xij y zj = iL xij . Luego el Dual de (PL) es:

X
yi +
zj sujeto a cij yi + zj . yi y zj son libres
jR
iL
iL
jR
Recordatorio 6. Dualidad D
ebil Toda soluci
on factible del problema Primal tiene un valor mayor que toda soluci
on
factible del Dual. En este caso se tiene:
X
X
X
cij xij (
yi ) + (
zj )
iL, jR
iL
jR
Dem.
X
XX
XX
XX
XX
X X
X X
cij xij =
cij xij
(yi +zj )xij = (
yi xij ) + (
zj xij ) = (
yi
xij ) + (
zj
xij )
iL,jR
Como i L
iL jR
jR
iL jR
xij = 1 y j R
iL jR
iL jR
xij = 1 se concluye que:

X
X
X
cij xij (
yi ) + (
zj )
iL
iL, jR
iL
jR
iL
jR
jR
iL

aticas
Dise
naremos entonces un algoritmo PRIMAL-DUAL que haga lo siguiente :
PRIMAL-DUAL
1. Elegir/encontrar una soluci
on dual factible (y, z).
2. Usar (y, z) para encontrar un M de igual valor :
Si se encuentra, estamos listos.
Si no, usar la informaci
on que tenemos para mejorar (y, z).
Observaci
on 2. Sea (y, z) dual factible, si (y , z ) fuera optimo, entonces existira x primal de mismo valor, y por
Holgura Complementaria :
Si cij > yi + zj , entonces xij = 0 ; Si xij > 0, entonces cij = yi + zj
Definamos (i, j) E, wij = cij yi zj .
Busquemos un matching que use s
olo las aristas en E0 = {(i, j) E | wij = 0}.
Si llegaramos a encontrar un matching perfecto M en E0 , tendramos :
X
X
X
X
valor(M ) =
cij =
(yi + zj ) =
yi +
zj = valor(y, z)
(i,j)M
(i,j)M
iL
jR
En efecto, las sumatorias se separan en dos sumas, una sobre L y una sobre R (pues M es perfecto), por lo que sus
aristas pasan por todos los vertices de V , en particular todos los de L y R. Por lo tanto, con esta igualdad, tendramos
que M es
optimo para nuestro problema.
Sin embargo, es posible que E0 no contenga matching perfecto. En este caso, busquemos M 0 matching de tama
no
m
aximo en E0 . Por el teorema de K
onig, sabemos que existe C cubrimiento de (V, E0 ) con |C| = |M 0 |. Como vimos la
clase pasada, C se podra encontrar como C = (L \ T ) (R T ), donde T es el conjunto de los alcanzables en D = (G, M 0 )
desde s, el vertice ficticio a
nadido al grafo. Queremos usar C para identificar vertices donde alterar (y, z) de modo que el
valor total aumente.
C cubrimiento de E0 (L T ) (R \ T ) E \ E0 : no pueden existir aristas entre L T y R \ T en E0 . Para
ij = e (L T ) (R \ T ), wij > 0, luego cij > yi + zj .
Figura 2: A la izquierda figura una representaci

on del digrafo asociado a E0 , con el vertice s a
nadido y las aristas que
se pueden encontrar o no desde s. A la derecha aparece una ilustracion de las distintas orientaciones para las aristas
encontrables en el digrafo construido con E0 .
Definamos = mn {wij : (i, j) (L T ) (R \ T )}. Sean tambien (y 0 , z 0 ) tales que :
yi + si i L T
zj si j R T
zj0 =
yi0 =
yi
si i L \ T
yi
si j R \ T
4

aticas
Veamos que (y 0 , z 0 ) es dual factible. Sea (i, j) arista de E :

Si i L T y j R \ T , por elecci
on de tenemos que : yi0 + zj0 = yi + zj + cij
Si i L \ T y j R \ T , obtenemos : yi0 + zj0 = yi + zj cij
Si i L y j R T , tenemos que : yi0 + zj0 yi + zj cij
P
P
P
P
Luego (y 0 , z 0 ) es dual factible ; adem
as, valor(y 0 , z 0 ) = iL yi0 + jR zj0 y valor(y, z) = iL yi + jR zj , por lo tanto:
valor(y 0 , z 0 ) valor(y, z) =
X
X
(yi0 yi ) +
(zj0 zj )
iL
jR
= .|L T | .|R T |
= .(|L| |L \ T | |R T |)
= .(|L| |C|) > 0
En efecto, tenemos L = (L \ T ) (L T ), C = (L \ T ) (R T ) y |L| |C| 1. Si esto u
ltimo no se tuviera, C
sera un cubrimiento total, luego M 0 sera un matching perfecto de E0 , lo que contradice nuestra hipotesis en esta parte
(E0 no contiene matching perfecto).
(y 0 , z 0 ) es una solucion del dual mejor que (y, z).

aticas
3.
Algoritmo H
ungaro Primal-Dual
El algoritmo que deducimos de la secci
on anterior es el siguiente:
Algoritmo 1 Algoritmo H
ungaro Primal-Dual
1: Encontrar Soluci
on Inicial Del Problema Dual:
2: yi 0, i L.
3: zj mn{cij : i L}, j R.
4: wij cij yi zj , i L, j R.
5: E0 {ij E : wij = 0}.
6: M 0 matching de tama
no m
aximo en (V, E0 ).
7: while (M 0 no es matching perfecto en E0 ) do
8:
Crear grafo dirigido D((V, E0 ), M 0 ).
9:
T vertices alcanzables desde s en D((V, E0 ), M 0 ).
10:
mn{wij : i L T, j R \ T }.
11:
yi yi + , i L T.
12:
zj zj , j R T.
13:
wij cij yi zj , i L, j R.
14:
Eo {ij E : wij = 0}.
15:
M 0 matching m
aximo en (V, E0 ).
16: end while
17: return M 0 , y, z.
Teorema 1. El Algoritmo H
ungaro Primal-Dual, si es que termina, devuelve un emparejamiento (matching) perfecto
M 0 de costo mnimo y devuelve un par (y, z) soluci
on dual de mismo valor que el emparejamiento.
Dem. En verdad, la demostraci
on de este teorema la completaremos en la proxima clase. Ya vimos en la secci
on anterior el tema de la correctitud, pero todava no sabemos si el algoritmo termina. Lo veremos mostrando que el algoritmo
es polinomial y tiene complejidad O(n4 ).
En la pr
oxima clase, seguiremos demostrando este teorema y otros mas. Veremos tambien la relacion entre nuestro
tema y la intersecci
on de dos matroides.

aticas

Profesor: Jose Soto
Escriba(s): Benjamn Ruiz
Fecha: 3 de Octubre del 2014 .
C
atedra 15
Habamos visto:
1.
Algortimo H
ungaro Primal-Dual
Recordemos que el algoritmo h

ungaro primal-dual recibe como entrada una matriz de costos cij y devuelve un matching
perfecto M de costo mnimo junto con el par (u, v) dual optimo. Veamos su seudocodigo:
Algoritmo 1 Algoritmo H
ungaro Primal-Dual
1: # Soluci
on Inicial:
2: yi 0, i L.
3: zj mn{cij : i L}, j R.
4: wij cij yi zj , (i, j) L R
5: Eo {ij E : wij = 0}.
6: M matching m
aximo en E0 .
7: while (M no es matching perfecto en E0 ) do
8:
Crear D((V, E0 ), M ).
9:
T vertices alcanzables desde s en D((V, Eo ), M ).
10:
mn{wij : i L T, j R \ T }.
11:
yi yi + , i L T.
12:
zj zj , j R T.
13:
# Actualizar E0 y M :
14:
Eo {ij E : wij = 0}.
15:
M matching m
aximo en E0 .
16: end while
17: return M, y, z.
Es importante recordar que el algoritmo recien enunciado encuentra un matching perfecto de costo mnimo en el grafo
E) con E = A B, |A| = |B| = n y Cij R. Ademas se basa es la siguiente igualdad entre los
bipartito G = (AB,
valores
optimos de los problemas primal y dual:
mn
xij cij
m
ax
iL,jR
yi +
iL
s.a
X
xij = 1 j R
zj
jR
s.a
yi + zj cij
xij = 1 i L
x0
Vimos que el algoritmo, de terminar, es correcto. Mas a

un veremos que termina en tiempo polinomial. Para probar
esto, veremos que el algoritmo es polinomial y tiene complejidad O(n4 ).
Recordemos la siguiente observaci
on:

aticas
Sea M, E0 , w al comienzo de una iteraci

on y T el conjunto de nodos alcanzables desde s en D = D((V, E0 ), M )
Similarmente, sea y M 0 , E00 , w0 , T 0 al final de una iteracion (y D0 = D((V, E00 ), M 0 )). Sea E = (LT RT )(L\T R\T )
el conjunto de aristas de E que conectan vertices con el mismo estado (alcanzable con alcanzable / no alcanzable con no
alcanzable).
Entonces:
1. Como C = (L \ T ) (R T ) es un cubrimiento de (V, E0 ) tenemos que E0 es disjunto de L T R \ T .
2. Como cada arista de M es incidente a exactamente un vertice de C, tenemos que M E .
3. Las aristas en E satisfacen que w0 (e) = w(e).
Concluimos que las aristas de E0 E siguen estando en E00 al final de la iteracion. Luego tenemos que:
Lema 1. El tama
no del matching maximo M solo aumenta de iteraci
on en iteraci
on.
Diremos que una iteraci
on del algoritmo H
ungaro Primal-Dual es exitosa si el tama
no de M aumenta en dicha iteraci
on.
En particular pueden haber a lo m
as n iteraciones exitosas.
Lema 2. Entre cada par de iteraciones exitosas consecutivas hay a lo m
as n iteraciones.
Demostraci
on. En una iteraci
on no exitosa el tama
no de M no aumenta, luego M es un matching de tama
no m
aximo en
E00 tambien. Sin perdida de generalidad suponemos que M 0 = M . De las observaciones anteriores sabemos que las aristas
en E0 E siguen estando en E00 . Por lo tanto, todos los arcos entre nodos alcanzables en D siguen estando presentes en
D0 . Esto quiere decir que todos los nodos que eran alcanzables en D, siguen siendo alcanzables en D0 .
Adem
as, en cada iteraci
on, agregamos un nodo al conjunto de los alcanzables: el arco ij L T R \ T que tiene
w(ij) = es tal que despues de la actualizaci
on, w0 (ij) = 0. Es decir, ij E00 \ E0 . Notar que j no es alcanzable en D.
Sin embargo, como i era alcanzable en D (y luego en D0 tambien), ahora tenemos que j es alcanzable en D0 .
Hemos probado que |T | crece en iteraciones no exitosas. Luego pueden haber a lo mas n iteraciones no exitosas
consecutivas.
Corolario 1. El algoritmo tiene O(n2 ) iteraciones.
En particular
Teorema 1. El algoritmo H
ungaro primal dual calcula una asignaci
on (matching perfecto) de costo mnimo en tiempo
O(n4 ) y una soluci
on dual (y, z) de igual valor.
Observaci
on 1. La complejidad se puede mejorar a O(n3 log n) usando colas de prioridad.
Veamos algunas consecuencias.
Teorema 2 (K
onig-Egerv
ary). Si los costos cij son enteros, entonces el problema dual admite una soluci
on (y, z) con
coordenadas enteras.
Demostraci
on. Directo de como se actualiza la solucion en el algoritmo.
Teorema 3 (Birkhoff-Von Neumann). Sea G un grafo bipartito completo y balanceado (|L| = |R|, E = L R). Y para
cualquier matching perfecto M , sea M su vector indicatriz (M RE , M
e = 1{eM } ).
Tenemos que
P = {x RE : x((v)) = 1, v; x 0}
es igual a
Pmatching perfecto (G) = conv{M : M matching perfecto de G}.
Demostraci
on. Notemos que Pmatching perfecto (G) (pues P es convexo y los vertices de Pmp. de G estan en P ). Para ver la
otra inclusi
on notemos que para cualquier funci
on de costo c RE la expresion mn{cT x : x P } se minimiza en un
punto con coordenadas enteras (seg
un el algoritmo h
ungaro primal dual). De aqu se deduce que todo punto extremo de
P es integral, y luego est
a en Pmatching perfecto (G).

aticas
El teorema anterior dice en particular que si x P entonces existen matchings M1 , . . . , Mk y coeficientes 1 , . . . , k

k
X
[0, 1] con
i = 1 tal que
i=1
x=
k
X
i Mi
i=1
En otras palabras, todo matching perfecto fraccional es combinacion convexa de matchings integrales
Observaci
on 2. Sea A [0, 1]nn , matriz doblemente estocastica o sea que (i, j [n])
n
X
k=1
Ak,j =
n
X
Ai,k = 1, es decir
k=1
que la suma por filas y columnas es 1.

El resultado anterior en su versi
on matricial nos dice que existen matchings perfectos Mi y coneficientes i [0, 1],
n
X
Pn
con
= 1 tal que A = i=1 i Mi .
i=1
Teorema 4 (Poltopos de matchings en grafos bipartitos). Sea G = (L, R; E) un grafo bipartito cualquiera (no necesariamente completo ni balanceado).
1.
Pmatching perfecto (G) = conv{M : M matching perfecto de G} = {x RE : x((v)) = 1, v; x 0}
2.
Pmatching (G) = conv{M : M matching de G} = {x RE : x((v)) 1, v; x 0}
Demostraci
on. Llamemos P1 al poltopo que aparece al lado derecho del primer punto. Veamos que los vertices deP1 son
indicatrices de matchings perfectos. Sea x un punto extremo de P1 y supongamos que x no es integral. Consideremos
entonces F = {e E : xe (0, 1)}. Para todo v G, dF (v) 6= 1 (puede ser 0, 2 o mas) pues x ((v)) = 1. Por lo tanto
(V, F ) no tiene vertices de grado 1 (y F 6= ), luego existe ciclo C F . Como G es bipartito, C es par. Llamemos C + a
las aristas pares y C a las impares.
C+
C+
C ) donde es suficientemente peque
no ( = mn{mn{xe , 1
C ) y x
Tomando x+
e = x (
e = x +(
)
lo
que
es
una
contradicci
on con la
+
x
xe } : e C}), tenemos que ambos puntos pertenecen a P1 . Ademas x = 21 (x+
e
e
definici
on de punto extremo. Concluimos as que P1 esta incluido en Pmatching perfecto (G). La otra inclusion es directa del
hecho que los vectores indicatrices matchings perfectos de G satisfacen las condiciones de P1 .
La parte 2 queda de ejercicio como controlable.
En particular, se concluye que si existe un matching fraccional (elemento de {x RE : x((v)) 1, v; x 0}) con
cT x a entonces debe existir un matching entero con cT x a.

aticas

Profesor: Jose Soto
Escriba(s): Enzo Aljovin, Felipe Arbul
u y David Hasson.
Fecha: 06 de Octubre 2014.
C
atedra 16
1.
Intersecci
on de Matroides
Definici
on 1 (Intersecci
on de Matroides). Sean M1 = (S, I1 ), M2 = (S, I2 ) con igual conjunto de referencia S. Decimos
que I S est
a en la intersecci
on de M1 y M2 , si I I1 I2 .
A continuaci
on se presentan ejemplos:
1. Matchings en grafos bipartitos
Sea G = (L, R; E) (recordamos que L, R corresponden a la particion de la definicion de bipartito). Definimos el
.
conjunto de referencia S = E y
.
I1 = {F E | |F (v)| 1 v L},
.
I2 = {F E | |F (v)| 1 v R}.
Notemos que los conjuntos independientes anteriores definen matroides de particion. En efecto,
[
[
E = (v) y E = (v).
vL
vR
2. Branchings (r - branchings)
Sea G = (V, E) un digrafo. Un branching es un subconjunto F E donde todo v tiene a lo mas un padre y puede
tener varios hijos. Adem
as entre cada par de nodos hay a lo mas un camino (en cualquier direccion). Llamamos
r-branching a aquellos branchings donde r V no tiene padre.
Figura 1: Ejemplo de branching.

Proposici
on 1 (Caracterizaci
on branchings). F es un branching F I1 I2
I1
I2
= {F E | F (sin considerar direcci

on) es un bosque}
= {F E | |F (v)| 1 v V r , |F (r)| 0}
Demostraci
on.
Solo S
debemos ver que ambos conjuntos definen matroides. En efecto, I1 define una matroide grafica y, usando que
E = vV (v), I2 induce una matroide de particion.

aticas
3. Problema
Sea G = (V, E) grafo donde cada arista e E tiene un color c(e). Determinar si existe un arbol generador multicolor
(es decir, todas las aristas tienen distinto color).
Una soluci
on de este problema es un conjunto F , donde:
F es una base de M(G) (matroide gr
afica), es decir, F I(M(G)), |F | = n 1

F I2 con I2 = F E F c1 (k) 1 color k .
Observaci
on 1. Notamos que I2 corresponde a una matroide de partici
on y, adem
as, c1 (k) corresponde al conjunto
de aristas que son llevadas al color k.
4. Orientaciones
Sea G = (V, E) grafo y sea k : V N. Una orientacion de G que respeta los grados de entrada, k, es un digrafo
D = (V, A) cuyo grafo subyacente es G y tal que d
A (v) k(v) v V.
0
Figura 2: Ejemplo de orientacion que respeta los grados de entrada.
M1 = (S, I1 ) donde
uvE
I1
{(u, v), (v, u)}
= {F S | |F {(u, v), (v, u)}| 1
M2 = (S, I2 ) donde
uv E}

I2 = F S F S (v) k(v)
Luego, el problema anterior se reduce a encontrar F I1 I2 , con |F | = |E|

Observaci
on 2. Las orientaciones son bases de la matroide M1 , es decir, son los F I1 tales que |F | = |E|.
Adem
as, nuevamente las clases de conjuntos independientes definidas forman matroides de partici
on.
Muchos problemas en optimizaci

on combinatorial se reducen a:
(1) Encontrar un conjunto independiente com
un a dos matroides de tama
no/peso maximo.
(2) Encontrar un conjunto independiente com
un de tama
no fijo y de peso maximo.
Nos enfocaremos en el problema (1) en su versi
on cardinalidad.
Teorema 1. (de Intersecci
on de Matroides) Sean M1 = (S, I1 ), M2 = (S, I2 ) dos matroides sobre S.
m
ax |I| = mn (r1 (X) + r2 (S \ X))
II1 I2
XS
M
as a
un, se puede encontrar el
optimo I , X en tiempo polinomial.
2

aticas
Antes de proceder con la demostraci

on del teorema, veamos algunas de sus consecuencias.
Corolario 1. Veamos que se obtiene como consecuencia el teorema de K
onig. En efecto:
Demostraci
on.
Los matchings son los conjuntos independientes en las matroides de particion.
I1
I2
=
=
{F S | |F (v)| 1
{F S | |F (v)| 1
v L}
v R}
Aplicando el lado izquierdo del teorema de interseccion de matroides en su homologo del teorema de Konig, se obtiene
justamente un matching de tama
no m
aximo M .
Sea X E. Sean XL un conjunto de vertices de L que cubre a X, con |XL | = r1 (X) y XR un conjunto de vertices de R
que cubre a X, con |XR | = r2 (S \ X). Luego, XL XR es un cubrimiento de tama
no r1 (X) + r2 (S \ X). El teorema de
intersecci
on de matroides dice que X S con |M | = r1 (X) + r2 (S \ X) = |XL XR |.
X
Figura 3: Ejemplo en que el subconjunto X corresponde a las aristas
negras.
Corolario 2 (Arboles
Multicolor). Sean G = (V, E), c : E R. Definimos
I1
I2
= {F
es bosque}
E | F
=
F E F c1 (k) 1

k color
Existe
arbol multicolor si y s
olo si F I1 I2 con |F | = |V | 1.
Demostraci
on. Es directo.
Corolario 3. Existe
arbol multicolor si y s
olo si para todo conjunto de colores C, el n
umero de componentes conexas que
quedan al borrar Ec no es m
as que |C| + 1.
Demostraci
on.
Para C conjunto de colores, llamemos EC a las aristas de color C (por ejemplo, E{1,2} es el conjunto de las aristas de
color 1
o 2). Tenemos lo siguiente:

aticas
|V | 1
max |F |
F I1 I2
mn
XE
r2 (X)
| {z }
+r1 (E \ X)
#colores en X
Notar que para todo X E:

r2 (X) = r2 (span2 (X))
r1 (E \ X) r1 (E \ span2 (X)),
donde la segunda lnea viene del hecho que X span2 (X). Por otro lado es facil ver que span2 (X) = Ec(X) , donde
c(X) = {c(e) : e X}. La observaci
on anterior nos dice que:
mn r2 (X) + r1 (E \ X) =
XE
mn
XE,Xcerrado para M2
r2 (X) + r1 (E \ X)
= mn r2 (EC ) + r1 (E \ EC )
Cc(E)
= mn |C| + |V | cc(E \ EC ).
Cc(E)
Por el teorema de intersecci

on de matroides sabemos entonces que existe arbol multicolor si y solo si para todo C,
|C| + |V | cc(E \ EC ) |V | 1 Es decir, ssi |C| + 1 cc(E \ EC ).
C se tiene que |V | 1 |C| + |V | cc(E \ C), vale decir cc(E \ C) |C| + 1.
El algoritmo para demostrar el teorema de interseccion de matroides sera inspirado en el de caminos M -aumentantes.
Dise
naremos un algoritmo que dado I I1 I2 , encuentre o bien
un conjunto P tal que IP I1 I2 y |IP | = |I| + 1. O bien,
un X S tal que r1 (X) + r2 (S \ X) = |I|
Veamos primero que I I1 I2 , X S
= |I X| +|I (S \ X)|
| {z }
|I|
I1
r1 (X) + r2 (S \ X),
pues |I X| = r1 (I X) r1 (X).
Este tipo de dualidad debil aparece en muchos problemas. Por ejemplo:
m
ax |I| mn r1 (X) + r2 (S \ X)
II1 I2
max
M Matching
XS
|M |
mn |C|
C Cover
mn b y
max ct x
xP
yD

aticas
Construcci
on Auxiliar
Grafo de intercambios de una matroide. Sea M = (S, I) matroide y sea I I.
Definici
on 2 (Grafo de intercambios). Se define G(M, I) un grafo bipartito tal que e = xy E I + y x I.
e
x
S\I
Figura 4: Construccion del grafo bipartito auxiliar.

Observaci
on 3. xy E y
/ span(I) el u
nico circuito en I + y contiene a x
Lema 1. Sean I, J I tal que |I| = |J| = existe un matching perfecto entre I \ J y J \ I en G(I, S, I)
I \J
J \I
I J
S\I
Figura 5: Ilustracion del resultado.

Demostraci
on. Sea H el subgrafo inducido por I \ J J \ I. Supongamos por contradiccion que H no tiene matching
perfecto, entonces por el teorema de Hall, se tiene que K J \ I : |NH K| < |K|.
Notar que dado I, J I, se tiene que:
(I J) NH (K) I
(I J) K I
|(I J) NH (K)| < |(I J) K|
5

aticas
I \J
K
NH (K) (I \ J)
J \I
I J
I
S\I
Figura 6: Aplicaci
on de aumento en la matroide correspondiente.
Luego, por aumento e K tal que (I J) NH (K) + e I.
Observaci
on 4. La demostraci
on continuar
a en la c
atedra siguiente.

aticas
Profesor: Jose Soto
Escriba(s): Juan Marshall, Martn Ros
Fecha: 10 de Octubre de 2014.
C
atedra 17
1.
Teorema de intersecci
on de matroides
Se haba empezado a trabajar en la demostracion del teorema de interseccion de matroides:
Teorema 1. Intersecci
on de matroides. Sean M1 y M2 dos matroides sobre el conjunto S. Entonces:
m
ax |I| = mn r1 (X) + r2 (S \ X)
II1 I2
XS
(1)
Adem
as se puede encontrar X e I en tiempo polinomial
La clase anterior se demostr
o la desigualdad 6 y se dijo que se demostrara > de forma algortmica usando como
inspiraci
on el algoritmo para encontrar caminos M-aumentantes. Para ello, se haba definido M = (S, I) matroide I I
y se haba creado el grafo de intercambio G(M, I) en donde xy E I + y x I. Por u
ltimo se haba enunciado el
siguiente lema que se terminar
a de demostrar a continuacion :
Lema 1. Si I , J I con |J| = |I| entonces, existe un matching perfecto en G(M, I) entre I \ J y J \ I , i.e , existe
matching perfecto en el subgrafo inducido por estos dos conjuntos.
Demostraci
on. Sea H el subgrafo inducido por I \ J y J \ I. Se razonara por contradiccion: Si no existiera matching
perfecto en H, por el teorema de Hall, W J \ I tal que |NH (W )| < |W |.
Se observa que: (I J) NH (W ) I pues NH (W ) I y ademas, como W J entonces, (I J) W I. Por
axioma de aumento, e ((I J) W I) \ (I J) NH (W )) tal que (I J) NH (W ) + e I.
Se nota lo siguiente : |I \ J| = |J \ I| y que |NH (W )| < |W | por lo tanto, |(I \ J) \ NH (W )| > |(J \ I) \ W |. De lo
anterior se deduce que existe un elemento f en (I \ J) \ NH (W ). Como f
/ NH (W ), se tiene que ef
/ E(G), es decir,
I +ef
/I
De lo anterior, se deduce que I + e
/ I; luego I + e tiene un circuito. Sea C dicho circuito. Este u
ltimo no puede
estar contenido completamente en ((I J) NH (W )) + e), pues dicho conjunto es independiente. Luego, C contiene un
elemento g en (I + e) \ ((I J) NH + e) = I \ J \ NH (W ). Se concluye que I + e g I, de lo que se deduce que
ge E(G). Esto es una contradicci
on, pues g
/ NH (W ).
Corolario 1. Axioma de Intercambio de Bases. Si I, J son bases de S con M = (S, I) matroide, entonces : I J
biyectiva tal que I + (x) x es base de S.
Demostraci
on. Directa del Lema 1.
A continuaci
on se construir
a el algoritmo que permitira demostrar el Teorema de Interseccion de Matroides:
Definici
on 1 (Digrafo de intercambio entre dos matroides). Sean M1 = (S, I1 ), M2 = (S, I2 ) dos matroides. Se define el
digrafo de intercambio asociado como D = D(M1 , M2 , I) , I I1 I2 como
xy E(D) I + y x I1
0 0
0
0
y x E(D) I + y x I2

aticas
S\I
Figura 1: Diagrama digrafo de intercambio entre dos matroides

Obs 1. D es la superposici
on de G(M1 , I) orientado hacia la derecha y G(M2 , I) orientado hacia la izquierda.
Algoritmo 1:
Sea I I1 I2
Construir D = (M1 , M2 , I)
X1 {y S \ I : I + y I1 }
X2 {y S \ I : I + y I2 }
while X1 -X2 camino en D do
Sea P el camino m
as corto de X1 a X2 .
I I 4 V (P ). (Este conjunto pertenece a I1 I2 y tiene un elemento mas que I)
end
X {v S : v-X2 camino }
return (I, X)
Este algoritmo devuelve I I1 I2 , X S tal que |I| = r1 (X) + r2 (S \ X). Se demostrara la correctitud de este
algoritmo en dos lemas:
Lema 2. Si I es tal que en D no existe un X1 -X2 camino entonces el conjunto X retornado por el algoritmo satisface
|I| = r1 (X) + r2 (S \ X).
Demostraci
on. Se probar
a que |I X| = r1 (X). Se razonara por contradiccion: si esto no ocurre significa que
|I X| < r1 (X)
(2)
Notar que X2 X y X1 X = (Pues se sale del while cuando no existen X1 -X2 caminos). De (2) sabemos que x X \I
tal que I X + x I1 (Pues si el conjunto independiente I X tiene cardinal menor que el rango siempre se puede
aumentar). Por otro lado como I es independiente, I X + x I1 entonces es posible aumentar el tama
no de I X + x
con elementos de I \ ((I X) + x hasta que tenga tantos elementos como I. De aqu se concluye que como I X + x tiene
un elemento m
as que I X entonces y I \ X tal que I + x y I1 . Luego por definicion se tiene que (y, x) D pero,
esto es una contradicci
on pues, como x X entonces x-X2 camino luego existe un y-X2 camino pero y
/ X.
De forma similar se prueba (cambiando el rol de X por el de S \ X) que |I (S \ X)| = r2 (S \ X) de lo que se tiene que,
|I| = |I X| + |I (S \ X)|
|I| = r1 (X) + r2 (S \ X)
Esto concluye la demostraci
on del teorema.
2

aticas
I X
Figura 2: Diagrama situaci

on demostraci
on anterior: el cuadrado representa el conjunto X y el circulo el conjunto I
Lema 3. Si P es un X1 - X2 camino mnimo IV (P ) I1 I2 .

Veamos primero una proposici
on antes de demostrar el lema.
Proposici
on 1. Sea M (S, I) una matroide. Si I I, J S son tales que existe un u
nico matching perfecto N entre I y
J en G = G(M, I), entonces J I.
Notemos que es una especie de recproca del lema del inicio de la clase. Utilizemos esta proposicon para demostrar el
lema 2.
X2
X1
v1
S\I
I
t
Figura 3: P un X1 - X2 camino.
Demostraci
on del Lema 3. Una observaci
on que podemos hacer de la figura es que si X1 X2 6= y X1 X2 I +y I1
y I + y I2 luego I + y I1 I2 . Consideremos entonces el caso X1 X2 = y demostremos en primera instancia que
IV (P ) I1 . Definimos la matroide auxiliar M1 = (S + t, {F S + t : F t I1 }), donde t es un elemento auxiliar
fuera de S. Notar que en el grafo de intercambios G(M1 , I + t), el elemento t se conecta mediante una arista a todos los
elementos de X1 .
Las aristas pares del camino P junto con e = tv1 , donde v1 es el primer vertice de P , son un matching perfecto entre
I V (P ) + t y V (P ) en el grafo G(M1 , I + t). De hecho este es el u
nico matching perfecto en G(M1 , I + t) entre estos
conjuntos, esto pues de existir otro existira un camino mas corto de X1 a X2 en G, pero por hipotesis P era de largo mnimo.

aticas
Usando la proposici
on obtenemos que I + t I1 IV (P ) I1 , esto u
ltimo pues I + t \ (IV (P )) = V (P ) I + t
e IV (P ) \ (I + t) = V (P ) \ I. Como IV (P ) no contiene a t, entonces IV (P ) I1 .
De la misma forma, podemos probar IV (P ) I2 simplemente agregando ahora t como u
ltimo vertice de P . Esto
completa la demostraci
on.
S
olo resta demostrar la proposici
on.
I \J
J \I
N
I J
S\I
Figura 4: Digrafo Auxiliar

Demostraci
on de la Proposici
on 1. Dirigimos las aristas del matching N hacia la izquierda y el resto de las aristas de G
hacia la derecha. En este digrafo no hay ciclos dirigidos, pues si hubiese un C diciclo entonces N C sera otro matching
perfecto entre I \ J y J \ I. Luego es un un digrafo acclico y entonces tiene un orden topologico.
De hecho podemos imponer que si e = xy M entonces el ndice de y en el orden es uno mayor que el de x. Formalmente
significa que podemos tomar una funci
on : S 7 |S| tal que si M = {y1 x1 , y2 x2 , ...} entonces (xi ) = (yi ) + 1 < (yi+1 ).
Notemos que bajo esta numeraci
on no existen arcos desde xi , yi hasta yj , xj respectivamente para j < i.
Supongamos que J
/ I luego existe C circuito contenido en J. Dicho circuito contiene alg
un yi J \ I y lo tomamos
con el mayor subndice.
C (J \ I)
xi
yi
Figura 5: I \ J y J \ I
OrdenTopol
ogico

aticas
Por construcci
on xi y no es arista (incluso olvidando la direccion) de E para cualquier y C yi . Como xi y
/ E
entonces I + y xi
/ I, luego y Span(I xi ) por lo que C yi Span(I xi ).
Por otro lado, como C es circuito, yi Span(C yi ) Span(I xi ). Es decir, yi esta generado por I xi y luego
I xi + yi no puede ser independiente. Pero esto contradice que xi yi E(G(M, I)).

aticas

Profesor: Jose Soto
Escribas: Christopher Cabezas, Catalina Pesce y Valentina Toro
C
atedra 18
1.
Volveremos a presentar los resultados de la clase anterior para plantear un algoritmo que calcule el conjunto independiente com
un de cardinalidad m
axima entre las matroides M1 = (S, I1 ) y M2 = (S, I2 ) con I = I1 I2 .
Lema 1. Sean X1 , X2 S \ I, con X1 X2 = . Si no existe X1 -X2 camino en D = D(M1 , M2 , I), entonces I es un
conjunto independiente com
un y de hecho:
X = {x S : x-X2 camino en D}
satisface:
|I| = r1 (X) + r2 (S \ X).
Lema 2. Sea P un X1 -X2 camino en D (si es que existe) con el menor n
umero de arcos posibles, entonces
IV (P ) I1 I2 ,
2.
con |IV (P )| = |I| + 1.
Sobre intersecci
on de matroides
A partir de los resultados anteriores, se obtiene el siguiente teorema.
Teorema 1. Sean M1 = (S, I1 ) y M2 = (S, I2 ) matroides, r1 () el rango con respecto a M1 y r2 () el rango con respecto
a M2 . Entonces
m
ax |J| = mn [r1 (X) + r2 (S \ X)] .
JI1 I2
XS
Ejemplo 1. Veamos como se interpreta este teorema en un grafo bipartito. Sea G = G(L, R, E) grafo, M1 = (E, I1 ) y
M2 = (E, I2 ) con I1 = {F E : |F (F )| 1, v L} e I2 = {F E : |F (F )| 1, v R}.
Notemos que M es un matching en G si y solo si M I1 I2 , es decir, si M tiene a lo m
as una arista incidente en
v, para cada v en L y R.
Tenemos que
m
ax
M matching
|M | = mn [r1 (X) + r2 (E \ X)].

XE
Analicemos lo que representa r1 (X):

r1 (X) = m
ax |J|
JI1
JX
= # de vertices de L que son tocados por alguna arista de X

= mn # de vertices de L necesarios para cubrir X.
Luego,
r1 (X) + r2 (S \ X)
= mn # de vertices de L
+
mn # de vertices de R
necesarios para cubrir X
necesarios para cubrir E \ X
= mn # de vertices de cubrimiento de X.
Entonces, el teorema anterior equivale a

m
ax
M matching
|M | =
que corresponde al teorema de K

onig visto en la clase 13.
1
mn
C cubrimiento
|C|.

aticas
A continuaci
on se presenta un algoritmo que calcula el conjunto independiente com
un de cardinalidad m
axima en D,
cuya correctitud est
a garantizada por las proposiciones anteriores.
Algoritmo 1: Algoritmo de conjunto independiente com
un de cardinalidad maxima en digrafo de intersecci
on.
Entrada: M1 ; M2 .
I
D D(M1 , M2 , I)
Elegir X1 , X2 S \ I, con X1 X2 =
while X1 -X2 camino en D do
P X1 -X2 camino m
as corto en D
I IV (P )
Recalcular D, X1 , X2
end
X {x S : x-X2 camino en D}
return (I, X)
Complejidad. Sea n = |E|, donde E es el conjunto de arcos de las matroides. Notemos que obtener el digrafo D, X1
y X2 en el algoritmo toma O(n2 ) unidades de trabajo y llamadas a oraculos de independencia para M1 y M2 . Adem
as,
cada vez que se pasa por el while se debe revisar si existe un camino entre los conjuntos X1 y X2 en D, lo que se puede
hacer agregando dos nodos s y t al digrafo, uno conectando a todos los vertices de X1 y el otro conectando a todos los
vertices de X2 , luego se busca con BFS un s-t camino, lo que toma O(n2 ).
Dentro del while, calcular el X1 -X2 camino m
as corto demora O(n2 ) y luego calcular IV (P ) demora O(n). Recalcular
D, X1 y X2 toma, al igual que al comienzo, O(n2 ). Finalmente, asignar a X aquellos elementos x X tal que haya un
x X2 camino en D toma lo mismo que encontrar un x X2 camino, por lo tanto esta operacion demora O(n2 ). Adem
as,
como el while se ejecuta a lo m
as n veces, entonces el algoritmo es O(n3 ).
Veamos ahora el siguiente problema. Se requiere dise
nar un algoritmo para determinar si un grafo G = (V, E) tiene
dos arboles generadores disjuntos y, en caso de que existan, encontrarlos.
Planteemos el problema en terminos de matroides. Sea M = M (G) la matroide grafica de G. Recordemos que para
T E
T I(M ) T no tiene ciclos T es un bosque
Buscamos entonces un conjunto T E tal que:
T I(M )
|T | = n 1, es decir, que T sea bosque generador.
En E \ T haya un
arbol generador de G, es decir, T I(M ).
Considerando esto, queremos revisar si
n1 =
m
ax
T I(G)I (G)
|T |.
Para ello, estudiemos el siguiente algoritmo.

Algoritmo 2:
Usamos el Algoritmo 1 con M1 = M (G), M2 = M (G), para encontrar T que maximice |T |, sujeto a que
T I1 I2 .
Si |T | < n 1 no existe soluci
on (se puede encontrar un conjunto X E tal que |T | = r1 (X) + r2 (E \ X)).
Si |T | = n 1, buscamos/encontramos T2 en G \ T arbol generador.

aticas
Del teorema de intersecci

on de matroides, existen dos arboles disjuntos si y solo si
n 1 = mn r1 (X) + r2 (E \ X)
XE
Realizamos el siguiente c
alculo:
r1 (X) + r2 (E \ X) = r1 (X) + [ |E \ X| + r1 (X) r1 (E) ] ,
= |E \ X| + 2r1 (X) r1(E),
= |E \ X| + 2[ |V | cc(X) ] r1(E),
= n + 1 + |E \ X| 2cc(X).
Reemplazando en la expresi
on anterior obtenemos que existen dos arboles disjuntos si y solo si
n 1 = mn n + 1 + |E \ X| 2cc(X),
XE
es decir, X E, |E \ X| 2(cc(X) 1).

Problema controlable. Probar que existen k arboles generadores arista-disjuntos en G si y solo si para toda partici
on
de V en p partes se tiene que
d(V1 , . . . , Vp ) k (p 1).
3.
Flujos en redes
Comenzamos ahora el estudio de un concepto fundamental en optimizacion combinatorial: el de flujos en redes. Supongamos, a modo de ejemplo, que tenemos que transportar agua a traves de tuberas desde s (nodo origen) hasta t (nodo
destino), como se muestra en la Figura 1. Para este proposito tenemos distintas rutas que podemos utilizar y cada tubera
posee distinta capacidad, es decir, cada tubera soporta un volumen distinto de agua. Queremos elegir la ruta de tuberas
que permita llevar la mayor cantidad de agua al destino t respetando las capacidades de cada tubera. Para solucionar
problemas como este plantearemos la siguiente teora.
Figura 1. Ejemplo de flujo en redes.

Definici
on 1. Sea G = (V, E) un digrafo. Una funcion de capacidad es una funcion U : E R+ , es decir, que a cada
arista le asigna un valor real positivo.
Definici
on 2. Llamamos red a una tupla (G, u, s, t) donde G = (V, E) es un digrafo, u una funcion de capacidad, s un
nodo origen y t un nodo destino.
Definici
on 3. Un flujo es una asignaci
on f : E R tal que
v V \ {s, t} : f ( (v)) = f ( + (v)),
donde f (X) =
f (e),
eX
es decir, todo lo que entra a cada nodo tiene que salir.

Esta condici
on se llama condici
on de conservacion de flujo. Ademas, se dice que un flujo es factible si
e E
0 f (e) u(e),
es decir, se dice factible si el flujo respeta la capacidad de los arcos de la red.

3

aticas
Definici
on 4. Definimos el flujo neto de entrada para un vector X : E R como:
X IN (v) = X( (v)) X( + (v))
Observaci
on 1. Sea X : E R. X(e) tambien se interpreta como X RE , Xe . Adem
as uno puede extender X a
conjuntos F E,
X
X(F ) =
Xe .
eF
Observaci
on 2. f es flujo si y s
olo si f IN (v) = 0, v V \ {s, t}
Veamos ahora el siguiente problema. Se requiere encontrar el flujo f factible en (G, U, s, t) que maximice f IN (t), es
decir,
m
ax
f IN (t)
s.a f = 0, v V \ {s, t}
0 fe Ue , e E
En realidad, esto corresponde a un PL. Veremos mas adelante que el PL se puede resolver en tiempo polinomial en el
tama
no de la entrada.
Ahora, estudiaremos especficamente el problema de flujos. Definimos el valor de un flujo f como
valor(f ) = f IN (t).
Teorema 2. Si f es un flujo factible, entonces
1. valor(f ) = f OU T (s) := f IN (s).
2. S V tal que s S y t 6 S se tiene que
valor(s) = f OU T (S) = f ( (S)) f ( + (S)).
Demostraci
on.
1. Como f es un flujo factible, sabemos que v V \ {s, t} f IN (v) = 0. Entonces
f IN (t) f OU T (s) = f IN (t) + f IN (s).
Por lo que,
f IN (t) + f IN (s) =
f IN (v),
vV
(f ( (v)) f ( + (v))),
vV
=
=
fe
vV
e (v)
fe
vV e (v)
X X
vV e + (v)
= f (E) f (E),
= 0.
Por lo tanto f IN (t) f OU T (s) = 0. Concluimos que valor(f ) = f OU T (s).
4
fe ,
e + (v)
fe ,

aticas
2. Como f es un flujo factible, tenemos que v V \ {s, t} f OU T (v) = 0. Luego

X
f OU T (s) =
f OU T (v),
vS
(f ( + (v)) f ( (v))),
vS
X X
fe
vS e + (v)
X X
fe ,
vS e (v)
= (f ( + (S)) + f (E(S))) (f ( (S)) + f (E(S))),

= f ( + (S)) f ( (S)),
= f OU T (S).
Donde E(S) = {e E : t(e), h(e) S}. Por la parte 1, tenemos que valor(f ) = f ( + (S)) f ( (S)).
Definici
on 5. Sea (G, u, s, t) una red y S V . Diremos que S es un s-t corte si s S y t 6 S. Luego, denotamos la
capacidad de un s-t corte por
X
u( + (S)) =
ue .
e + (S)
Teorema 3. Si f es factible, entonces S V tal que s S y t 6 S, valor(f ) u( + (S)).

Demostraci
on. Se tiene que
valor(f ) = f ( + (S)) f ( (S)) f ( + (S)) u( + (S)).
Notemos que por el Teorema 3 tenemos el siguiente resultado de dualidad debil:

m
ax
valor(f )
f : factible en (G,u,s,t)
mn
S st: corte
u( + (S)).
La pr
oxima clase veremos en m
as detalle la aplicacion de dualidad debil a flujos en redes.

aticas

Profesor: Jose Soto
Escriba: Manuel C
aceres.
Fecha: 17 de Octubre 2014 .
C
atedra 19
1.
Previo
En la clase pasada se vio:
(G, u, s, t) es una red, donde:
G = (V, E) digrafo.
u : E R+ , funci
on de capacidad.
s V , nodo de origen.
f V , nodo destino.
f IN (v) = f ( (v)) f ( + (v)).
f OU T (v) = f IN (v).
valor(f ) = f IN (t) = f OU T (s).
f flujo factible si f IN (v) = 0 para todo v V \ {s, t} y ademas 0 f u.
S V es un s-t corte si s S y t V \ S.
(Dualidad debil)
m
ax
f flujo factible
valor(f )
mn
S s-t corte
u( + (S))
El problema consista en encontrar un flujo factible de mayor valor. Este se poda resolver con el siguiente programa lineal:
m
ax f IN (t)
s.a f = 0 , v V \ {s, t}
0 fe ue , e E,
pero se buscar
a un algoritmo combinatorial que lo resuelva.
Ejemplo 1. Sea el digrafo :

1
HH

*

H

2HH
2

HH

1
j t
s
*

H
HH

2
2

H
HH
?

j
H
2

donde se etiquetan los arcos con sus capacidades.

aticas
Idea b
asica
Encontrar un s-t camino por el cual podemos enviar mas flujo del que actualmente mandamos, actualizar la funci
on
de flujo y repetir el procedimiento anterior.
Problema
Supongamos que el primer st camino que encontramos es s 1 2 t, por donde mandamos uno de flujo (el
m
aximo de las capacidades de los arcos del camino).
Luego nuestro grafo queda :

1
HH
*

HH

1
2 H

HH

0
j

s H
* t

HH

1
H2H
?
H
j
H
2

donde se etiquetan los arcos con las capacidades menos el flujo enviado hasta el momento.
Despues repetimos el proceso, donde encontramos los st dicaminos :
s 1 t, por donde enviamos uno de flujo.
s 2 t, por donde enviamos uno de flujo.
Quedando finalmente con el grafo :

1
H
*
HH

1HH
0

HH

0
j t
s
*

H

HH

0
H1

HH
?

j
H
2

al cual no se le puede aumentar su valor usando el algoritmo (pues no hay st camino por donde pueda enviar flujo).
As nuestro algoritmo b
asico encuentra un flujo de valor 3, el cual no es optimo, pues se podra haber mandado dos
unidades de flujo por s 1 t y dos por s 2 t, obteniendo un flujo de valor 4.
Idea mejor
Complementar lo anterior con la posibilidad de devolver flujo1 .
Esta idea, se traduce en usar arcos hacia adelante, cuya capacidad residual sea ue fe (que representa el flujo que
a
un se puede mandar por ese arco), y arcos hacia atras con capacidad residual fe (que representa el flujo que podra ser
devuelto por este arco).
Para continuar necesitaremos formalizar esta idea :
1 En
el ejemplo esto sera devolver el flujo del arco 1 2 para mandarlo por 1 t , y as alcanzar el o
ptimo.

aticas
Definici
on 1. (RED RESIDUAL)
Dado f, flujo factible en la red (G, u, s, t), se construye la red residual (Gf , uf , s, t),donde :
Gf = (V, E E), E = { e : e E}, con e , arco antiparalelo a e.2

(
ue fe si e E(G)
f
f
e E(G ), ue =
fa
si e = a E(G)
Ejemplo 2. Si G es nuestro grafo del ejemplo anterior, y f la obtenida al aplicar la Idea b
asica.

1
HH

*

HH

2
1 H

HH

1
j

s H
* t

HH

2
H1
HH
?
j
H
2

donde las etiquedas de los arcos ahora representan la funci
on de flujo.
Entonces su red residual sera:

YH
1 H
H H 1
*
2

6 HHHH
0
1HHHH

H

0
1
j
H
s
* t

H

YHH
H

HHH1
0

H
H H
?
j
H
2
1 HHH
2

Observaci
on 1. Informalmente, lo que nos gustara hacer es empujar uno de flujo en s 2, devolver uno en 1 2 y
empujar otro en 1 t, lo que se podra hacer es encontrar un dicamino en el grafo residual, cuyos arcos tengan pesos
positivos. Veremos a continuaci
on que esto se tiene de un modo un poco m
as general.
Lema 1. Sea f un flujo factible en (G, u, s, t).
Si g : E(Gf ) R es un flujo factible en la red residual (Gf , uf , s, t).
Definimos g : E R como
g(e) = g(e) g( e ).
Entonces f + g es flujo factible en (G, u, s, t) de valor : valor(f ) + valorGf (g).
Antes de ir a la desmostraci
on veamos que significa lo anterior graficamente :
2 Notar
que para cada arco se adjunta el arco reverso, incluso si ya existe otro arco que conecte los mismos nodos en ese sentido.

aticas
1. Grafo G con u como etiquetas

1
HH
*

HH

2
2 H

HH

1
j

s H
* t

HH

2
2
HH
?
H
j
H
2

2. Grafo G con f como etiquetas

1
HH
*

HH

2
1 H

HH

1
j

s H
* t

HH

2
H1H
?
H
j
H
2

3. Grafo Gf con uf como etiquetas

YH
1 H
HHH 1
2
*

HH
6

H
0
1HHHH

HH
0 1
j

s H
* t

H

YHH 1
H

0
HH
HH

?

H
2
j
1 HHH

H 2

4. Grafo Gf con g como etiquetas3

YH
1 H
HHH 0
0
*

HH
6

H
0
1HHHH

HH
0 1
j
s
* t

HH

YHH 1
H

0
HH
HH

?

H
0
j
H
0 HHH
2

5. Grafo G con g como etiquetas

1
HH
*

H

0
1HH

H

1
j
H

s H
* t

HH

0
H1

HH
?

j
H
2

Demostraci
on Notar que
6. Grafo G con f + g como etiquetas

1
HH
*

H

2
2HH

H

0
j
H
s
* t
H

HH

2
H2

HH
?

j
H
2

+
gIN (v) = g(E
(v)) g(E
(v))
+
+
= g(E
(v)) g(
(v)) g(E
(v)) + g(
(v))
E
+
IN
= g(E(G
f ) (v)) g(E(Gf ) (v)) = g(Gf ) (v).
Luego:
(f + g)IN (v) = f IN (v) + g IN (v)Gf
v 6 {s, t}
0
= valor(f ) + valorGf (g)
v=s
valor(f ) valorGf (g) v = t
En particular f + g es flujo en (G, u, s, t). Por otro lado, f (e) + g(e) = f (e) + g(e) g( e ) f (e) + (u(e) f (e)) 0 = u(e),
y f (e) + g(e) = f (e) + g(e) g( e ) f (e) + 0 + f (e) = 0.

Lo que dice que f + g es factible.
Diremos que f + g se obtiene aumentando f con el flujo residual g.
3 Notar
que este flujo en particular es un camino.

aticas
Para el caso particular en que P es un (s, t)-camino en Gf , definimos :

ufP = mn ufe (capacidad residual de P).
eP
P : E(Gf ) {0, 1}, tal que P

e = 1 e P (vector indicatriz).
Si la capacidad residual es positiva, el camino P se dice aumentante para f.
Notar que el vector ufP P es un flujo factible en la red residual.4 Luego por el lema anterior.
f + ufP P
es flujo factible en la red original, de valor igual a valor(f ) + ufP .
Notemos como consecuencia de este lema que para ver si se puede aumentar el flujo f , basta buscar un (s, t)-camino
en Gf que tenga capacidades positivas. Eso se puede lograr quitando los arcos de capacidad 0 de Gf : llamaremos el grafo
obtenido Gf+ . Basta ahora buscar un (s, t)-camino en Gf+ , ocupando por ejemplo BFS o DFS.
Ahora se puede presentar un algoritmo para encontrar un flujo maximo en una red : el algoritmo de Ford y Fulkerson.
Algoritmo de Ford-Fulkerson
La b
usqueda de tal algoritmo empez
o durante la segunda guerra mundial por razones militares. Uno de los ejercitos
estaba recibiendo armas tras una red de puentes, el enemigo busco cual era la mnima cantidad de puentes a destruir para
impedir la llegada del armamiento.
Algoritmo 1: Algoritmo de Ford-Fulkerson
Entrada: (G, u, s, t), red.
f 0(flujo 0)
Construir red residual (Gf , uf , s, t)
while P , st camino aumentante para f do
f f + ufP P
Actualizar (Gf , uf , s, t)
end
return f
Lema 2. No hay caminos aumentantes para f f es flujo m
aximo.
Demostraci
on
: Si existe un camino aumentante P en Gf , entonces f + ufP P es un flujo factible con mayor valor.
: Supongamos que no existen caminos aumentantes, es decir que Gf+ no tiene (s, t)-caminos. Llamemos S el conjunto
de los nodos alcanzables desde s en Gf+ , notemos que s S, t
/ S, por lo que S es un st corte.
Vamos a calcular la capacidad de S, u( + (S)).
Sea e = ab (S).
Si e + (S), ufe = ue fe en Gf . Si tuvieramos ufe > 0, tendriamos e E(Gf+ ) y como a S, tendramos b S,
contradicci
on. Entonces ufe = 0 y ue = fe de lo que deducimos u( + (S)) = f ( + (S)).
Si ab = e (S), uf = fe . Si tuvieramos ba = e E(Gf+ ) tendriamos que b S implica a S lo que es una

e
contradicci
on. Entonces uf = 0 entonces fe = 0, y u( (S)) = 0.
e
Se tiene entonces por conservaci

on de flujo que valor(f ) = f ( + (S)) f ( (S)) = u( + (S)) 0 = u( + (S)). Adem
as,
sabemos por dualidad debil que para cada flujo f 0 y cada s-t corte S 0 se tiene valor(f 0 ) u( + (S)). Como se tiene la
igualdad para f y S, f es flujo m
aximo y S es corte de capacidad mnima.
4 Pues
f
f
f
e P, ufP P
/ P, ufP P
e = uP c ue y e
e = 0 ue .

aticas
Observaci
on 2. En dualidad debil para flujos y st cortes vimos,
m
ax
f flujo factible
valor(f )
mn
S st corte
u( + (S)),
pero no justificamos por que el lado de la izquierda era un m

aximo (y no s
olo un supremo), y es pues f es un flujo factible
si f IN (v) = 0, v V \ {s, t}, y 0 f u, que forma un poltopo acotado(por lo tanto compacto), luego como f es
continua, alcanza su m
aximo.
Teorema 1 (Flujo m
aximo y corte mnimo). Para cada red (G, u, s, t) se tiene
m
ax
f flujo factible
valor(f ) =
mn
S st corte
u( + (S))
Adem
as S se puede encontrar buscando el conjunto de los nodos alcanzables desde s en Gf+ .
Observaci
on 3. Acerca del algoritmo de Ford-Fulkerson
Teorema de integralidad de flujo m
aximo: Si las capacidades son enteras, es decir u : E R+ y adem
as el flujo
m
aximo es finito, entonces existe un flujo f con coordenadas enteras. (demo: El algoritmo de Ford y Fulkerson
mantiene la integralidad de f y en cada iteraci
on el valor del flujo aumenta en al menos una unidad, luego el
algoritmo termina).
Se puede probar, amplificando, que si las capacidades son racionales entonces el algoritmo de Ford y Fulkerson
termina.
En el caso de capacidades irracionales, es posible que no termine.
De hecho, es posible que el valor lmite del flujo construido sea estrictamente menor que el valor de un flujo
optimo.
Facultad de Ciencias Fsicas y Matemticas

Profesor: Jos Soto
Escriba(s): Camilo Rojas , Cristbal Rojas y Francisco Venegas.
Fecha: Lunes 20 de Octubre, 2014.
Ctedra 20
1.
Teorema de Descomposicin de flujos
Teorema 1. (Descomposicin de flujos) Todo (s, t)-flujo se puede descomponer en ciclos y (s, t)-caminos.
Sea (G, u, s, t) una red y f flujo en sta red (factible o no). Sean
Pst el conjunto de todos los (s, t)-caminos en G.
Pts el conjunto de todos los (t, s)-caminos en G.
C el conjunto de todos los ciclos en G.
Si valor(f ) 0, podemos escribir
X
X
f=
p p +
c p
pPst
cC
Si valor(f)< 0, podemos escribir

X
X
f=
p p +
c p
pPts
cC
De hecho, todos los coeficientes 0 y el nmero de coeficientes no nulos son a lo ms |E(G)|.

Observacin 1. Para cada p , se tiene que 0 p p f . Por lo que se verifica que si f es factible, entonces p p .
Ejemplo 1. En la siguiente figura se puede apreciar como se descompone el flujo en un ciclo y tres caminos.
1
1
2
t
s
t
s
3
2
2
1
Demostracin. Definamos para todo vector x RE , el soporte de x como Sop(x) = {e E : e > 0}

Definiremos iterativamente flujos factibles f i en la red (G, u, s, t), y grafos Gi = (V, Sop(f i )), donde f 0 se define como
f . Para ello repetiremos el siguiente proceso:
Si Gi = (V, Sop(f i )) contiene un ciclo C = Ci . Definimos f i+1 = f i fci c , con fci = mn fei as f i+1 es un flujo en
eC
(G, u, s, t) y valor(f i+1 ) = valor (f i ).

Notemos que Sopf i+1 ( Sopf i pues para e C pues al definir f i+1 anulamos el flujo de la arista e correspondiente a
mn luego esta arista sale del soporte, adems se cumple que valor(fei ) =valor(fei+1 ) = 0.
eC
Repetiremos este proceso creando flujos f 0 , f 1 , , f k hasta que el grafo Gk = (V, Sop(f )) sea ciclico.
Veamos que se verifica que:
(f 0) si valor(f ) 0. Entonces existe un s t camino en Sop(f i ), el caso f < 0 es anlogo
En Efecto,
Si hacemos BFS desde s en Sop(f i ) para calcular el conjunto S de los nodos alcanzables desde s obtenemos:
1
si t S BFS encuentra un x t camino.

si t 6 S S es un s t corte.
0 <valor(f i ) = f i ( + (S)) f i ( (S)) f i ( + (S))
Luego existe un arco e = uv + (S) con f i (e) > 0 entonces e Sop(f i ) lo que es una contradiccin pues u S, v S.
Con este resultado podemos tomar un P un s-t camino en G y definir:
f i+1 = f i fPi P
Sop(f i+1 ) ( Sop(f i )
fPi = mn fei
eP
donde se cumplira que 0 valor(f i+1 ) =valor (f i ) fP . De otra manera se podra haber encontrado un ciclo en Sop(f i ).
Repetiremos este proceso hasta que Sop(f i ) = . Finalmente se obtendra:
f=
k1
X
fcii ci +
l
X
i=0
fPi i Pi
i=k

Observacin 2. Todo (s, t)-flujo factible de valor positivo es combinacin cnica de indicatrices de (s, t)-caminos y de
ciclos.
Corolario 1. Si f es (s, t)-flujo factible en (G, u, s, t) (de valor positivo), entonces existe un (s, t)-camino en esta red con
valor(f )
capacidad mayor o igual que
.
m
P
P
Demostracin.
p p + c c . Esto implica que
P Por el teorema, sabemos que se cumple la siguiente igualdad f =
valor(f ) =
p . Como la combinacin es cnica y hay a lo ms m trminos no nulos, existe un (s, t)-camino p con
p > valor (f )/m.
Algorithm 1 Recuerdo Algoritmo de Ford-Fulkerson.
1: Dado (G, u, s, t) una red.
2: f .
f
3: while Existe un camino aumentante P en Gt do
p f
4:
Aumentar f con P (f f + up ).
5: end while
6: Return f .
Ejemplo 2. Malo para FF. Sea u = N N, con N 0.
FF podra elegir mal y partir con
,
Repitiendo esto, FF toma 2N iteraciones para llegar al ptimo. Esto NO es polinomial, pues la entrada se codifica en
O(ln(N )) bits.
2.
Algoritmo de Edmonds-Karp 1
Algorithm 2 E-K 1
Aumentar por el camino con mayor capacidad residual.
La clase anterior se prob que si f es factible en (G, u, s, t) y g es factible en (Gf , uf , s, t) entonces f + g es factible en
(G, u, s, t), con ge = ge + ge donde g : E R y g : E E R. Recordar que el dominio de g es E E , mientras
que el dominio de g es E Ms an, este lema tiene una recproca:
Lema 1. Si f y h son factibles entonces h f = g para cierto g factible en (Gf , uf , s, t).
Demostracin. Defina g : E E 7 R del siguiente modo: Para e E
si he = fe
ge = he fe
si fe > he
ge = 0
ge = fe he
Del lema anterior se deduce que: Si f es factible en (G, u, s, t) y f es el flujo mximo en (G, u, s, t) entonces existe g
flujo en (Gf , uf , s, t) con valor(g) = valor(f ) valor(f ).
Por el corolario anterior, sabemos que existe s-t camino residual en (Gf , uf , s, t) de capacidad residual al menos
valor(g)
)valor(f )
= valor(f 2m
.
2m
Teorema 2. Sea u : E Z y no existe s-t camino de capacidad infinita en (G, u, s, t). Entonces Edmonds-Karp 1
termina en O(n log( ) = O(m+log(m m
ax ue )) iteraciones, por lo cual su complejidad es O((m+n log(n)(m log( ))
eE:ue <
Demostracin. sea f el flujo en la i-sima iteracin. (f 0 = 0E ) Sea el valor de un flujo mximo y i el valor de un
flujo fi . La observacin
anterior nos dice que en la i-sima iteracin se encuentra un camino aumentante de capacidad
i
residual al menos 2m
.
i
Luego i+1 i + 2m
.

1
i
Entonces i+1 i 2m
= ( i ) 1
2m
i
Despus de k iteraciones:
1
)
2m
1 2
( k2 )(1
)
2m
k ( k1 )(1
..
.
( 0 )(1
1 k
)
2m
1 k
)
2m
Observacin: Si k > 2m ln( )
1 2m ln( )
k (1
)

2m
2m ln
exp
= =1
2m
= (1
Usamos que (1 x) exp(x)

Es decir, despus de k = O(n ln()) iteraciones k < 1. Se concluye que k = , con lo que se llega al ptimo.
Complejidad
Hay O (n ln( )) iteraciones. En cada una se debe encontrar el camino con mayor cuello de botella de s a t en el grafo
residual (Gf , uf , s, t).
Esto se puede hacer modificando Dijkstra en tiempo O(m + n log(n)).
Observacin:
Esta versin de Edmonds Karp (1) es dbilmente polinomial, pues su complejidad depende del valor del nmero de datos.
3.
Algoritmo de Edmonds-Karp 2
Algorithm 3 E-K 2
Edmonds y Karp dieron un segundo algoritmo, que es fuertemente polinomial.
Aumentar por el camino P ms corto (segn el # de arcos)
Demostremos que E K(2) es fuertemente polinomial; mas an, usa a lo ms O(nm) .
i
i
Sea f i el flujo a la i-sima iteraciones, y Gi = (Gf , uf , s, t)

(i)
Usamos BFS en Gi+ , y llamemos Lk = v V : el s - v camino mnimo en Gi+ usa karcos
La prxima clase demostraremos el siguiente lema.

(i)
(i)
Lema 2. Si v Lk , entonces j i, v Lk0 , con k 0 k

aticas

Profesor: Jose Soto
andez, Emilien Garcia y Alberto Rojas.
Fecha: 24 de Octubre 2014 .
C
atedra 21
1.
Flujos m
aximos y Algoritmo de Edmonds-Karp (II)
Algoritmo 1 Edmonds-Karp
1: f
2: while (exista camino aumentante) do
3:
4:
5:
Aumentar en el camino P m
as corto (f f + ufp p )
end while
return f
(Con P s-t camino en Gf+ )
Lema 1. En cada iteraci

on i, definimos las siguientes capas:
(i)
Lj = {v V : distGfi (s, v) = j}
+
(i0 )
(i)
Si v Lj = para toda iteraci

on posterior i0 i, se tiene que v Lj 0 con j 0 j.
En otras palabras, la distancia entre s y v en el grafo Gf+i es una funci
on creciente en i.
(i)
Figura 1: Representacion de las capas Lj en una iteracion i.
Demostraci
on. Notar que en la iteraci
on i, aumentamos fi con un s-t camino Pi .
f
Que pasa con Gf+i 7 G+i+1 ? Que arco puede salir de Gf+ ?.
Si e E, ufei = u(e) fi (e). Al aumentar, este arco podra saturarse y su nueva capacidad residual ser 0.
nicos arcos que pueden salir de Gf+ son arcos de Pi
Lo mismo para si e E , ufei = fi (e), los u
Qu
e arcos pueden entrar a Gf+i ?.
Solo los arcos en P (los reversos de arcos de P).
(i)
(i)
Si e = uv es un arco que sale de Gf+i (hacia adelante), entonces u Lj , v Lk con j + 1 = k.
Si e = uv entra, entonces k + 1 = j (hacia atr
as).

aticas
En cada iteraci
on al menos 1 arco sale de Gf+ , este arco que sale no puede volver a entrar en iteraciones futuras muchas
veces. De hecho si e = uv sale, y u est
a en la capa j, entonces cuando vuelva a entrar u debe estar en una capa de ndice
mayor o igual que j + 2.
Luego e no puede entrar a Gf+ m
as que n/2 veces. As, cada arco sale a lo mas n/2 veces. Como en cada etapa sale un
arco y hay 2m arcos en total, se concluye que el n
umero de etapas es a lo mas 2m(n/2) = nm
Por lo tanto hay a lo m
as:
O(mn) iteraciones
Teorema 1. Edmonds-Karp tiene complejidad

O(mn(m + n)) = O(m2 n)
Este algoritmo es fuertemente polinomial.

Corolario 1. Podemos encontrar flujos m
aximos y s-t cortes mnimos en tiempo O(nm2 )
f
(Recuerdo: S = {v : s-v camino en G+ para f m
aximo, en un s-t corte mnimo})
Observaci
on 1. Este no es el algoritmo m
as r
apido. Se puede mejorar a O(mn) por ejemplo, usando resultados muy
recientes (2012) de Orlin y de King, Rao y Tarjan.

aticas
2.
Problema del Corte de peso mnimo
En adelante trabajaremos en un grafo no dirigido conexo G = (V, E) dotado de una funcion de peso w : E R+ .
Buscamos encontrar un conjunto de aristas F de peso mnimo que desconecte al grafo, es decir:
F arg mn{w(F ) : (V, E \ F ) es disconexo}
Problema Controlable 1. Demuestre la existencia de una solucion de este problema de la forma F = (S) con S
E.
Por el controlable, sabemos que este problema se reduce a encontrar un corte S E con w((S)) mnimo. Este
problema se puede resolver utilizando tecnicas de flujo ya conocidas, pues Edmonds-Karp nos entrega un flujo m
aximo,
lo que equivale a encontrar un s-t corte mnimo. Por lo tanto podemos encontrar un corte mnimo simplemente iterando
Edmonds-Karp.
Una primera estrategia consiste en buscar un s-t corte entre dos vertices cualquiera y minimizar el peso del corte
sobre todos los pares s-t. As encontraremos el corte mnimo tal que al menos dos vertices no pertenezcan a la misma
componente conexa, es decir, que desconecte el grafo.
Algoritmo 2 Calculando todos los s-t cortes
1: Dirigir el grafo: G0 (V, {uv, vu : {u, v} E}) (donde los arcos heredan el peso de las aristas de las que provienen).
2: for ( s, t V : s 6= t ) do
3:
Calcular F (s, t) mnimo s-t corte de G0
4: end for
5: Calcular el corte F mnimo sobre todos los F (s, t)
6: return F
Una mejora sobre el algoritmo anterior ocupa la transitividad de la conexidad en un grafo. Con esto basta que
analicemos un u
nico vertice s. Pues si desconectamos dos vertices entre s, entonces necesariamente alguno de ellos no
debe estar conectado con el vertice raz s, de lo contrario ambos vertices estaran conectados entre s por un camino que
pasa por s. Luego un corte entre dos vertices cualquiera es necesariamente un corte entre alguno de ellos y s.
Algoritmo 3 Calculando todos los cortes a partir de una raz
1: Dirigir el grafo: G0 (V, {uv, vu : {u, v} E}) (donde los arcos heredan el peso de las aristas de las que provienen).
2: Fijar s V
3: for ( t V \ {s} ) do
4:
Calcular F (s, t) mnimo s-t corte de (G0 )
5: end for
6: Calcular el corte F mnimo sobre todos los F (s, t)
7: return F
Revisemos la complejidad de estos algoritmos. En el primero se hacen O(n2 ) iteraciones, en cada una de ellas se
debe encontrar un s-t corte mnimo en un grafo conexo, lo que con Edmonds-Karp 2 demora O(m2 n). Por lo tanto el
primer algoritmo corre en O(n3 m2 ), lo cual es demasiado lento, pues dependiendo del grafo esto puede llegar a O(n7 ). El
segundo algoritmo es un poco mejor, ya que s
olo realiza O(n) iteraciones, demorandose en total O(n2 m2 ) que sigue siendo
demasiado lento, ya que puede llegar a ser O(n6 ).
Como estos algoritmos son muy ineficientes se vuelve necesario encontrar un algoritmo mas eficiente. Para encontrarlo ser
a necesario trabajar con propiedades de la funcion que queremos minimizar. Para esto introduciremos algunas
definiciones.
Definici
on 1 (Submodular). f : 2V R se dice Submodular si:
f (A B) + f (A B) f (A) + f (B)
Definici
on 2 (Modular). f : 2V R se dice Modular si:
f (A B) + f (A B) = f (A) + f (B)
3

aticas
Definici
on 3 (Supermodular). f : 2V R se dice Supermodular si:
f (A B) + f (A B) f (A) + f (B)
Observaci
on 2. La funci
on | | m
odulo de un conjunto (cardinal) es modular:
|A B| + |A B| = |A| + |B|
Proposici
on 1. Las funciones submodulares cumplen la propiedad de retornos decrecientes. Es decir dado X Y , z
/Y
se cumple:
f (Y + z) f (Y ) f (X + z) f (X)
Demostraci
on: Tomando A = X +z y B = Y se tiene que AB = X y AB = Y +z. luego ocupando submodularidad:
f (X) + f (Y + z) f (X + z) + f (Y )
f (Y + z) f (Y ) f (X + z) f (X)
Problema Controlable 2. La recproca tambien es cierta y queda propuesta su demostracion. Es decir pruebe que si
una funci
on cumple la propiedad de retornos decrecientes, es entonces una funcion submodular.
Muchas funciones son submodulares. Veamos algunos ejemplos :
1. La funci
on de rango de matroides.
2. El Teorema de Intersecci
on de Matroides nos dice que :
m
ax I = mn r1 (X) + r2 (S \ X)
II1 I2
XS
En esta igualdad, el lado derecho que minimizamos es una funcion submodular, pues :
La suma de funciones submodulares es una funcion submodular.
Si f es submodular sobre V , entonces g dada por g(X) = f (V \ X)(= f (X c )) tambien es submodular :
g(A B) + g(A B) = f (Ac B c ) + f (Ac B c ) f (Ac ) + f (B c ) = g(A) + g(B)
donde la desigualdad se tiene por submodularidad de f , y las igualdades por definicion de g.
3. Las funciones de cortes y de cortes dirigidos son submodulares :
Sean : E(G) R+ y f : 2V R tal que f (S) = ((S)) S V ; f es submodular ya que como lo muestra
el siguiente dibujo se cumple : f (A B) + f (A B) f (A B) + f (A B) + f (E(A : B)) = f (A) + f (B), donde
E(A : B) representa las aristas que van de A en B (o equivalentemente de B en A ya que el grafo no es dirigido).
on del conteo de las aristas asociadas a f (A) + f (B) y a f (A B) + f (A B).

aticas
Cada tipo de aristas aparece en este dibujo : las que no contamos en ninguna cantidad son grises y las que contamos
una vez en ambas cantidades son azules ; por otro lado, las que contamos dos veces aparecen en verde y rojo.
Ojo : los dos colores corresponden a dos casos de conteo distintos. En efecto, la arista verde la contamos dos veces
en f (A) + f (B) (est
a en el corte de A y en el corte de B) y dos veces en f (A B) + f (A B) (esta en el corte de
A B y en el corte de A B). Sin embargo, la arista roja se cuenta dos veces en f (A) + f (B) (esta en el corte de
A y en el corte de B, pues sale de A y sale de B) pero no se cuenta en f (A B) + f (A B) (no sale de A B ni
sale A B).
Con esto se entiende bien que las aristas contadas en f (A) + f (B) pero no en f (A B) + f (A B) son las que van
de A en B, es decir las contadas en f (E(A : B)).
4. En cierto sentido, las funciones submodulares son el analogo a las funciones convexas o concavas en optimizaci
on
continua :
Sea f con dominio 2V = {0, 1}V . Su dominio se puede ver como los vertices de un hipercubo, con coordenadas
0 o 1 en cada dimensi
on. Podemos extender su dominio a [0, 1]V de manera multilinear, donde {0, 1}V son los
vertices del cubo. Se puede verificar que f as extendida es convexa si y solo si la funcion original es submodular.
Si g : R R es c
oncava, entonces f dada por f (X) = g(|X|) es submodular.
Concentremonos ahora en las funciones de corte. Sean entonces el grafo (no dirigido) G = (V, E), las funciones :
E(G) R+ y f : 2V R tal que f (S) = ((S)) S V . Como lo acabamos de ver, f es una funcion submodular,
pero adem
as es una funci
on simetrica, en el sentido que f (X) = f (S \ X) X S.
Por eso estudiaremos un algoritmo para minimizar funciones a la vez submodulares y simetricas.
Definici
on 4 (Separador de dos elementos). S V separa dos elementos s, t V si |S {s, t}| = 1.
Definici
on 5 (Tro Factible). Sean s, t V y S V tal que S separa s y t, (S, s, t) se dira tro factible si es el mejor
separador de s y t, es decir si f (S) f (X) para todo X s-t separador.
Imaginemos que somos capaces de encontrar un tro factible. La idea es la siguiente : si (S, s, t) es un tro factible y X
es un mnimo para f ,
o bien X separa s y t, entonces f (S) = f (X), luego S es optimo.
o bien X no separa s y t, y entonces todo optimo tiene a s y t juntos.
Definici
on 6 (Fusi
on de dos elementos). Sea f : 2V R submodular, sean s, t V . La funcion fst : 2V st+st R
es la fusi
on de los dos elementos s y t, dada por :
si st
/X
f (X)
X (V s t + st), fst =
f (X {s, t} st) si st X
Veamos ahora la idea principal del algoritmo que minimiza una funcion submodular y simetrica :
Algoritmo 4 Minimizar f submodular simetrica
1: U
2: f 0 f
3: while (existe (S, s, t) tro factible de f 0 ) do
4:
U U + S 0 , donde S 0 es el conjunto obtenido al expandir los elementos de S.
5:
f 0 funci
on fusi
on de s y t
6: end while
7: return S arg mn{f (X) ; X U }
La pr
oxima clase, veremos un algoritmo m
as explcito que sigue este procedimiento para minimizar una funci
on
submodular y simetrica : el algoritmo de Queyranne.

aticas

Profesor: Jose Soto
Escriba(s): Juan Pablo Donoso, Felipe Garrido y Juan Granier.
C
atedra 22
1.
Recuerdo
Estabamos resolviendo el problema siguiente: Dado un grafo no dirigido conexo G = (V, E), dotado de una funci
on de
peso w : E R+ , queremos encontrar un conjunto de aristas F de peso mnimo que desconecte el grafo, es decir:
F arg min{w(F ) : (V, E \ F ) es disconexo}
(1)
2
Si bien se poda resolver con Edmond-Karp, esto nos llevo a una solucion O(n m2 ). Para encontrar una soluci
on m
as
eficiente, se introdujo el concepto de funci
on submodular y s-t separador.
Definici
on 1 (Separador de dos elementos). S V es un s-t separador si |S {s, t}| = 1
Definici
on 2 (Tro factible). Sean s, t V y S V un s-t separador. El tro (S, s, t) se dira tro factible si es el mejor
separador de s y t, es decir, si f (S) f (X) para todo X s-t separador.
Definici
on 3 (Funci
on submodular). f : 2V R+ se dice submodular si para todo A, B V
f (A) + f (B) f (A B) + f (A B)
diremos adem
as que f es simetrica si para A V
f (A) = f (V \ A)
Ejemplo 1. Dado G = (V, E) y w como antes, podemos tomar f : 2V R+ como
f (A) = w((A))
Por u
ltimo, para resolver el problema enunciado arriba mediante funciones submodulares simetricas, necesitamos
resolver el problema siguiente
mn{f (X) : ( X ( V }
(2)
para f una funci
on submodular y simetrica.
Observaci
on 1. Notemos que el problema interesante es tomar inclusiones estrictas, pues siempre se tiene que, para todo
X V y f submodular simetrica
2f (X) = f (X) + f (X)
f () + f (V \ X)
= 2f ()
La u
ltima c
atedra vimos que, asumiendo que somos capaces de encontrar un tro factible, entonces el siguiente algoritmo
resuelve (2).
Algorithm 1 Minimizar f submodular y simetrica
1: U
2: f 0 f
3: while (existe (S, s, t) tro factible para f 0 ) do
4:
U U + S 0 donde S 0 se obtiene expandiendo los elementos de S.
5:
f 0 funci
on fusi
on de s y t
6: end while
7: return S arg min{f (X) : X U }

aticas
Donde en el algoritmo anterior usamos la fusion de elementos:

Definici
on 4 (Fusi
on de elemtentos). Sea f : 2V R submodular, y sean s y t en V . La funcion fst : 2V st+st R es
la fusi
on de los dos elementos s y t, dada por:
(
f (X)
si st
6 X
fst (X) =
f (X {s, t} st) si st X
para todo X V s t + st.
Ahora veremos una manera de encontrar un tro factible, mediante el concepto de par colgante y el Teorema de
Queyranne.
2.
Par colgante y Teorema de Queyranne
2.1.
Par Colgante
En adelante consideraremos f una funci

on submodular y simetrica.
Definici
on 5 (Par colgante de f ). Un par ordenado (s, t) tal que ({s}, s, t) es tro factible se dice par colgante.
Mader (1978) demostr
o que toda funci
on submodular simetrica tiene un par colgante. Queyranne (1998) di
o un
algoritmo para encontrarlo. As, en vez de demostrar Mader, demostraremos Queyranne. Para esto necesitaremos la
bifunci
on de adyacencia.
Definici
on 6 (Bifunci
on de adyacencia). Dada f : 2V R+ , la bifunci
on de adyacencia d : 2V 2V R+ esta dada por
d(A, B) =
1
(f (A) + f (B) f (A B))
2
Ejemplo 2. Si f = w(()), entonces d(A, B) es el peso de todas las aristas que van desde A hasta B.
Lema 1. d(, ) satisface lo siguiente
1. Es simetrica, i.e. para todo A, B V :
d(A, B) = d(B, A).
2. f (A) = d(A, V \ A) + 12 f ().
3. d es mon
otona en el siguiente sentido: Para A, B, C V disjuntos
d(A, B) d(A, B C).
4. d es consistente: Para A, B, C V disjuntos
d(A, B) d(A, C) = d(A C, B) d(A B, C).
Demostraci
on Lema1.
1. Directo.
2. Sea A V .
1
(f (A) + f (V \ A) f (V ))
2
1
= f (A) f ()
(f (A) = f (V \ A) f (V ) = f ())
2
d(A, V \ A) =
de donde se concluye.
2

aticas
3. En efecto:
2(d(A, B C) d(A, B)) = f (A) + f (B C) f (A B C) (f (A) + f (B) f (A B))
= f (B C) + f (A B) f (B) f (A B C)
0
donde el u
ltimo paso se tiene por submodularidad.
4. Hacemos la misma idea que en (3)
(
(
(
(
(C)
(C)
(
(
2(d(A B, C) d(A C, B)) = f (A B) + f (C) (
f (A
B
f (A C) f (B) + (
f (A
B
((
((
= f (C) f (A C) f (B) + f (A B)
= f (A) + f (C) f (A C) (f (A) + f (B) f (A B))
= 2(d(A, C) d(A, B))
0
Para poder utilizar la bifunci

on de adyacencia, es necesario saber que significa que (s, t) sea un par colgante de f .
Tenemos lo siguiente:
(s, t) es par colgante de f S s-t separador, f ({s}) f (S)
S s-t separador, d({s}, V s) d(S, V \ S)
2.2.
Teorema de Queyranne
Mader (1978) prob

o que toda funci
on submodular y simetrica tiene un par colgante, de manera no constructiva. El
a
no 1998, Queyranne dio un algoritmo para encontrar un par colgante.
Teorema 1. Supongamos que V se ordena de forma {v1 , ...vn }, de modo que para todo i 2
d({v1 , ..., vi1 }, {vi }) d({v1 , ..., vi1 }, {vj }), j > i
Entonces, el u
ltimo par, (vn , vn1 ) corresponde a un par colgante.
Observaci
on 2. Este orden se llama Orden de M
axima Adyacencia.
Ejemplo 3. Consideremos el siguiente grafo con pesos.
Consideremos v1 arbitrario. Se elige v2 de modo que d(v1 , v2 ) sea m

aximo. Luego se elegir
a v3 de modo que d({v1 , v2 }, {v3 })
sea m
aximo, y as sucesivamente.
Queyranne nos dice entonces, que (v5 , v4 ) es par colgante.
3

aticas
Demostremos el Teorema de Queyranne.

Demostraci
on Teorema de Queyranne. Utilizamos induccion sobre |V | = n.
Caso n = 2: Tenemos que V = {v1 , v2 }. Luego, los singletons son los u
nicos v1 v2 separadores pues notemos que
d({v1 }, V \ {v2 }) = d({v1 }, {v2 }) = d({v2 }, {v1 })
Luego, no hay nada que probar.
Caso n = 3: Sea v1 , v2 , v3 un orden de m
axima adyacencia. Debemos ver que (v3 , v2 ) es par colgante. Sea X un v3 -v2
separador, cualquiera. Probaremos que
d({v3 }, {v1 , v2 }) d(X, V \ X)
Pero en realidad, basta probarlo para X = {v3 , v1 }, pues es el u
nico v1 -v3 separador distinto a (v3 , v2 ).
Veamos entonces que
d({v3 }, {v1 , v2 }) d({v3 , v1 }, {v2 })
En efecto, como el orden es de m
axima adyacencia, d(v1 , v2 ) d(v1 , v3 ), y luego se concluye por consistencia.
Caso n 4: Sea v1 , ..., vn orden de m
axima adyacencia. Sea X un vn -vn1 separador. Separaremos en 3 casos.
Caso 3.1: X no separa v1 de v2 . Definamos entonces V 0 = V v1 v2 + v1 v2 , la contraccion de los vertices v1 y v2 .
Dado X 0 V 0 , definimos

X si v1 v2
/X
expandir(X 0 ) =
X v1 v2 + v1 + v2 si v1 v2 X
De este modo, definimos
f 0 (X 0 ) = f (expandir(X 0 ))
Es f
acil ver que f 0 es simetrica y submodular. Ademas, su bifuncion de adyacencia d0 viene dada por
d0 (A, B) = d(expandir(A), expandir(B))
Como el orden inicial era de m
axima adyacencia para d, el orden v1 v2 , v3 , ..., vn es de maxima adyacencia para d0 y
tenemos que la cantidad de vertices es n 1. Luego, por hipotesis inductiva, (vn , vn1 ) es par colgante de d0 . Pero notemos
que
d0 (vn , V 0 vn ) d0 (X 0 , V 0 \ X 0 )
y expandir(X 0 ) = X, luego se obtiene, por definicion de expandir, que
d(vn , V vn ) d(X, V \ X)
y se concluye el primer caso.
Caso 3.2: X no separa v2 de v3 . Hacemos la contraccion de v2 y v3 y definimos V 0 = V v2 v3 + v2 v3 adem
as de
definir f 0 y d0 de forma an
aloga al caso anterior.
Veamos que v1 , v2 v3 , v4 , ..., vn es de m
axima adyacencia para d0 . Aprovechandose de que el antiguo orden era de m
axima
adyacencia para d y de la definici
on de expandir, solo falta chequear que
d0 (v1 , v2 v3 ) d0 (v1 , vk ), k 4
En efecto, por la monotona de d y por su m
axima adyacencia,
d0 (v1 , v2 v3 ) = d(v1 , {v2 , v3 }) d(v1 , v2 ) d(v1 , vk ) = d0 (v1 , vk ), k 4
Luego, de la misma forma que en el caso 3.1 se concluye que (vn , vn1 ) es par colgante de d.
Caso 3.3: X no separa v1 de v3 . Fusionamos entonces a v1 con v3 como lo hemos hecho en los casos anteriores. Veamos
que v2 , v1 v3 , v4 , ..., vn es orden de m
axima adyacencia para d0 .
Debemos ver que
4

aticas
d0 (v2 , v1 v3 ) d0 (v2 , vk ), k 4
O equivalentemente
d(v2 , {v1 , v3 }) d(v2 , vk ), k 4
En efecto, por m
axima adyacencia de d, d(v1 , v2 ) d(v1 , v3 ), luego por consistencia
d({v1 , v3 }, v2 ) d({v1 , v2 }, v3 )
d({v1 , v2 }, vk ), k 4
d(v2 , vk ), k 4
donde la segunda desigualdad se obtiene por m
axima adyacencia y la tercera por monotona.
Se concluye entonces al igual que en los casos anteriores que (vn , vn1 ) es par colgante de d0 , y luego, es par colgante
de d.
Gracias a que los casos 3.1, 3.2 y 3.3 cubren todos los escenarios posibles de X, se concluye que (vn , vn1 ) es par
colgante.
A continuaci
on escribimos el algoritmo de Queyranne en su forma recursiva e iterativa.
3.
Algoritmo de Queyranne
Algorithm 2 ALG (Queyrranne) para minimizar f (Version Recursiva)

1: if |V | = 2, (V = { s, t}) then
2:
devolver s
3: else
4:
if |V | 3 then
5:
Encontrar par colgante (s, t) de f
6:
Fusionar s y t para obtener f 0
7:
X 0 ALG(f 0 )
8:
end if
9: end if
Presentamos tambien una versi
on iterariva del algoritmo.
Algorithm 3 ALG (Queyranne) para minimizar f (Version Iterativa)
1: cand
2: V 0 V, f 0 f
3: while do |V 0 | 2)
4:
Encontrar par adyacente (s0 , t0 ) de f 0
5:
cand cand {expandir(S 0 )}
6:
Fusionar s0 y t0 y actualizar f 0 y v 0
7: end while
8: Devolver el mejor candidato, X arg min{f (X) : X cand}
Estudiamos la complejidad del Algoritmo de Queyranne
Complejidad: En total es O(n3 ) operaciones y O(n3 ) llamadas a un oraculo que calcule f . Pues
De la linea 1 a 2 toma O(n).
La linea 4 toma O(n2 ).

aticas
De la 5 a la 6 toma O(n).
Devolver el mejor candidato toma O(n) + O(nT (|V |)), donde hacemos el supuesto de que f (X) se puede calcular en
T (|V |).
As, la complejidad total es O(n3 ) operaciones y O(n3 ) llamadas al oraculo f , es decir O(n3 (1 + T (n))). La proxima clase
se ver
a que, para corte mnimo, efectivamente esto es O(n3 ), y se puede mejorar un poco a O(n log n + m).

Profesor: Jos Soto
Escriba(s): David Hasson , Martn Rios y Cristbal Rojas.
Fecha: Lunes 03 de Noviembre, 2014.
Ctedra 23
Recuerdo
En la clase anterior vimos el algoritmo de Queyranne, que nos permite encontrar un conjunto S (con ( S ( V ) tal que
minimice f (S) con f submodular y simtrica.
Algoritmo 1 Queyranne
1: cand
2: f 0 f
3: V 0 V .
4: while |V 0 | 2 do
5:
Calcular (s, t) par colgante del sistema (f 0 , V 0 ).
6:
Sea S el conjunto obtenido de {s} expandiendo todos los elementos fusionados.
7:
cand cand {S}.
8:
(f 0 , V 0 ) sistema donde s y t se fusionan.
9: end while
10: return argmin{f (X) : X cand} // el objeto S cand de menor f (S).
Veamos un caso particular: Sea f : 2V R, f (S) = w((S)) donde (V, E) es un grafo y w : E R+ funcin de pesos.
Fusionar los elementos (vrtices) es simple:
Algoritmo 2 f f 0 , fusin s y t
1: G0 = (V 0 , E 0 )
2: V 0 = V s t + st
3: E 0 = {xy E : x, y V s t} {(st)v : sv E o tv E}
4: w 0 : E 0 R+
5: if e = xy E(V s t) then
6:
w0 (e) = w(e)
7: else if e = (st)v then
8:
w0 (e) = w(sv) + w(tv) // abusando de la notacin: Si sv, tv 6 E, w(sv) = w(tv) = 0
9: end if
Esto se puede lograr en un tiempo O(n + m).
A continuacin presentamos un algoritmo para encontrar un par colgante.
Algoritmo 3 Orden de mxima adyacencia para G no dirigido.
Require: Par colgante (G, w).
vi v V (G) arbitrario.
for i = 2, . . . , |V (G)| do
vi argmax{d({v1 , , vi1 }, x) : x V {v1 , , vi1 }}.
end for
return (vn , vn1 ).
Algoritmo 4 Modificacin del anterior.

vi v |V (G)| arbitrario.
d(x) = 0 x V (G) v1
for j = 2, . . . , |V (G)| do
for x V \ {v1 , . . . , vj1 } do
d(x) d(x) + w(xvj1 ).
end for
vj argmax{d(x) : x V {v1 , , vi1 }}.
end for
return (vn , vn1 ).
En la primera versin calcular el mximo toma O(n) y como se realiza sobre todos los vrtices toma tiempo O(n). En
la modificacin la primera asignacin, el ciclo anidado y calcular el el mnimo toman tiempo O(n) luego el orden del
algoritmo es O(n2 ).
Complejidad del algoritmo de Queyranne para el caso de corte global mnimo

1. Encontrar un par colgante de G toma tiempo O(n2 )
2. Recalcular fusiones toma tiempo O(n + m)
As el algoritmo de Queyranne toma en total #iteraciones O(n2 + m) = O(n3 )
Observacin. Podemos calcular un corte global mnimo en O(n3 ) (mucho mejor que el O(n nm2 ) correspondiente a
resolver el problema con flujo mximo). Este tiempo se puede mejorar utilizando colas de prioridad:
Heaps Binarios: Encontrar par colgante toma tiempo O(m log n).
Heaps Fibonacci: Encontrar par colgante toma tiempo O(m + n log n).
As, se podr encontrar un corte global mnimo en tiempo O(n(m + n log n)).
Programacin lineal
Recordemos que si queremos calcular un flujo mximo f de una red una opcin habra sido resolver
(P )
m
ax
s.a.
f ( + (s))
f ( (v)) = f ( + (v)),
0 f U.
v V s t
Normalmente no es buena idea resolver el problema lineal cuando existen algoritmos combinatoriales disponibles. Pero a
veces la nica opcin es resolver este problema.
Se suele usar el mtodo SIMPLEX para resolver estos problemas dado que es rpido en la prctica, pero en general hay
instancias donde SIMPLEX demora tiempo exponencial. Es por esto que a continuacin veremos un algoritmo polinomial
para resolver PL, en general este algoritmo sirve para programas convexos con ciertas propiedades.
Mtodo de la Elipsoide
Dado K convexo y cerrado en Rd (de una manera implcita que se ver ms adelante), con K satisfaciendo ciertas hiptesis
mnimas, este mtodo puede o bien certificar que K es vaco o encontrar x K.
Para describir este mtodo necesitaremos introducir la siguiente notacin:
Definicin 1. Un Orculo de Separacin para un convexo K Rd es un algoritmo que puede describir K de la siguiente
manera:
Dado x Rd , el orculo dir si x K o si no est, en cuyo caso entregar un hiperplano separador c Rd , es decir,
ct x < C0 y ct y C0 , y K.
Diremos que el orculo es polinomial cuando ocurre en tiempo polinomial en (d, hKi, N ), donde
N = # bits necesarios para codificar nuestro problema.,
d = dimensin del espacio.,
hKi = #bits necesarios para codificar el convexo.
A continuacin se presentan algunos ejemplos de orculos.
Ejemplo 1.
1. Encontrar un orculo polinomial para el convexo K = {x Rd : Ax b y x 0} con A Qmd , b Qm dados.
Algoritmo 5 ALG(X)
Se denota ai a la fila i-sima de A.
if i aTi z b x 0 then
return z K.
else
Devolver la restriccin ati x bi (o xi 0) donde falla.
end if
Observacin. Esto es polinomial en la codificacin de A y b (y es polinomial en d).
2. Dado G = (V, E), n = |V |, m = |E| encontrar orculo de separacin para el convexo K = {x RE : x((S))
1, x 0, S V ; ( S ( V } en funcin de n y m
Si queremos un orculo polinomial, no podemos revisar todas las desigualdades, pues hay una cantidad exponencial
de ellas. Sin embargo, podemos hacer lo siguiente:
Algoritmo 6 ALG(X)
Dado x, revisar si x 0.
Utilizar x como funcin de peso y calcular el corte minimo global S del grafo.
if x((S)) 1 then
return true
else

1 si e (S )
devolver el hiperplano asociado a S , es decir, S =
0
si no
end if
Definicin 2. Una elipsoide E Rd es una transformacin lineal afn invertible de B(0, 1).
En otras palabras: T : Rd Rd ; T (x) = Ax + b con A invertible, b Rd .
La elipsoide asociada a T es
T (B(0, 1)) = {T (x) Rd : xt x 1}

t

= {y Rd : A1 (y b) A1 (y b) 1}
= {y Rd : (y b)t (At )1 A1 (y b) 1}
| {z }
M 1
Normalmente llamamos M = AAt y E(b, M ) = {y Rd : (y b)t M 1 (y b) 1} la elipsoide de centro b y matriz M .

Adems la elipsoide est bien definida cuando M es semidefinida positiva.
Observacin.
B(0, 1) = E(0, I)
B(0, r) = E(0, r2 I)
2
r1

En general la elipsoide con ejes de largo ri y centro 0 es E 0,
V ol(E(0; r1 , r2 , , rd )) = V ol(B(0, 1))
donde i son los valores propios de A.
..
Q
ri .En general V ol(E(b, A)) = V ol(B(0, 1)) det A = V ol(B(0, 1))
i ,
Mtodo de Elipsoide
INPUT:
K convexo cerrado con orculo de separacin.
Se supondr que se tienen p, R tales que K B(p, R)
Si K 6= , entonces existe c K tal que B(c, r) K.
donde p, R, r y el orculo de separacin son datos.
OUTPUT: K es vacio o no ? si no es vacio retornar x K
Algoritmo 7 Mtodo del Elipsoide
E B(p, R)
qp
while Vol(E) Vol(B(0, r)) do
if q K (preguntar al orculo) then
return q
else
El orculo devuelve un hiperplano c tal que ct q = 0 y ct y < 0, y K
E el elipsoide de volumen mnimo que contiene E {y : cT y cT q}
end if
end while
return K =
E0
E1
rd2
K
P
b
Lema 1 (de la media elipsoide). E(q, A) {x : cT x cT a} est contenida en E 0 = E(q 0 , A0 ) con q 0 = q
,
d
+
1

2
d
2
Ac
A
bbT con b =
.
d2 1
d+1
cT Ac
0
1
V ol(E )
Adems,
e 2d .
V ol(E)
La prxima clase vamos a ver que por este lema nmero de iteraciones no puede ser muy grande.
A0 =

aticas
MA3705. Algoritmos Combinatoriales. 2014

Profesor: Jose Soto
Escriba(s): Pedro Espinoza , Felipe Salas y Juan Jose Granier
Fecha: 6 de Noviembre de 2014.
C
atedra 24
1.
Definici
on.

1. Elipsoide. E(p, A) = x Rd : (x p)T A1 (x p) . Donde A es una matriz semidefinida positiva.
2. Or
aculo de separaci
on para convexo K Rd : Oraculo que dado x Rd responde:
xK
x
/ K y devuelve hiperplano c de separacion; cT x < cT y, y K
Figura 1: Hiperplano de separacion
2.
2.1.
M
etodo Elipsoide
Datos:
Convexo K Rd dado por or
aculo de separacion (polinomial)
B = B(a, R) tal que K B
> 0 tal que K 6= V ol(K) >
o bien r > 0 tal que K 6= c K; B(c, r) K.
2.2.
Output:
K=
K 6= y devolver x K

aticas
2.3.
M
etodo:
q a (centro);
E B(q, r);
while V ol(E) > do
Preguntar al or
aculo si q K;
if q est
a en K then
Responder q K;
end
else
Usar or
aculo para encontrar hiperplano z tal que z T q < z T y, y K;
0
E el elipsoide de volumen mnimo que contiene E {x : z T x z T q};
E E0
end
end
return K =
Figura 2: Segunda iteracion del metodo.

Lema 1. Dada E(q,A) Rd , tenemos
que E(q,
A) {x : z T x z T q} E(q 0 ,A0 ) = E 0 .

2
b
d
2 T
Az
V ol(E 0 )
1
Con q 0 = q
; A0 = 2
A
b b , donde b =
,y
exp
d+1
d 1
d+1
V ol(E)
2d
z T Az

k
V ol(Ek )
exp
(E0 := Elipsoide inicial).
Corolario 1. La kesima elipsoide Ek encontrada por el metodo satisface
V ol(E0 )
2d

d
k
r
Notar que V ol(E0 ) = (Rd ). Luego, si queremos que V ol(Ek ) rd , basta tomar k tal que exp
=
d
2d
R

k
R
R
d ln
, luego basta k d2 ln
.
2d
r
r

R
iteraciones.
En otras palabras, el metodo toma O d2 ln
r
Observaci
on. En realidad, uno calcula
aproximaciones de las elipsoides mnimas, el problema es la irracionalidad del
metodo exacto, ya que al calcular b, z T Az puede ser irracional.
3.
M
etodo de la elipsoide para problemas de Optimizaci
on
Dado que el metodo original es s

olo para la factibilidad, veremos dos tecnicas para problemas de optimizaci
on.
3.1.
Primera t
ecnica.
Tenemos el problema de encontrar max{wT x : x K} donde K es dado por el oraculo de separacion y satisface las
hip
otesis.
2

aticas
Si sabemos adem
as que a wT x b, x K.
Figura 3: Nuestra busqueda sube una linea de nivel hasta dar con el otimo.
Haciendo b
usqueda binaria de a0 en [a, b] se puede encontrar un punto tan cercano al optimo como queramos. Los problemas
de esta tecnica son: la irracionalidad del
optimo y que para llegar al verdadero optimo, debemos llegar a K {a wT x},
que tiene volumen 0.
3.2.
Segunda t
ecnica.
Esta tecnica es especfica para programas lineales.

Toda soluci
on
optima del primal tiene una soluci
on dual asociada, de la forma
m
ax cT x
sa. Ax b
x0
mn bT y
= sa. AT y c
y0
Cambiamos al problema de factibilidad:

K = {(x, y) : Ax b, x 0, AT y c, y 0, cT x = bT y}
Los optimos del problema lineal est
an en el convexo K, pero K (normalmente) no tiene volumen, luego definimos:
K = {(x, y) : Ax b, x 0, AT y c, y 0, cT x bT y + }
Se buscan iterativamente soluciones (x , y ) K , hasta tener la presicion deseada.
Caso Particular. Optimizaci
on en poliedros {0, 1}.
Estos poliedros son aquellos cuyos vertices tienen coordenadas en {0, 1}d .
Ejemplo. Dado G grafo bipartito, definimos PMatching (G) = {x RE : x((v)) 1, x 0} = conv{M : M matching}
Todos los vertices viven en {0, 1}|E| .
Sea P poltopo con vertices en {0, 1}d de dimension completa (no todos los vertices estan en el mismo plano).
P = conv(S), con S {0, 1}d . Sea w Zd funci
on de pesos.
Teorema 1. Podemos resolver mn{wT x : x P } en O(d3 log(d||w|| )) iteraciones y llamadas a un or
aculo para P .
Del teorema anterior surgen un par de preguntas; Cual es la factibilidad de P ?,Como comprbar si P 6= ?
Necesitamos:
3

aticas
1. Bola que contenga a P :

1
1
d
P B , ...,
;
2
2
2
| {z }
dveces
2. Volumen mnimo: Si P 6= tiene dimensi

on completa, v0 , v1 , ..., vd S afnmente independientes (no todos en
elmismo hiperplano, i.e.{(vi v0 )}di=1 son l.i) tal que conv({v0 , ..., vd }) P
1
1
1 Qd
2
vol(conv{(v0 , ..., vd )}) = V ol(Paraleleppedo generado por (vi v0 )di=1 ) =
i=1,i>j ||vi vj ||2
d!
d!
d!

d/2
R
Luego, se puede revisar factibilidad en P en O d2 log
= O d2 log q = O(d2 log(d d d!)) = O(d2 log(d)).
r
d 1
d!
1
Para optimizar, definamos Pk = P {w x k + }, con k Z.
2
Para ver la factibilidad de Pk ; necesitamos cota inferior para el volumen de todas maneras. Si Pk 6= , entonces contiene
al menos un vertice de coordenadas enteras en S, llamemoslo v0 .
Sean v1 , ..., vd S tal que v0 , ..., vd son afnmente independientes.
T
Definamos:
(
vi
ui =
v0 + (vi v0 )
si vi Pk
donde =
si vi
/ Pk
1
4||w|| d
A continuaci
on un dibujo que ilustra la construccion que hemos hecho
Veamos que ui Pk :
Notar que si vi Pk ui Pk
Por otro lado, si ui
/ Pk , entonces wT ui > k + 1/2
1
1
wT ui = wT v0 + wT (vi v0 ) k +
2||w|| d k +
4||w|| d
2
ui Pk
Observaci
on. Las coordenadas de w est
an en (||w|| ,||w|| ); y las de (vi v0 ) est
an en {1,1}

d
1
1
Luego, V ol(Pk ) V ol(conv(u0 , ..., ud )) V ol(con(v0 , ..., vd ))d =
.
d! 4||w|| d
Por lo tanto, revisar factibilidad en Pk toma:
d
2
O d2 log q
d
1
d!
4||w|| d = O(d2 log(||w|| d))

aticas

Profesor: Jose Soto
Escriba(s): Juan Pablo Donoso, Valentina Toro y Yasser Nanjari.
Fecha: 10 de Noviembre 2014 .
C
atedra 25
1.
Recuerdo
1.1.
Factibilidad de un convexo K Rd
Cuando debamos determinar si K = o bien si devolver x K, el metodo del elipsoide nos permitira decidir si este
conjunto K es un conjunto factible. De la clase anterior sabemos que el metodo puede realizar esto en

R
VExt (K)
2
= O d log
O d log
VInt (K)
r
iteraciones y llamadas al or
aculo de separaci
on para K, donde
VExt (K): Volumen de una bola/elipsoide que cubre a K.
VInt (K): , tal que K 6= V (K) .
R, r : Radios de las bolas que contienen o estan contenidas en K.
Lo antes mencionado se estaba viendo para resolver el problema que se enunciara a continuacion.
1.2.
Optimizaci
on sobre envolturas convexas de v
ertices del cubo
d
Problema: Dados S {0, 1} , P = conv(S), un oraculo para P (P es de dimension completa o vaco) y w Rd

funci
on de pesos (en general trabajamos con w Zd ); se busca obtener
mn {wt x : x P }.
Vimos que se tena la factibilidad en P . En efecto, esto se tiene ya que
R=
d
2 .
VInt (P )
1
d! .
Por lo tanto, bastan O(d log(d1/2 d!)) = O(d2 log(d)) iteraciones para encontrar x P .
Observaci
on: El d! aparece por lo siguiente:
Qd = {x Rd : 0 xi 1, i [d]}
d = {x Qd : 0 x (1) . . . x(d) 1},
X
V (Qd ) =
V (dP i )
Sd
V (d ) =
1
V (Qd )
d!
Tambien definimos para k Z
1
Pk = {x P : wt x k + }.
2
La clase anterior probamos que se puede resolver factibilidad en Pk . En efecto,
1
con Sd

aticas
R=
d
2
VInt (K)
1
d!kwk 2d
Luego, podemos decidir factibilidad en Pk utilizando

O(d log(d2 d! dkwk )) = O(d2 log(dkwk ))
iteraciones y llamados al or
aculo.
2.
B
usqueda del mnimo
Se realizar
an los siguientes pasos para encontrar
k = mn{wt x : x P }
(1) Encontrar xf P factible = k kmax = dwt xf e.

(2) k kmn = dkwk . (Observaci
on: Esto es cierto, puesto que el mnimo wt x se alcanza en x S.)
(3) Se realiza b
usqueda binaria para hallar el k [kmn , kmax ]. As, se puede encontrar k usando
O(log(kmax kmin )) = O(log(dkwk ))
test de factibilidad en Pk .
Finalmente, esto da en total
O(d2 log2 (dkwk ))
llamadas al or
aculo para P . As, sabemos cu
anto vale k .
Ya establecido el valor de k , nace la siguiente interrogante: C
omo calcular un punto x P que alcance dicho
valor?
Se define
P 0 = {x P : wt x = k }
y luego se despeja una variable en funci
on de las demas para considerar P 0 como poltopo en d 1 dimensiones. Si P 0 no
es de dimensi
on completa, entonces se puede despejar una variable en funcion de las demas y repetir hasta llegar a un P
de dimensi
on d0 < d completa.
Cualquier punto de P es soluci
on
optima y se puede encontrar dicho punto con el metodo elipsoidal. Mas a
un, podemos
devolver un vertice del problema original. Para realizar esto, tenemos dos formas posibles:
(1) Iterar el metodo del elipsoide para mn {w2t x : x P }, donde w2 es una funcion de peso arbitraria.
(2) Invertir una matriz dada por d0 desigualdades l.i de P .
Gracias a esto, se puede concluir el siguiente teorema:
Teorema 1. Dado P poltopo con or
aculo de separaci
on, P = conv(S), S {0, 1}d y w Zd , podemos encontrar vertice
optimo de
mn {wt x : x P } = mn{wt x : x S}
usando O(d3 log(dkwk )) llamadas al or
aculo.

aticas
3.
Teorema de Khachiyan
Teorema 2 (Khachiyan). El problema

(P )
ct x
m
ax
Ax b
s.a
A Qmd
b Qm
x Qd
Se puede resolver en tiempo debilmente polinomial, es decir, polinomial en m, d y log(U ), donde
U = m
ax{kAk , kck , kbk }
Demostraci
on: (Esquema)
(1) El problema se reduce a mostrar factibilidad de
P = {(x, y) : Ax b, At y = x, y 0, ct x = bt y}.
Luego, basta dedicarnos a probar factibilidad en Q = {x : Ax b}, con A y b distintos a los anteriores, ya que si
somos capaces de crear un algoritmo polinomial para este problema, lo tenemos para el anterior.
(2) Nos reducimos ahora al caso en que Q 6= , ya que entonces Q tiene al menos un vertice. Esto se hace diagonalizando
la matriz A, es decir,
A [A0 : 0].
A0 x0 b0 tiene vertices si y s
olo si Q 6= .
(3) Se acota el tama
no de los vertices: Todo vertice x de Ax b es solucion de Cx = p para cierta submatriz C de A y
subvector p de b, con C invertible.
Lema 1. Sea x = C 1 p. Entonces x es un punto racional con numerador y denominador acotados por (d U )d .
Demostraci
on: (Usando la f
ormula de Cramer)
xj =
det(C; P ; j)
det(C)
donde (C; p; j) es la matriz obtenida al reemplazar la j-esima columna de C por el vector p.

X

d0
Y

|det(X)| =
sgn()
xi,(i)
Sd0

i=1
0
d0 ! kXkd ,
donde X es de dimensi
on d0 . En nuestro caso, tanto el numerador como el denominador de xj es un entero menor o
d d
d
igual a d U = (dU ) .
Luego, todos los vertices de Q est
an en la bola
Ba (0, (dU )2d ) B(0, d(dU )2d )

As, para partir el metodo del elipsoide usamos B(0,
d(dU )d ) (si hay un vertice, esta en esta bola).

aticas
(4) Para evitar el caso Q = V (Q) = 0 trabajamos con

QExp = {x Rd : Ax b + 1},
donde ser
a fijado despues.
Lema 2. Para suficientemente peque
no:
Q = QExp =
Demostraci
on:
(=) Como Q QExp , esta implicancia es obvia.
(=) Usando Farkas, como Q = {Ax b} = , tenemos que y 0 tal que At y = 0, bt y = 1.
Si QExp 6= , tiene un punto x QExp . Vemos entonces que
0 = y t (Ax ) y t (b + 1) = 1 + y t 1 1 +
1
1
= < 0
2
2
donde la pen
ultima desigualdad se obtiene eligiendo adecuado (*). As, se obtiene una contradicci
on y se
concluye que QExp = .
(*) Para determinar , podemos suponer que y es vertice del sistema. Entonces, por el Lema 1,
kyk (dU )2d
= |y t 1| d(dU )2d
Finalmente, basta tomar
1
2d(dU )2d
para concluir.
Para terminar la demostraci

on de Kachiyan, podemos revisar la factibildad de QExp usando
!!
( d(dU )2d )d
O d log
VInt (QExp )
Notemos que si Q 6= , entonces x Q.
=
d
Y
[xj , xj + ] QExp .
j=1
0
En efecto, si x est
a en dicho intervalo,
Ax0 = Ax + A(x x0 ) b + (dU ) 1
Tomando =
dU
1
,
2d(dU )2d+1
concluimos que x0 QExp . Luego,

V (QExp ) d =
2d
dd
1
.
(dU )d(2d+1)
Juntando todo esto, necesitamos

2
2
O d log (dU )O(d ) (2dU )O(d )
= O d3 log(dU )
llamados a el or
aculo de Q.
Como este or
aculo es polinomial, obtenemos un algoritmo polinomial.
Observaci
on: En realidad encuentra un punto en QExp . Para encontrar un punto de Q existen tecnicas de redondeo
que no veremos.
4

aticas
3.1.
Aplicaci
on del teorema
Problemas de flujo de costo mnimo o con demandas, costos y capacidades.

Sean
G = (V, E) grafo dirigido
b(v) la demanda de flujo de v V (si es negativo, es oferta)
c(e) el costo de un arco e E
Capacidades de los arcos en el intervalo [l(e), u(e)]
El problema de envo de flujo de costo mnimo es
mn
{ct : x RE ; x( (v)) x( + (v)) = b(v) para todo v V ; l(e) x(e) u(e) para todo e E.}
y es soluble con Khachiyan, pero es lento (lo escrito en rojo son restricciones que se pueden testera en tiempo polinomial).

aticas
Profesor: Jose Soto
Escribas: Manuel C
aceres, Felipe Garrido, Camila Romero,
Sebasti
an Tapia.
C
atedra 26
1.
Recuerdo
En la clase pasada se mencion

o que se poda resolver el problema de Matching Perfecto en grafos generales, escribiendo este como un problema de programacion lineal y prosiguiendo con el Metodo de la elipsoide 1 .
Para esto se definieron los siguientes conjuntos :
= conv(M : M es M atching).
(1)
PM atching
(2)
Q(G) = { x RE : x((v)) = 1, v V,
perf ecto (G)
x((S)) 1, S V : |S| impar,

x 0 }.
2.
Teorema de Edmonds
Teorema 1 (Teorema de Edmonds).

P (G) = Q(G)
Demostraci
on. Inducci
on en n + m = |E| + |V | :
Caso base: (n + m = 1) Se tiene que n = 1 y m = 0, por lo tanto P (G) = Q(G) = .
Caso general: (n + m 2)
En este caso podemos suponer adem
as que n es par, pues si no lo fuese, no existira un Matching perfecto
en G, por lo que P = y podramos tomar S = V tal que x((V )) = 0, por lo que Q sera vaco tambien.
La inclusi
on P Q es directa pues claramente un vertice de P cumple las condiciones para estar en Q, por
lo que nos dedicaremos a demostrar la otra inclusion (Q P ).
Sea x un vertice (punto extremo) de Q y dividamos la demostracion en los siguientes casos :
1) Existe e tal que xe = 0.
En este caso, se tiene que x |Ee Q(G e) = P (G e) por hipotesis inductiva, es decir, x |Ee
es combinaci
on convexa de indicatrices de matchings perfectos en G e, y por lo tanto en G. Luego,
x P (G).
2) Existe e con xe = 1,
An
alogamente a la parte anterior, tomando Gvu, (donde e = uv) se puede demostrar que x P (G).
3) Para todo e E, xe (0, 1),
Como x ((v)) = 1, se cumple que v V : dG (v) 2 2 . Dividamos ahora nuevamente en casos :
1 Teniendo
2 Para
as un algoritmo polinomial para el problema

que la suma de los del corte de 1, tienen que haber al menos 2 aristas.

aticas
i)
Para todo v V : dG (v) = 2.

Sabemos que G sera uni
on disjunta de ciclos y ademas, el n
umero de vertices de cada ciclo debe
ser par3 .
Sea C un ciclo de estos,
se cumple entonces que (0, 1), tal que :

para las aristas pares,
xe =
1 para las aristas impares
pues x ((v)) = 1, en particular v C.
Definimos ahora :
x+ : el vector obtenido al sumar a las aristas pares, y restar a las aristas impares
x : el vector obtenido al restar a las aristas pares, y sumar a las aristas impares
eligiendo suficientemente peque
no como para que x+ , x Q.
Notando que x = 12 (x+ + x ), contradecimos que x es punto extremo de Q.
ii)
Existe v V : dG 3. Luego,
|E| =
1X
d(v) > |V |
2
vV
Ahora, como sabemos x Q es extremo y Q tiene dimension |E|, entonces se tendran |E| desigualdades ajustadas l.i. que definen a x
Por otro lado, se tiene xe > 0 : e E, y hay solo |V | < |E| condiciones del tipo x((v)) = 1,
por lo que se concluye que al menos una de las condiciones x ((S)) 1 esta activa y es l.i.
con respecto a las anteriores, es decir, existe S con |S| impar y tal que x ((S)) = 1, |S| 6= 15 y
|S| =
6 n 16 .
Tenemos
no lo fuese, no se cumplira la condicion x ((C)) 1, con |C| impar
pues v V v d(v) 2 y d(v ) 3
5 si no, esta desigualdad se deducir
a de x ((v)), con S = {v} y no sera l.i.
6 si no, esta desigualdad se deducir
a de x ((S)) = x ((v)), con v
/ S y no sera l.i.
3 Si
4 Esto

aticas
donde las lneas rojas corresponden al corte de V y V \ S.

como los obtenidos al fusionar las aristas de S
Sea S = V \S. Definimos los multigrafos: G/S y G/S,
y S en los vertices vS y vS respectivamente, y eliminando los loops generados en vS y vS al fusionar.

Grafo E \ S
Grafo E \ S
Definimos adem
as :
0
E(G/S)
x R
,
x00 RE(G/S) ,
como las restricciones de x a las aristas que no fueron borradas.
Observaci
on 1. Notar que x0 Q(G/S), pues :
x0 0

x ((v)) = 1
0
x (G/S (v)) =
x ((S)) = 1
T : |T | es impar x0 (G/S (T )) = x (G (Texpandido ))
y lo mismo para x00 , es decir, x00 Q(G/S)

3
v V \ S
si v = vS

aticas
Como G/S y G/S tienen menos vertices y aristas que G, usamos induccion y obtenemos que
x00 P (G/S)
X
00
x00 =
M 00 M
x0 P (G/S)
X
0
x0 =
M 0 M
M0
M 00
, es decir, combinaci
on convexa de indicatrices de matchings perfectos en G/S y G/S respectivamente.
Recordando que x es un vertice de Q, el cual es un poltopo racional.
x tiene coordenadas racionales
x0 y x00 tienen coordenadas racionales7
Abusando un poco de notaci
on, podemos escribir:8
x0 =
N
1 X Mi0
N i=1
x00 =
N
1 X Mi00
N i=1
M
as a
un, como 1 = x0 |(S) = x00 |(S) = x |(S) , podemos crear los matchings de modo que i, las
u
nicas aristas de Mi0 y Mi00 que cruzan el corte son las mismas.
Haciendo esto, podemos definir Mi = Mi0 Mi00 , matching perfecto de G, luego
x =
N
1 X Mi
,
N i=1
y as x P .
Observaci
on 2. Como consecuencia del resultado anterior, si tenemos un or
aculo de separaci
on polinomial
para:
PMatching perfecto = {x RE | x(S(v))) = 1, x((S)) 1, x 0, S V impar},
podemos usar el metodo elipsoidal para encontrar un vertice
optimo del PL:
max{wt x; x M : M matching perf ecto}.
A modo general, muchos problemas de optimizacion combinatorial se pueden describir definiendo los
siguientes 3 objetos:
1) Conjunto de instancias donde nuestro problema cobra sentido, el cual se puede denotar por I. Por
ejemplo durante el curso hemos usado I = {Grafos}, entre otros.
2) Conjunto de objetos factibles de interes, esto es, para cada G I considerar un conjunto F(G) en el
cual resolveremos el problema. Por ejemplo si I son grafos, podemos pensar en F(G) como el conjunto
de matchings perfectos o el conjunto de bosques generadores, entre otro.
7 De
hecho los M 0 , M 00 tambi

en
repeticiones en los Mi0 y en los Mi00
8 Permitiendo

aticas
3) Funci
on de peso G : F(G) Q, en el cual se basara la optimizacion del problema. Por ejemplo dada
una instancia G en I, encontrar el objeto factible que maximiza el peso.
Una estrategia para resolver estos tipos de problemas cuando G es una funcion linealde los elementos
de cada objeto factible es escribir el problema como:
Dado G:
wT x | x = F , F F(G),
es lo mismo que resolver
m
ax{wT x | x conv(F | F F(G))},
dado esto, si adem
as podemos describir de manera eficiente el conjunto conv(F | F F(G)) mediante un
or
aculo de separaci
on polinomial, podramos resolver usando el metodo de la elipsoide.
3.
Clases de complejidad para problemas de Optimizaci

on Combinatorial.
Definiremos de manera informal dos clases de problemas.
1) Clase P: Problemas tales que para todas las instancias G de I, podemos determinar en tiempo polinomial
si F F(G) con (F ) , donde Q esta dado.
Altenativamente podemos resolver m
ax wT x | x conv(F | F F(G)) en tiempo polinomial.
2) Clase N P: Problemas tales que dado una instancia G y Q, F arbitrario (no necesariamente factible),
se puede verificar en tiempo polinomial si F F(G), y en caso de estarlo, si (F ) .
A modo de resumen, la clase P son los problemas polinomialmente resolubles, y la clase N P son los
polinomialmente verificables.
Observaci
on 3. El nombre P y N P vienen de problemas deterministas y problemas no deterministas.
Adem
as, es f
acil ver que (P ) N P
Gran problema abierto: Es P =
6 N P o P = N P.
3.1.
Reducci
on de Cook/Turing de problemas
Definici
on 1. Dado dos problemas A y B, decimos que A se reduce a B, o bien, A TP B si podemos resolver
A en tiempo polinomial usando la subrutina que resuelve a B. En particular, si B P entonces A P.
Observaci
on 4. En la definici
on anterior, la desigualdad se escribe TP , donde la T proviene de que es la
comparaci
on de Turing.
Definici
on 2. N P-difcil: Un problema Q es N P-difcil, si problema X N P, X TP Q, si ahora Q N P
se dir
a N P-completo.
4.
Pr
oxima Clase
La siguiente clase veremos el siguiente teorema.
Teorema 2 (Cook-Levin). Existe un problema N P-difcil, que es N P-completo. M

as a
un, es el problema
denominado SAT, que refiere a determinar si una funci
on booleana (x) es satisfactible.o no.
Ejemplo de funci
on SAT: : {V, F }3 {V, F }, definida por (x) = (x1 x2 ) (x1 x3 ). Es facil notar
que es satisfactible, dado que ((V, V, V )) = V .
5

aticas
Profesor: Jose Soto
Escriba(s): Mauricio Campos, Juan Marshall, Martn Ros, Piero Zanocco.
Fecha: 17 de Noviembre de 2014.
C
atedra 27
1.
Recuerdo
Est
abamos estudiando las clases de problemas de optimizacion combinatorial. Entre estas, definimos las siguientes:
Definici
on 1 (Clase P ). Son aquellos problemas de maximizacion, donde encontrar solucion factible de peso al menos
un valor dado es polinomial.
Definici
on 2 (Clase N P ). Son aquellos problemas de maximizacion, donde verificar si un conjunto X es soluci
on factible
de peso al menos un valor dado es polinomial.
A partir de estas definiciones, nos preguntamos si un problema de optimizacion, que puede verificarse en tiempo
polinomial, admite una soluci
on factible que pueda ser encontrada en tiempo polinomial. Es decir, es N P = P ?.
Para abordar esta pregunta, requerimos definir algunos conceptos:
Definici
on 3 (Reducci
on (Turing)). Se dice que un problema A se reduce a un problema B,
A TP B,
si podemos resolver A en tiempo polinomial usando como rutina un oraculo que resuelva B.
Definici
on 4 (Clase N P -difcil). Un problema Q se dice N P -difcil si para todo problema X de N P se tiene que:
X TP Q
Definici
on 5 (Clase N P -completo). Un problema Q se dice N P -completo si es N P -difcil y esta en N P .
Nos preguntamos entonces sobre la existencia de problemas N P -completos. En 1971, Stephen Cook resuelve este
problema mediante el siguiente resultado:
Teorema 1 (Cook-Levin). SAT es N P -completo, donde:
SAT: Dado (x) booleana, determinar si existe x tal que (x).
2.
Problemas N P -completos
Obs 1. Karp (1971) di

o una lista de 21 problemas N P -completos. Entre ellos se encuentran los siguientes:
Clique (subgrafo en que cada vertice est
a conectado a cada otro vertice del grafo) de tama
no maximo.
Conjunto independiente de tama
no m
aximo.
Corte de cardinalidad m
axima.
Encontrar cubrimiento por vertices en grafos no bipartitos.
Existencia de un ciclo Hamiltoniano (ciclo que pasa por todos los vertices del grafo).
C
omo probamos que un problema Q es N P -completo?
1. Q N P
2. Encontrar R N P -difcil tal que R TP Q
1

aticas
Ejemplo. Probar que el problema de encontrar un s t camino de largo maximo en un grafo G, dada una funci
on de
largos l : E R, s, t V (G) es N P -completo.
1. s t Camino M
aximo est
a en N P . Dado un conjunto F E, verificar si F es camino es facil, y calcular su largo
tambien.
2. Ciclo Hamiltoniano TP s t Camino M
aximo. Dado G grafo, para verificar si G tiene un ciclo Hamiltoniano
repetimos lo siguiente: Para cada arista e = uv verificar si existe u v camino de largo n 1. Notemos que
Existe alguno de estos caminos G tiene ciclo Hamiltoniano.
Problema Controlable. Encontrar un s t camino de tama
no maximo se reduce al problema encontrar un camino
de tama
no m
aximo.
Que hacemos si nos enfrentamos a problemas N P -difciles?
Heursticas.
Algoritmos de aproximaci
on.
Definici
on 6 (Algoritmos de aproximaci
on). Sea Q un problema de maximizacion:
m
ax{w(S) : S F}.
Un algoritmo polinomial que devuelve un conjunto S F:
w(OP T )
,
donde OP T es el
optimo para Q, se llama algoritmo de aproximacion.
w(S)
An
alogamente, si Q es de minimizaci
on, la idea es encontrar S tal que:
w(S) w(OP T )
En ambos casos, 1 se conoce como el factor de aproximaci
on ( puede depender de los par
ametros del
problema).
3.
El problema del vendedor viajero (TSP).

Antes de explicitar el problema, veamos dos definiciones sobre grafos que ayudan a comprenderlo mejor:
Definici
on 7 (Tour/Ciclo Hamiltoniano). Sea G = G(V, E) un grafo. Un Tour/Ciclo Hamiltoniano es un paseo/ciclo en
G que visita cada vertice al menos una vez.
Definici
on 8 (Paseo Euleriano). Sea G = G(V, E) un grafo. Un paseo Euleriano es un paseo en G que recorre cada arista
exactamente una vez.
Ahora veamos el problema:
Definici
on 9 (Problema del vendedor viajero). Sea G = G(V, E) un grafo, l : E 7 R funcion de largo. El problema del
vendedor viajero consiste en encontrar un ciclo Hamiltoniano de largo mnimo.
Obs 2. Una variante del problema anterior es considerar la b
usqueda de un tour en vez de un ciclo. De hecho ambos
problemas coinciden cuando consideramos l, la funcion de largo, metrica i.e. satisface la desigualdad triangular, y que el
grafo G sea completo.
El problema de encontrar un ciclo Hamiltoniano de largo mnimo en un grafo completo es NP-difcil. De hecho tenemos
lo siguiente:
2

aticas
Teorema 2 (Ciclo Hamiltoniano TSP). El problema de encontrar un ciclo hamiltoniano en un grafo se reduce al TSP.
Veamos un dibujo para entender la idea de la demostracion:
C
A
Figura 1: Tour: ABCDBEA, Ciclo: ACDBEA

Demostraci
on. Sea G grafo y H el grafo obtenido al completarlo. Queremos determinar si G tiene un ciclo Hamiltoniano.
Ponemos en H la siguiente funci
on de pesos:

w(e) =
e E(G)
e
/ E(G)
0
1
Utilizando el un algoritmo para TSP podemos encontrar un ciclo Hamiltoniano C de H de peso mnimo. Ahora es f
acil
decidir:
Si w(C) = 0, entonces G tiene un ciclo Hamiltoniano.
Si w(C) 6= 0, entonces G no tiene un ciclo Hamiltoniano.
El siguiente lema demuestra la equivalencia dicha en la Obs 1.

Lema 1. Sea G grafo completo y l : E 7 R metrica. Si W es un tour, entonces existe C ciclo Hamiltoniano tal que
l(C) l(W ).
Demostraci
on. Si W es un tour lo describimos por W = V1 V2 ...VN +1 donde VN +1 = V1 . Ahora nos basta encontrar el ciclo
obtenido al borrar todas las apariciones de cada vertice salvo la primera, en la escritura de W . Este queda C = S1 S2 ...Sn ,
mientras que W queda descrito ahora como W = W1 W2 ...Wn , donde Wi es un Si Si+1 paseo. Por desigualdad triangular
se concluye.
Veamos un resultado cl
asico que no demostraremos:
Lema 2. Sea G un (multi)grafo conexo tal que todo vertice tiene grado par. Entonces G posee un paseo Euleriano que
se encuentra en tiempo polinomial.
Tambien se tiene la siguiente versi
on para grafos dirigidos:
Sea G un (multi)digrafo fuertemente conexo tal que todo vertice tiene igual n
umero de arcos entrantes que salientes.
Entonces G posee un paseo Euleriano dirigido que se encuentra en tiempo polinomial.

aticas
C
B
D
F
Figura 2: Paseo Euleriano: ABCDBFEAEDFA

A continuaci
on se exponen dos algoritmos de aproximacion para TSP metrico:
Algoritmo 1: Primer algoritmo de aproximacion TSP metrico
Sea G grafo completo, l metrica
Dado T
arbol generador de G de peso mnimo
Encontrar paseo euleriano P del multigrafo 2T (cada arista aparece dos veces)
A partir de P , hacer atajos (Usando Lema 1 pues P es paseo hamiltoniano en particular) y encontrar ciclo
hamiltoniano C
El siguente paso es duplicar cada arista,de modo que una es antiparalela a la

otra, mencionamos que este digrafo en
un paseo Euleriano donde se pasa 2 veces por cada vertice
Aca vemos un arbol generador

aticas
En esta etapa usamos el Lema 1 para

hacer atajos y as encontrar un ciclo Hamiltoniano
El ciclo Hamiltoniano resultante
Observamos que el ciclo obtenido usando este algoritmo satisface lo siguiente:

l(C) 6 l(P ) 6 2l(T ) 6 2l(OP T )
En donde OP T es el
optimo de TSP metrico.
Un segundo algoritmo fue desarrollado por Nicos Cristofedes, profesor del Imperial College de Londres, en 1976. Actualmente es el mejor algoritmo de aproximaci
on que existe. La principal mejora que introduce el algoritmo es que encuentra
un subgrafo euleriano de G sin duplicar todas las aristas de T, usando vertices que ya tienen grado par y que, por lo tanto,
no se necesitan duplicar.
Algoritmo 1: Segundo algoritmo de aproximacion TSP metrico
Sea G grafo completo, l metrica
Dado T
arbol generador de G de peso mnimo
Sea I el conjunto de vertices de grado impar de T. (Notar que |I| es par puesto que la suma de los grados de un
vertice en G es par)
Sea M matching perfecto en (I, E[I]) de peso (largo) mnimo
T M es un multigrafo euleriano
Encontrar P paseo euleriano de T M
A partir de P , hacer atajos (Usando Lema 1 pues P es paseo hamiltoniano en particular) y encontrar ciclo
hamiltoniano C
Se observa que el ciclo obtenido satisface
l(C) 6 l(P ) 6 l(T ) + l(M )

aticas
Figura 5: El ciclo que vemos aca representa el

optimo, ahora OP TI sera el ciclo obtenido(haciendo atajos) borrando los
vertices fuera de I en OPT
Estimemos l(M ): sea OP TI el ciclo obtenido borrando los vertices de OP T que estan fuera de I (haciendo atajos como
en el Lema 1) entonces:
l(OP T ) > l(OP TI ) = l(OP TIpar ) + l(OP T Impar )
Donde OP TIpar corresponde a las aristas pares y OP T Impar corresponde a las aristas impares considerando alguna numeraci
on de las aristas en OP TI . Ambos son matchings perfectos de I pues OP TI contiene todos los vertices de I.
De estas dos estimaciones se concluye que
3
l(OP T )
2
Queda propuesto demostrar que el algoritmo gloton es una 2-aproximacion de encontrar un matching de cardinalidad
m
axima.
l(C) 6

aticas

Profesor: Jose Soto
Escriba(s): Juan Granier, Ian Letter, Alberto Rojas y Jose Soto.
C
atedra 28
1.
T
ecnicas para dise
nar/analizar algoritmos de aproximaci
on
En esta secci
on se ver
a la resoluci
on de algunos problemas de alta complejidad utilizando algoritmos que permiten
aproximar por una constante. Antes de ello se enuncian algunos ejemplos.
Ejemplo 1. TSP: Problema del vendedor viajero
En este caso, utilizando
arboles generadores y matchings se puede obtener una
3
2
aproximaci
on.
Observaci
on 1. No es trivial obtener aproximaciones en base a constantes para problemas NP-Completos. Muchas veces
queda en base a los datos del problema.
M
as ejemplos:
Glot
on (K-aproximaci
on para intersecci
on de K matroides)
Programaci
on Din
amica (Problema de la mochila)
1.1.
Problema 1: Programaci
on Lineal
Vertex-cover (cubrimiento por v

ertices de peso mnimo)
Dado G = (V, E), w : V R+ .
Encontrar C V cubrimiento de peso mnimo.
Observaci
on 2. Vertex-cover es NP-Completo, para grafos generales. (En el caso bipartito es polinomial; como ya fue
visto).
Soluci
on. En primer lugar lo modelamos como un problema entero.
Programa Entero:
mn
xv wv
vV
s.a.
xi + xj 1
e = ij V
xv {0, 1}
v V
Se relaja el programa entero, obteniendo un programa lineal:

X
mn
xv w v
vV
s.a.
xi + xj 1
xv 0
e = ij E
v E
Observaci
on 3. Se puede eliminar la restricci
on de 1 ya que la funci
on de peso est
a definida en R+ . Luego, si una
variable es mayor que 1, el bajarla a 1 mejora la soluci
on.
Notar que es solo valido para funcion de peso no negativo.
Sea x una soluci
on
optima del PL, que en general no es integral.
Algoritmo 1: Redondeo determinista
return C = {v : xv 12 }
Probaremos algunos resultados respecto al conjunto obtenido.
1

aticas
Lema 1. El conjunto devuelto C es cubrimiento.

Demostraci
on. Sea e = ij en E. Sabemos que xi + xj 1. Luego k {i, j} : xk 21 . Por lo tanto, k C, y entonces
e est
a cubierto.
Lema 2. El peso de C satisface:
X
X
X
w(C) =
wv =
wv 1{xv 12 }
wv xv 1{xv 12 } = 2w(P L) 2w(OP T )
vC
vV
vV
Antes de demostrar este lema, se enunciar

a un lema que nos resultara u
til, ademas de servir en contextos m
as generales.
Lema 3. Si x es punto extremo del poltopo que define el PL, entonces: x {0, 21 , 1}
Demostraci
on. Se definen los conjuntos:
C + = {v V : xv (0, 1/2)}
C = {v V : xv (1/2, 1)}
Se probar
a que C + = C = concluyendo el resultado buscado. Para ello, como sabemos que C + C = , supongamos
+
que C C 6= , se define:

xv : v C
:
v
x
v
2
=
x 1 : v C +
v 2
1 xv : v C +
Luego, se toman los siguientes elementos en V :
si v V \ (C + C )
x v
yv+ = xv + si v C

xv si v C +
si v V \ (C + C )
xv
yv = xv si v C

xv + si v C +
Notamos que y +, y son puntos factibles. Sea e = ij E. Si i o j estan en C , luego, usando que xi + yj 1, el
otro est
a en C + o bien tiene valor 1. Por otro lado, si ambos ndices estan en C + , eso implica que
yi+ + yj+ (xi + ) + (xj ) 1
| {z } | {z }
12
12
Esto nos permite deducir en ambos casos que yi+ + yj xi + xj 1.

De lo anterior vemos que x =
C = .
y + +y
2
no es extremo, lo que es una contradiccion. Por lo tanto probamos que C + =
En conclusi
on, el algoritmo devuelve un cubrimiento de peso a lo mas 2 veces el del optimo.
Observaci
on 4. Esto funciona tambien para restricciones del tipo xi + xj +...+xl 1, la cual da una n-aproximaci
on,
donde n es el n
umero de sumandos de la restricci
on.

aticas
1.2.
Problema 2: Set-cover
Sean C = (c1 ,..., cm ) una familia de conjuntos (subconjuntos de V)

Sea adem
as w : C 7 R+ (funci
on de peso para cada subconjunto)
Encontrar una subfamilia de C, digamos A, tal que su union cubra todo V , y que ademas cumpla con ser de peso
mnimo.
Observaci
on 5. Esto generaliza el problema de Vertex-cover.
Soluci
on. Repitiendo la idea anterior primero lo escribimos como un Programa Entero:
X
mn
xc w c
cC
s.a.
xc 1
v V
c: vC
xc {0, 1}
c C
En primer lugar intentamos utilizando la tecnica del Redondeo Aleatorio:

Algoritmo 2: Redondeo aleatorio
x soluci
on
optima del PL obtenido de relajar el Programa Entero. (xc [0, 1] c)
A=
for i [k]
for c C
Agregar c a A con probabilidad xc
return A
Ahora s
olo falta analizar este algoritmo, tanto en factibilidad como optimalidad. Haremos lo segundo pregunt
andonos;
Cu
al es el pesoP
esperado de A?
Sea w(A) = cA w(c) variable aleatoria, entonces calculamos su esperanza:
X
E(w(A)) =
w(c) P(c A)
cC
w(c)xc
cC
k w(OP T )
Es decir; podemos controlar el peso
optimo de nuestro algoritmo si cambiamos k. Si bien A es aleatorio, falta ver que
con alta probabilidad A es factible para k adecuado:
Sea v V : Probabilidad de que v este cubierto por A?
Sean ci tal que v ci . Como x ,
xci 1, se tiene lo siguiente:
P(v no est
a cubierto ) = P(ci no es elegido i)

aticas
Luego:
P(v est
a en A)
= 1 P(v no esta en A)
Y
=1
P(ci no es elegido)
vci
=1
(1 xci )k
vci
exp (xci k)
vci
= 1 exp (k
xci )
vci
1 exp (k)
Donde hemos usado que 1 x ex y que
xci 1.
Ahora, Probabilidad de todos que los vertices esten cubiertos?

[
P(A factible) = P(v
A, v)
AA
1 P(v no cubierto)
X
1
P(v no cubierto)
vV
1 |V | exp (k)
Ahora podemos elegir k de buena manera; por ejemplo k 2log(|V |) y asi:

1
1 |V | exp(k) 1
|V |
Observaci
on 6. Podemos elegir k para obtener aproximaciones de tipo (1 |V1|l ) con l a eleccion; eligiendo k (l +
1) log(|V |). Con esto el peso esperado es (l + 1) log(|V |) OP T . Luego, el factor esperado de aproximaci
on es O(log |V |),
factor que, salvo casos particulares, es lo mejor que se conoce para set-cover.
1.3.
Problema 3: Corte de Peso M

aximo
Dado G = (V, E), w : V 7 R+

Encontrar U V tal que w((U )) sea m
aximo.
Observaci
on 7. Este problema es NP-Difcil.
Soluci
on. De manera similar al problema anterior, se plantea un algoritmo utilizando redondeo aleatorio. Se ver
a que
este algoritmo se puede mejorar trabajando de forma iterativa.
Algoritmo 3:
Elegir U del siguiente modo:
e = ij, P(e este cortada) =
return U
1
2
Al igual que en el caso anterior, el corte obtenido es probablemente una buena aproximacion, para probarlo se calcula
la esperanza de la variable aleatoria:

aticas
E[w((U ))]
we P(e (U ))
eE
1
= w(E)
2
1
w(OP T )
2
Por lo tanto este algoritmo devuelve un corte cuyo peso esperado es mayor o igual a 12 w(OP T )
M
etodo de esperanzas condicionales
Este metodo desaleatoriza la elecci
on del conjunto U , proponiendo un metodo de aproximacion iterativo para el
problema.
Dado un conjunto de vertices {v1 , v2 , . . . , vn } se define la siguiente funcion:
f (x1 , . . . , xn ) = w[(U )]
donde U = {i : xi = 1}.
Se sigue el siguiente procedimiento:
Algoritmo 4:
for i [n]
Elegir si {0, 1} que maximice E[f (s1 , . . . , si1 , si , xi+1 , . . . , xn )] = E[f (x)|x1 = s1 , . . . , xi = si )].
return s
Notar que es posible usando la misma idea, resolver el problema cuando algunos de los vertices ya est
an fijados de
antemano.

Algoritmos Combinatoriales

Cargado por

Copyright:

Formatos disponibles

Algoritmos Combinatoriales

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Algoritmos Combinatoriales

Cargado por

Copyright:

Formatos disponibles

Facultad de Ciencias Fsicas y Matem

MA3705. Algoritmos Combinatoriales. 2014.

Se entiende por Optimizaci

= {(a, b) P 2 | a 6= b} es un matching en P ssi

Ejemplo 2. Considerando que el hotel solamente

donde se define la funci

Facultad de Ciencias Fsicas y Matem

Ejemplo 4 (Problema de Conectividad

Facultad de Ciencias Fsicas y Matem

({a, b} E) : X{a,b} {0, 1}

Figura 1: Representacion de Problema de Matching

Facultad de Ciencias Fsicas y Matem

Antes de comenzar a trabajar se formalizan las estructuras que se manejaran en el curso.

= ({1, . . . , n}, {ij : i < j}) .

El complemento del grafo completo: Kn = ([n], ).

Facultad de Ciencias Fsicas y Matem

Figura 3: El grafo completo K5

Conjuntos notables en un grafo

Paseos, caminos y ciclos

Facultad de Ciencias Fsicas y Matem

Figura 4: Un ciclo de largo 8

Facultad de Ciencias Fsicas y Matem

MA3705. Algoritmos Combinatoriales. 2014.

Figura 1: ({v1 , v2 , v3 , v4 }, {e1 , e2 , e3 , e4 }) es un ciclo.

Facultad de Ciencias Fsicas y Matem

Figura 2: Grafo con tres componentes conexas

Facultad de Ciencias Fsicas y Matem

Por ejemplo, en la figura, F genera e.

Figura 4: En este caso e

Corolario 2. Si G0 G es un subgrafo de G tal que genera G y e pertenece a un ciclo de G0 G0 e genera G.

Facultad de Ciencias Fsicas y Matem

Para analizar la correctitud del algoritmo probaremos:

Facultad de Ciencias Fsicas y Matem

Casos especiales del algoritmo gen

Algoritmo 3: DFS (Depth First Search o B

Facultad de Ciencias Fsicas y Matem

MA3705. Algoritmos Combinatoriales. 2014.

Algoritmo 1: BFS (Breath First Search o B

Algoritmo 2: DFS (Depth First Search o B

Figura 1: Grafo de ejemplo

Facultad de Ciencias Fsicas y Matem

Facultad de Ciencias Fsicas y Matem

Facultad de Ciencias Fsicas y Matem

Algoritmo 4: Algoritmo de Prim (Prim 1957 - Jarnk 1930)

E 0 (U ) = , pero e es de peso mnimo en (U )

Facultad de Ciencias Fsicas y Matem

(=) Si E 0 + e es extendible, existe F

Facultad de Ciencias Fsicas y Matem

Figura 2: EJEMPLO BFS

Facultad de Ciencias Fsicas y Matem

Figura 3: EJEMPLO DFS

Facultad de Ciencias Fsicas y Matem

MA3705. Algoritmos Combinatoriales. 2014.

Facultad de Ciencias Fsicas y Matem

1. 5n2 + 2n4 O(n5 ).

A modo de otro ejemplo: n3 + 5n2 + 40n1,5 = n3 + O(n2 ) = O(n3 ).

Eficiencia o Complejidad de un Algoritmo.

Todo algoritmo recibe una entrada que pueden ser N n

Facultad de Ciencias Fsicas y Matem