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 59: | Línea 59: | ||
<br>d) V (En todo grafo, todos los vertices forman un recub. de ejes) | <br>d) V (En todo grafo, todos los vertices forman un recub. de ejes) | ||
<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) | <br>f) V El conjunto indep. maximo en peor tiene tiene n vertices, entonces cada uno estaria en un clique distinto, y entonces el recub. de ejes tiene como minimo n vertices en total -> |I| <= |Re| (mmm.. revisar) | ||
<br>g) F (Por ejemplo el primero grafo del 10.1) | <br>g) F (Por ejemplo el primero grafo del 10.1) | ||