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

Propiedades

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)