Edición de «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 <math>\forall</math> v en V, v incide hasta en un eje de M <i>(no hay dos ejes de M que toquen un mismo vertice)</i>
* (DEF) Un '''conjunto independiente''' I de vertices de G es un conjunto I de vertices tq <math>\forall</math> e en E, e incide hasta en un vertice v de I <i>(no hay vertices de I adyacentes entre si)</i>
* (DEF) Un '''recubrimiento de los ejes''' de G es un conjunto Re de vertices tq <math>\forall</math> e en E, e incide al menos en un nodo v de Re <i>(los vertices de Re "cubren" todos los ejes de G)</i>
* (DEF) Un '''recubrimiento de los vertices''' de G es un conjunto Rn de ejes tq <math>\forall</math> v en V, v incide al menos en un eje e de Rn <i>(los ejes de Rn "cubren" todos los vertices de G)</i>
* (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)<math>\cup</math>(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) <math>\forall</math> e en EN.
**ii) Σ{e en In(v)} f(e) = Σ{e en Out(v)} f(e) <math>\forall</math> 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) <math>\forall</math> 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) <math>\forall</math> 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 <=> <math>\forall</math> W<math>\subset</math>V1 |W|<=|Г(W)|, donde Г(W) es el conjunto de vertices vecinos a W

<table bgcolor="blue"><tr><td><font color="white"> Matching </font></td></tr></table>

==Ejercicio 10.01:==
<br>a)
<br>b)
<br>c)
<br>d)

==Ejercicio 10.02:==
<br>a) F (Un grafo sin ejes no tiene)
<br>b) F (Idem a)
<br>c) V (En todo grafo, un solo vertice es conj. indep)
<br>d) V (En todo grafo, todos los vertices forman un recub. de ejes)
<br>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|
<br>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)
<br>g) F (Por ejemplo el primero grafo del 10.1)

==Ejercicio 10.03:==
<br>a)
<br>=>) Sup. que hay un vertice aislado v. Entonces hay un eje que recubre a v -> v esta conectado a otro vertice -> ABS
<br><=) Si no hay vertices aislados -> siempre se puede recubrir los vertices eligiendo todos los ejes -> OK
<br>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].
<br>c)Si no fuera minimal. entonces siempre se podrian sacar ejes del recub. y nunca seria minimal -> ABS
<br>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
<br>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.
<br>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 <= <math>\alpha * \beta </math>, donde <math>\alpha</math>=#(conj. indep. maximo) y <math>\beta</math>=#(Recubrimiento minimo de aristas)
<br>Sea: <math>v \in \real</math>, y V1,V2 las particiones de G
<br><math>m \leq 2*m = \sum d(v) \leq max(|V1|,|V2|)* \beta \leq  \alpha * \beta </math>

Posted by Alejandro

==Ejercicio 10.06:==
Ehh.. otro dia con mas tiempo lo analizo

==Ejercicio 10.07:==
<br>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
<br>b)Con matriz de adyacencia es O(n^2). Es una heuristica golosa
<br>c)Ver ejemplo midral
<br>d)Mm..buena pregunta :P

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

==Ejercicio 10.09:==
<br>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)
<br>b) Creo que sale con Teorema de Hall

<table bgcolor="blue"><tr><td><font color="white"> Flujo Maximo </font></td></tr></table>

==Ejercicio 10.10:==
<br>a)s-b-t y s-c-b-t
<br>b)F=4
<br>c)No es lo mismo que b)?

==Ejercicio 10.11:==
Cuentas cuentas..

==Ejercicio 10.12:==
<br>a)
<br>http://www.subir-imagenes.com/subir_imagenes_fotos/693172db4e.jpg
<br>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.

<br>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:==
<br>a)Hay contraejemplo
<br>b)

==Ejercicio 10.15:==
Asignar f(e) <math>\forall</math> e en un ciclo dirigido
<br> Crear un camino de S a T y luego incrementar todos los ejes 

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

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

Posted By Alejandro

==Ejercicio 10.16:==
==Ejercicio 10.17:==
Despues lo dibujo

==Ejercicio 10.18:==
==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:==
<br>a) (Revisar) =>) Facil <=) Sup. no fueran disjuntos. Existe un corte de menos de k arcos ABS
<br>b)

==Ejercicio 10.22:==
<br>a)Con DFS sacando ejes usados
<br>b)Con DFS sacando vertices usados

==Ejercicio 10.23:==
==Ejercicio 10.24:==
<br>a)
<br>b)
==Ejercicio 10.25:==
<b>HECHO EN CLASE, ALGUIEN QUE LO TENGA SUBALO (por favor)</b>
<br>a)
<br>b)

==Ejercicio 10.26:==
<br>a)
<br>b)
<br>c)
<br>d)
<br>e)
<br>f)
==Ejercicio 10.27:==
<br>a)
<br>b)
<br>c)
==Ejercicio 10.28:==