Edición de «Resumen (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 138: | Línea 138: | ||
(Nota de otro lector: El problema es que tomas vertex cover como cubrimiento de vertices, para la bibliografia en ingles vertex cover es recubrimiento de aristas, por lo que en el ejemplo el matching maximo tiene 0 ejes y el vertex cover tiene 0 vertices porque no hay aristas). (Nota de lector 2 : el teorema que se puede consultar en el gross pagina 568 se llama konig,1931 ) | (Nota de otro lector: El problema es que tomas vertex cover como cubrimiento de vertices, para la bibliografia en ingles vertex cover es recubrimiento de aristas, por lo que en el ejemplo el matching maximo tiene 0 ejes y el vertex cover tiene 0 vertices porque no hay aristas). (Nota de lector 2 : el teorema que se puede consultar en el gross pagina 568 se llama konig,1931 ) | ||
* Dado un grafo G sin vértices aislados, I un conjunto independiente máximo y Re un recubrimiento de nodos mínimo, vale que <math>|I| \leq |R_e|</math> | * Dado un grafo G sin vértices aislados, I un conjunto independiente máximo y Re un recubrimiento de nodos mínimo, vale que <math>|I| \leq |R_e|</math> | ||
* Dado un grafo G, si M es un matching máximo y Re un recubrimiento mínimo de los nodos de V, entonces <math>|M| + |R_e| = n</math>. Es un problema bien resuelto. | * Dado un grafo G, si M es un matching máximo y Re un recubrimiento mínimo de los nodos de V, entonces <math>|M| + |R_e| = n</math>. Es un problema bien resuelto. |