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 S es un conjunto independiente maximo 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) F (Un grafo sin ejes no tiene)
b) F (Idem a)
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) V El conjunto indep. maximo en peor tiene tiene n vertices, entonces cada uno estaria en un clique distinto, y entonces el recub. de ejes tiene como minimo n vertices en total -> |I| <= |Re| (mmm.. revisar)
g) F (Por ejemplo el primero grafo del 10.1)

Ejercicio 10.03:

a)
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)
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)

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$

Fin :P

Posted by Alejandro

Ejercicio 10.07:

a)
b)
c)
d)

Ejercicio 10.08:

a)
b)
c)
d)

Ejercicio 10.09:

a)
b)

Flujo Maximo

Ejercicio 10.10:

a)
b)
c)

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)
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.21:

a)
b)

Ejercicio 10.22:

a)
b)

Ejercicio 10.24:

a)
b)

Ejercicio 10.25:

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

Ejercicio 10.26:

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

Ejercicio 10.27:

a)
b)
c)