Práctica 11: Matching - Flujo Máximo (Algoritmos III)

Propiedades

(Para todo G: grafo)

• (DEF) Una correspondencia o matching entre los vertices de G es un conjunto M de ejes tq $\forall$ v en V, v incide hasta en un eje de M (no hay dos ejes de M que toquen un mismo vertice)
• (DEF) Un conjunto independiente I de vertices de G es un conjunto I de vertices tq $\forall$ e en E, e incide hasta en un vertice v de I (no hay vertices de I adyacentes entre si)
• (DEF) Un recubrimiento de los ejes de G es un conjunto Re de vertices tq $\forall$ e en E, e incide al menos en un nodo v de Re (los vertices de Re "cubren" todos los ejes de G)
• (DEF) Un recubrimiento de los vertices de G es un conjunto Rn de ejes tq $\forall$ v en V, v incide al menos en un eje e de Rn (los ejes de Rn "cubren" todos los vertices de G)
• (DEF) Un vertice v se dice saturado por un matching M si hay un eje de M incidente a v
• (DEF) Dado un matching M en G, un camino alternado en G es un camino simple donde se alternan ejes que estan en M con ejes que no estan en M
• (TEO) Sean M0 y M1 dos matching en G y sea G´ tq E´= (M0 - M1)$\cup$(M1 - M0) -> las componentes conexas de de G´son de alguno de los siguientes tipos:
  • i) nodo aislado
  • ii) circuito simple con ejes alternadamente en M0 y M1
  • iii) camino simple con ejes alternadamente en M0 y M1
• (DEF) M es un matching maximo <=> no existe un camino alternado entre pares de nodos no saturados
• (TEO) Si M es un matching máximo y Rn un recubrimiento mínimo de los vertices de G -> |M|+|Rn|=n
• (TEO) Si I es un conjunto independiente máximo y Re un recubrimiento mínimo de los ejes de G -> | I | + |Re| = n
• (DEF) Una red N es un grafo orientado conexo que tiene dos nodos distinguidos una fuente s con grado de salida positivo y un sumidero t con grado de entrada positivo.
• (DEF) Una función de capacidades en la red es una función c(e)>=0 definida para todo e en EN
• (DEF) Un flujo factible en una red N con capacidades, es una función f: EN->R+ que verifica:
  • i) 0<=f(e)<=c(e) $\forall$ e en EN.
  • ii) Σ{e en In(v)} f(e) = Σ{e en Out(v)} f(e) $\forall$ v (salvo s y t), donde
    • In(v)={e en EN, e=w->v con w otro vertice de N}
    • Out(v)={e en EN, e=v->w con w otro vertice de N}
