Diferencia entre revisiones de «Práctica 4: Problemas de Grafos (Algoritmos III)»
De Cuba-Wiki
| Línea 28: | Línea 28: | ||
==Ejercicio 04.08:== | ==Ejercicio 04.08:== | ||
==Ejercicio 04.09:== | ==Ejercicio 04.09:== | ||
(Sale con Coloreo de Grafos) | |||
==Ejercicio 04.10:== | ==Ejercicio 04.10:== | ||
Revisión del 15:52 15 nov 2006
Ejercicio 04.01:
(Sale con Matching)
Ejercicio 04.02:
Es equivalente a preguntar si hay camino hamiltoniano. El grafo resultante (un cubo de 9 subcubos/vertices por cara) tendria 27 vertices y 26 ejes. Como la suma de ? es impar -> No hay.
Ejercicio 04.03:
a)
b)
c)
d)
Ejercicio 04.04:
(Sale con Vertex Cover)
Ejercicio 04.05:
a)
b)
c)
Ejercicio 04.06:
a)
b)
c)
Ejercicio 04.07:
a) 1.No 2.Si
b) Es equivalente a preguntar si hay circuito euleriano. Hay cuando para todo v, d(v) es par.
c) Un grafo es euleriano <=> tiene un particin en circuitos siempre disjuntos en ejes.
Ejercicio 04.08:
Ejercicio 04.09:
(Sale con Coloreo de Grafos)
