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

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

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)