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 4: | Línea 4: | ||
(Para todo G: grafo) | (Para todo G: grafo) | ||
* (DEF) Una '''correspondencia o matching''' entre los vertices de G es un conjunto M de ejes tq <math>\forall</math> v en V, v incide hasta en un eje de M <i>(no hay dos ejes de M que toquen | * (DEF) Una '''correspondencia o matching''' entre los vertices de G es un conjunto M de ejes tq <math>\forall</math> v en V, v incide hasta en un eje de M <i>(no hay dos ejes de M que toquen los mismos vertices)</i> | ||
* (DEF) Un '''conjunto independiente''' I de vertices de G es un conjunto I de vertices tq <math>\forall</math> e en E, e incide hasta en un vertice v de I <i>(no hay vertices de I adyacentes entre si)</i> | * (DEF) Un '''conjunto independiente''' I de vertices de G es un conjunto I de vertices tq <math>\forall</math> e en E, e incide hasta en un vertice v de I <i>(no hay vertices de I adyacentes entre si)</i> | ||
* (DEF) Un '''recubrimiento de los ejes''' de G es un conjunto Re de vertices tq <math>\forall</math> e en E, e incide al menos en un nodo v de Re <i>(los vertices de Re "cubren" todos los ejes de G)</i> | * (DEF) Un '''recubrimiento de los ejes''' de G es un conjunto Re de vertices tq <math>\forall</math> e en E, e incide al menos en un nodo v de Re <i>(los vertices de Re "cubren" todos los ejes de G)</i> |