Práctica 10: 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 en S y t no en 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 10.01:

a)
b)
c)
d)

Ejercicio 10.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 10.1)

Ejercicio 10.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 habría 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

Ejercicio 10.04:

Si G tiene un conjunto independiente de n nodos, entonces cada uno esta en un clique distinto, y el cubrimiento minimo tiene por lo menos n cliques -> |I|<=|Rn|

Ejercicio 10.05:

Probar que si G es bipartito, m <= $\alpha *\beta$, donde $\alpha$=#(conj. indep. maximo) y $\beta$=#(Recubrimiento minimo de aristas)
Sea: $v\in \Re$, y V1,V2 las particiones de G
$m\leq 2*m=\sum d(v)\leq max(|V1|,|V2|)*\beta \leq \alpha *\beta$

Ejercicio 10.06:

Ehh.. otro dia con mas tiempo lo analizo

Ejercicio 10.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 10.08:

a)El algoritmo asigna a cada conj. indep. maximo un color, por lo tanto no habra vertices adyacentes con el mismo color
b)Y..como es NP-Completo debe ser fea :P
c)Creo que si
d)MM.. puede ser

Ejercicio 10.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 10.10:

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

Ejercicio 10.11:

Cuentas cuentas..

Ejercicio 10.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 10.13:

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

Ejercicio 10.14:

a)Hay contraejemplo
b)

Ejercicio 10.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))

Posted By Alejandro

Ejercicio 10.17:

Despues lo dibujo

Ejercicio 10.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 10.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 10.21:

a) (Revisar) =>) Facil <=) Sup. no fueran disjuntos. Existe un corte de menos de k arcos ABS
b)

Ejercicio 10.22:

a)Con DFS sacando ejes usados
b)Con DFS sacando vertices usados

Ejercicio 10.24:

a)
b)

Ejercicio 10.25:

HECHO EN CLASE, ALGUIEN QUE LO TENGA SUBALO (por favor)
a)
b)

Ejercicio 10.26:

a)
b)
c)
d)
e)
f)

Ejercicio 10.27:

a)
b)
c)