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)
=>) 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$

Posted by Alejandro (Dr. Cisco / Punga / Scooby)

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)
c)Ver ejemplo midral
d)Mm..buena pregunta :P

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)