Edición de «Práctica 9: Planaridad - Coloreo (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 262: | Línea 262: | ||
<br>=>)Sup. que G tiene un circuito C de long. impar -> X(C)= 3 -> no hay forma de usar solo 2 colores -> ABS | <br>=>)Sup. que G tiene un circuito C de long. impar -> X(C)= 3 -> no hay forma de usar solo 2 colores -> ABS | ||
<br><=)Como G no tiene circuitos de long. impar -> G es bipartito -> X(G) = 2 (ya que se puede usar un color para la primer particion y otro para la segunda) -> G es 2-coloreable OK | <br><=)Como G no tiene circuitos de long. impar -> G es bipartito -> X(G) = 2 (ya que se puede usar un color para la primer particion y otro para la segunda) -> G es 2-coloreable OK | ||
<br>b) | <br>b) Se podria usar el alg. para ver si es bipartito. | ||
<br>c) | <br>c) Habria que ver si es eficiente :P | ||
==Ejercicio 09.20:== | ==Ejercicio 09.20:== |