• (DEF) Un corte en la red N es un subconjunto S(V) tq s $\in$ S y t $\notin$ S
• (DEF) SS'={ejes que tienen la cola en S y la cabeza en S'} y S'S={ejes que tienen la cola en S' y la cabeza en S} donde S'=V\S
• (TEO) Sea f un flujo definido en una red N y sea S un corte -> F= Σ{e en SS'} f(e)-Σ{e en S'S} f(e)
• (DEF) La capacidad de un corte S se define como c(S)=Σ{e en SS'} c(e)
• (TEO) Si f es una función de flujo con valor F y S es un corte en N, entonces F<=c(S).
• (COR) Certificado de optimalidad: Si F es el valor de un flujo y S un corte en N tal que F=c(S) entonces F es un flujo máximo y S es un corte de capacidad mínima
• (DEF) Un camino de aumento en N es un camino P entre s y t tal que el flujo en un eje “hacia delante” puede crecer y en un eje “hacia atrás”puede decrecer, o sea para todo eje e de P se verifica que f(e)<c(e) si e es “hacia delante”o f(e)>0 si e es “hacia atrás”
• (TEO) Si los valores del flujo inicial y las capacidades de los ejes son enteras -> el método de Ford y Fulkerson termina en un número finito de pasos y determina un flujo máximo en N
• (COR) El valor del flujo máximo en una red N es igual a la capacidad de un corte mínimo
• (TEO) Sea N una red tal que dout(s)>din(s), din(t)>dout(t) y tal que dout(v)=din(v) $\forall$ v distinto de s y t -> hay un camino orientado simple entre s y t en N
• (TEO) Sea N una red tal que dout(s)-din(s)=dint(t)-dout(t)=p y tal que dout(v)=din(v) $\forall$ v distinto de s y t -> existe un conjunto de p caminos simples orientados disjuntos en los ejes entre s y t
• (TEO) Sea N una red con fuente s y sumidero t, tal que c(e)=1 para todo eje e -> el valor F* de un flujo máximo en N es igual al número de caminos simples disjuntos en los ejes entre s y t

• (DEF) Un conjunto de ejes "s-t separador" en un digrafo G es un conjunto de ejes, tal que si se los saca de G, no quedan caminos orientados entre s y t en el grafo resultante
• (TEO) Sea N una red tal que c(e)=1 para todo eje e. La capacidad de un corte mínimo en N es igual al cardinal de un conjunto de ejes “s-t separador” mínimo en N
• (TEO) (Menger) Sean s y t dos nodos distintos en un grafo orientado D. Entonces el máximo número de caminos orientados disjuntos entre s y t en D es igual al cardinal de un conjunto de ejes “s-t separador” mínimo en D
• (TEO) (Hall) Si G es un grafo bipartito con partición (V1, V2) -> G tiene un matching que satura a V1 <=> $\forall$ W$\subset$V1 |W|<=|Г(W)|, donde Г(W) es el conjunto de vertices vecinos a W

Matching

Ejercicio 11.01:

a)
b)
c)
d)

Ejercicio 11.02:

a) V aca uno cree que un grafo sin ejes lo hace falso, pero este si es un matching, es un conj vacio. si revisan la definición, con el conj vacio vale. Un conj de ejes G contenido en E, el vacio, tal que para todo vertice es G, v incide hasta en un eje de M, la defición la cumple. el truco es ver el a lo sumo.

b) F El grafo sin ejes no posee un recubrimiento de vertices, ya que en un recubrimiento los vertices deben ser adyacentes a al menos un eje.
c) V (En todo grafo, un solo vertice es conj. indep)
d) V (En todo grafo, todos los vertices forman un recub. de ejes)
e) V El matching maximo en peor caso tiene n/2 ejes (seria uno con todos los pares de vertices, salvo n impar, entonces queda uno aislado), que a su vez es el minimo de ejes de un recub. de vertices, por la misma razon -> |M| <= |Rv|
f) Falso. Si el grafo no tiene ejes, el vertex cover es vacio y el independent set puede ser todo el grafo.
g) F (Por ejemplo el primero grafo del 11.1)

Ejercicio 11.03:

a)
=>) Sup. que hay un vertice aislado v. Entonces hay un eje que recubre a v -> v esta conectado a otro vertice -> ABS
<=) Si no hay vertices aislados -> siempre se puede recubrir los vertices eligiendo todos los ejes -> OK
b)Supongamos que NO. Sea k la cantidad de ejes con k < [n/2]. Si cada eje cubre 2 vertices, entonces cubrimos 2*k vertices, pero como k <[n/2] entonces 2*k < n. Por lo tanto cada eje debe cubrir mas de 2 vertices. Pero por definicion un eje incide sobre exactamente 2 vertices. ABS que provino de suponer que la cantidad de ejes es k < [n/2].
c)Si no fuera minimal. entonces siempre se podrian sacar ejes del recub. y nunca seria minimal -> ABS
d)Si un recub. de vertices contiene ciclos -> hay vertices cubiertos por mas de 1 eje -> no es minimal -> ABS. Si un recub. de ejes contiene ciclos -> hay ejes cubiertos por mas de 1 vertices -> no es minimal -> ABS
e)n-1. Si hubiera más, habría un ciclo, y luego se podría sacar un eje. Será minimal ya que si sacamos algun eje, luego es posible que haya un vertice que quede sin cubrir.
f)Si existe un camino con long >= 3, por ej. a-b-c-d, entonces hay vertices cubiertos por 2 ejes (cuando se podria haber evitado elegir el eje b-c) -> no es minimal. La vuelta se hace suponiendo que no es minimal.

