Edición de «Práctica 10: Matching - Flujo Máximo (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 10: | Línea 10: | ||
* (DEF) Un vertice v se dice '''saturado por un matching M''' si hay un eje de M incidente a v | * (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 | * (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) | * (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 | **i) nodo aislado | ||
**ii) circuito simple con ejes alternadamente en M0 y M1 | **ii) circuito simple con ejes alternadamente en M0 y M1 |