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 es incidente a lo sumo a un eje e en M
• (DEF) Un conjunto independiente I de vertices de G es un conjunto I de vertices tq $\forall$ e en E, e es incidente a lo sumo a un vertice v en I
• (DEF) Un recubrimiento de los ejes de G es un conjunto Rn de vertices tq $\forall$ e en E, e es incidente al menos a un nodo v en Rn
• (DEF) Un recubrimiento de los vertices de G es un conjunto Re de ejes tq $\forall$ v en V, v es incidente al menos a un eje e en Re
• (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)∪(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 Re un recubrimiento mínimo de los vertices de V -> |M|+|Re|=n
• (TEO) Si I es un conjunto independiente maximo y Rn un recubrimiento mínimo de los ejes de V -> |I|+|Rn|=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)
b)
c)
d)
e)
f)
g)

Ejercicio 10.03:

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

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$
$m\leq \sum d(v)\leq${(v1),(v2)}
$\beta \leq \alpha *\beta$

Fin :P

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

Ejercicio 10.14:

a)
b)

Ejercicio 10.21:

a)
b)

Ejercicio 10.22:

a)
b)

Ejercicio 10.24:

a)
b)

Ejercicio 10.25:

a)
b)

Ejercicio 10.26:

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

Ejercicio 10.27:

a)
b)
c)