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 16: | Línea 16: | ||
* (DEF) M es un '''matching maximo''' <=> no existe un camino alternado entre pares de nodos no saturados | * (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 Rn un recubrimiento mínimo de los vertices de G -> |M|+|Rn|=n | * (TEO) Si M es un matching máximo y Rn un recubrimiento mínimo de los vertices de G -> |M|+|Rn|=n | ||
* (TEO) Si I es un conjunto independiente máximo y Re un recubrimiento mínimo de los ejes de G | * (TEO) Si I es un conjunto independiente máximo y Re un recubrimiento mínimo de los ejes de G <math>⇒</math> | I | + |Re| = n | ||
* (DEF) Una '''red''' N es un grafo orientado conexo que tiene dos nodos distinguidos una fuente s con grado de salida positivo y un sumidero t con grado de entrada positivo. | * (DEF) Una '''red''' N es un grafo orientado conexo que tiene dos nodos distinguidos una fuente s con grado de salida positivo y un sumidero t con grado de entrada positivo. | ||
* (DEF) Una '''función de capacidades''' en la red es una función c(e)>=0 definida para todo e en EN | * (DEF) Una '''función de capacidades''' en la red es una función c(e)>=0 definida para todo e en EN |