Ejercicio 11.04:

La propiedad vale para cualquier conjunto independiente y cualquier recubrimiento, no es necesario que sean máximo y mínimo respectivamente.

Sean I y Rn un conjunto independiente y un recubrimiento de nodos. Para cada nodo de I hay al menos un eje en Rn que incide sobre él. Como I es independiente, a cada uno de sus elementos lo tocan ejes distintos. Entonces como máximo hay tantos nodos en I como ejes en Rn.

Ejercicio 11.05:

Probar que si G es bipartito, m <= $\alpha *\beta$, donde $\alpha$=#(conj. indep. maximo) y $\beta$=#(Recubrimiento minimo de aristas)

Sean V1, V2 las particiones de G.

Uno se convence de que $\alpha \geq max(|V1|,|V2|)$. Multiplicando por $\beta$ de los dos lados queda $\alpha .\beta \geq max(|V1|,|V2|).\beta$. Ahora hay que ver por qué eso es mayor a m.

Como G es bipartito vale que $gr(v)\leq max(|V1|,|V2|)$ para todo nodo. Sumando sobre los nodos del recubrimiento de aristas, Re, queda que $\sum gr(v)\leq max(|V1|,|V2|).\beta$. Como Re es un recubrimiento de aristas, sus nodos tocan todos los ejes, con lo cual $\sum gr(v)\geq m$, y listo.

Ejercicio 11.06:

4.1,4.4

Ejercicio 11.07:

a)El algoritmo siempre toma un vertice y elimina ese y sus adyacentes de G, con lo cual el conjunto resultante nunca puede tener vertices adyacentes entre si
b)Con matriz de adyacencia es O(n^2). Es una heuristica golosa
c)Ver ejemplo midral
d)Mm..buena pregunta :P

Ejercicio 11.08:

a)El algoritmo asigna a cada conj. indep. maximo un color, por lo tanto no habra vertices adyacentes con el mismo color. No da el numero cromatico

b)Y..como es NP-Completo debe ser fea :P
c) no, dado que no da el numero cromatico
d)MM.. puede ser

Ejercicio 11.09:

a) Por ej. sea G tq V1={a,b,c} y V2={d,e,f} y los ejes de G son a-b, b-e, c-f -> G tiene matching completo. K2 no tiene (solo se puede elegir un eje de los 2)
b) Creo que sale con Teorema de Hall

Flujo Maximo

Ejercicio 11.10:

a)s-c-a-b-t , s-c-b-t y s-c-t
b)F=4
c)No es lo mismo que b)?

Ejercicio 11.11:

F=12

Ejercicio 11.12:

a)
http://www.subir-imagenes.com/subir_imagenes_fotos/693172db4e.jpg
Elije primero el camino s-a-b-t y aumenta uno en todos. Después elije s-b-a-t, aumenta en s-b uno, disminuye en b-a uno y aumenta en a-t uno. Esto lo vuelve a hacer hasta llegar al flujo máximo . En total son F iteraciones.

b)

Ejercicio 11.13:

Usando BFS en el algoritmo de camino de aumento para marcar nodos y ejes queda O(n*m^2), ya que.. (completar)

Ejercicio 11.14:

a) Hay contraejemplo
b) Hay contraejemplo. Pensar en un cuello de botella de capacidad 1 y todos los demás ejes distintos.

Ejercicio 11.15:

Asignar f(e) $\forall$ e en un ciclo dirigido
Crear un camino de S a T y luego incrementar todos los ejes

$\forall$ e tal que f(e)=0
Si hay camino de S a T tal que incluya a e -> Aumentar el flujo del camino en 1
Sino -> No hay flujo factible

Buscar caminos de disminucion:
Si e1,e2,ei... es un camino de S a T tq f(ei) > c(ei) $\forall$i -> es camino de disminucion
... Y podemos disminuir el flujo del camino en min(f(ei)-c(ei))

No pense lo que pusieron arriba, pero lo saque de un libro y decia que se hacia en dos pasos. el primero es ver si el flujo es factible. el segundo paso es convertir el problema haciendo que todos las cotas inferiores sean cero. esto se logra haciendo que en la red residual rij = (uij-xij)+(xij-lij) donde uij es la cota de capacidad del arco y lij la cota inferior del flujo. (por las dudas ver , Network Flows,Ravindra K. Ahuja,Thomas L. Magnanti,James B. Orlin pag 192)

El problema es complejo y se llama "Maximum Flows with Edge Demands". Pueden encontrar una explicación detallada en: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/25-maxflowext.pdf

Ejercicio 11.17:

Yo lo que hice fue , por cada ciudad un nodo. Y cada eje entre ciudades existe si algun turista puede viajar. La cantidad de lugares entre ciudades es la capacidad. El flujo maximo es lo que decide si los 10 turistas pueden viajar. A mi me dio Flujo Max=11, asi que los 10 turistas puede llegar a Viena.

Aca faltaria algo mas formal para decir que esto esta bien.

Ejercicio 11.18:

Matching maximo en grafo bipartito (V1 son las comisiones, V2 son las personas). Para resolver esto con flujo maximo, se agrega una fuente artificial f y un sumidero artificial. Se transforman los ejes en arcos de V1 a V2, se agregan arcos de s a todo v en V1, y arcos de todo v en V2 a t. A cada arco se le asigna una capacidad de 1. El flujo maximo es la cardinalidad del matching maximo, y los arcos entre V1 y V2 que tiene flujo = 1 son los correspondientes al matching en el grafo orginal.

Para mas detalle, ver [Cormen, Introduction to Algorithms, Cap 26 (Maximun Flow)]

Ejercicio 11.19:

Agregar s conectado a x1, x2, x3, con capacidad 5, 10, 5 respectivamente, y agregar t conectado a y1, y2, y3 con flujo entre [5..inf],[10..inf],[5..inf] respectivamente

Ejercicio 11.20:

Dividir cada vertice en 2, por ej. a se reemplaza por ain->aout, y el eje que los conecta tiene capacidad max. del vertice

Ejercicio 11.21:

a) =>) Como exiten k caminos que no tienen aristas en comun,cualquier corte por aristas debera cortar todos los caminos,por lo tanto debera tener al menos k arcos, cada uno de los k caminos.
<=) (Hago observacion que esto lo consulte en clase, porque no tenia ni la minima idea de como hacerlo)
El grafo no es dirigido, para solucionar este problema se lo convierte en uno dirigido duplicando las aristas con capacidad 1. Se pone a como fuente "s" y a b como sumidero "t". Si todo corte tiene al menos k arcos en el grafo original, en el nuevo grafo dirigido tendra k arcos que salen. En todos los cortes de la red,la capacidad sera almenos k (por esos arcos que salen). El flujo maximo es al menos k, ya que todos los cortes tienen almenos esa capacidad. Se calcula el flujo, y se consideran los ejes con flujo 1. Por conservacion del flujo se puede llegar de "a" a "b" por un camino. Ahora se eliminan estas aristas del grafo y el nuevo flujo sera de almenos k-1.

b)

Ejercicio 11.22:

a)Cambios los ejes por ejes direccionados en ambas vias con capacidad 1, y busco el flujo maximo.
b)

Ejercicio 11.24:

a)
b)

Ejercicio 11.26:

a)
b)
c) En un corte la capacidad esta dada por :
$\sum _{e\in SS^{c}}c_{ij}-\sum _{e\in S^{c}S}b_{ij}$
Observacion : Comparar esto con el corte cuando no hay limite inferior, aca estamos obligados a mandar flujo encontra.
Supongamos $v$ el valor de un flujo valido y el flujo que pasa por cada arista $x_{ij}$. Entonces
$v=\sum _{e\in SS^{c}}x_{ij}-\sum _{e\in S^{c}S}x_{ij}$ En particular vale que $x_{ij}\leq c_{ij}$ y $x_{ij}\geq b_{ij}$. Usando esto vale que :
$v\leq \sum _{e\in SS^{c}}c_{ij}-\sum _{e\in S^{c}S}b_{ij}$
d)
e)
f)

Ejercicio 11.27:

a)
b)
c)