Edición de «Práctica 11: 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 60: | Línea 60: | ||
<br>e) V El matching maximo en peor caso tiene n/2 ejes (seria uno con todos los pares de vertices, salvo n impar, entonces queda uno aislado), que a su vez es el minimo de ejes de un recub. de vertices, por la misma razon -> |M| <= |Rv| | <br>e) V El matching maximo en peor caso tiene n/2 ejes (seria uno con todos los pares de vertices, salvo n impar, entonces queda uno aislado), que a su vez es el minimo de ejes de un recub. de vertices, por la misma razon -> |M| <= |Rv| | ||
<br>f) Falso. Si el grafo no tiene ejes, el vertex cover es vacio y el independent set puede ser todo el grafo. | <br>f) Falso. Si el grafo no tiene ejes, el vertex cover es vacio y el independent set puede ser todo el grafo. | ||
<br>g) F (Por ejemplo el primero grafo del | <br>g) F (Por ejemplo el primero grafo del 10.1) | ||
==Ejercicio 11.03:== | ==Ejercicio 11.03:== |