Edición de «Práctica 10: Matching - Flujo Máximo (Algoritmos III)»

De Cuba-Wiki
Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si inicias sesión o creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.

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 85: Línea 85:


Como G es bipartito vale que <math>gr(v) \leq max(|V1|,|V2|)</math> para todo nodo. Sumando sobre los nodos del recubrimiento de aristas, Re, queda que <math>\sum gr(v) \leq max(|V1|,|V2|).\beta</math>. Como Re es un recubrimiento de aristas, sus nodos tocan todos los ejes, con lo cual <math>\sum gr(v) \geq m</math>, y listo.
Como G es bipartito vale que <math>gr(v) \leq max(|V1|,|V2|)</math> para todo nodo. Sumando sobre los nodos del recubrimiento de aristas, Re, queda que <math>\sum gr(v) \leq max(|V1|,|V2|).\beta</math>. Como Re es un recubrimiento de aristas, sus nodos tocan todos los ejes, con lo cual <math>\sum gr(v) \geq m</math>, y listo.
'''Otra forma simple y en criollo:'''
En un bipartito '''sin nodos aislados''' entonces alfa y beta son iguales al maximo entre |P1| y |P2| dado que el maximo conjunto independiente va a ser el tamaño de la partición más grande, y el minimo numero de aristas que se necesitan para cubrir a todos los nodos también, porque sino va a haber nodos en la particion grande que van a quedar sin cubrir.
Ademas, m <= |P1|*|P2| porque a lo sumo se tiene tantas aristas como en el completo que "le corresponde".
En contreto, sea M el maximo entre |P1| y |P2|, por lo anterior
alfa = beta = M
Entonces:
m <= |P1|*|P2| <= M*M = alfa*beta
Y si '''se tiene k nodos aislados''' entonces aglutinamos todos
los nodos aislados en la particion mas grande.
Ahora ellos no contribuyen aristas, con lo cual, si llamamos n' y m' al numero de nodos y aristas del grafo que resulta de eliminar los k nodos aislados, se tiene que:
m' = m y n' = n - k <= n
y ademas
alfa' = alfa - k
donde alfa' es el conjunto independiente maximo del grafo sin los nodos aislados.
Ahora, por lo anterior tenemos que beta' = beta (porque no cambiamos las aristas) y que:
m' <= alfa' * beta' = (alfa - k) beta <= alfa * beta


==Ejercicio 10.06:==
==Ejercicio 10.06:==
Ten en cuenta que todas las contribuciones a Cuba-Wiki pueden ser editadas, modificadas o eliminadas por otros colaboradores. Si no deseas que las modifiquen sin limitaciones, no las publiques aquí.
Al mismo tiempo, asumimos que eres el autor de lo que escribiste, o lo copiaste de una fuente en el dominio público o con licencia libre (véase Cuba-Wiki:Derechos de autor para más detalles). ¡No uses textos con copyright sin permiso!

Para editar esta página, responde la pregunta que aparece abajo (más información):

Cancelar Ayuda de edición (se abre en una ventana nueva)

Plantilla usada en esta página: