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
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 Posted by "El Punga"

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: