Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si
inicias sesión o
creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.
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 95: |
Línea 95: |
|
| |
|
| ==Ejercicio 10.10:== | | ==Ejercicio 10.10:== |
| <br>a)
| | El grafo de Grotzsch. (Es el grafo de Mycielski 4, M_4.) |
| <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>b) Con BFS (si llego a un vertice marcado y se quiere pintar con el mismo color -> no es 2-coloreable)
| |
| <br>c) O(n+m)
| |
|
| |
|
| ==Ejercicio 10.11:== | | ==Ejercicio 10.11:== |