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)