Práctica 10: Matching - Flujo Máximo (Algoritmos III)

De Cuba-Wiki

Propiedades

(Para todo G: grafo)

  • (DEF) Una correspondencia o matching entre los vertices de G es un conjunto M de ejes tq 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 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 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 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) e en EN.
    • ii) Σ{e en In(v)} f(e) = Σ{e en Out(v)} f(e) 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) 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) 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 <=> WV1 |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.04:

Ejercicio 10.05:

Probar que si G es bipartito, m <= , donde =#(conj. indep. maximo) y =#(Recubrimiento minimo de aristas)



{(v1),(v2)}

Fin :P

Ejercicio 10.06:

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.11:

Ejercicio 10.12:


a)
b)

Ejercicio 10.13:

Ejercicio 10.14:


a)
b)

Ejercicio 10.15:

Ejercicio 10.16:

Ejercicio 10.17:

Ejercicio 10.18:

Ejercicio 10.19:

Ejercicio 10.20:

Ejercicio 10.21:


a)
b)

Ejercicio 10.22:


a)
b)

Ejercicio 10.23:

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)

Ejercicio 10.28: