Diferencia entre revisiones de «Práctica 4: Problemas de Grafos (Algoritmos III)»

De Cuba-Wiki
Línea 23: Línea 23:
==Ejercicio 04.07:==
==Ejercicio 04.07:==
<br>a) 1.No 2.Si
<br>a) 1.No 2.Si
<br>b) Es equivalente a preguntar si hay camino euleriano. Hay cuando para todo v, d(v) es par.
<br>b) Es equivalente a preguntar si hay circuito euleriano. Hay cuando para todo v, d(v) es par.
<br>c) Un grafo es euleriano <=> tiene un particin en circuitos siempre disjuntos en ejes.
<br>c) Un grafo es euleriano <=> tiene un particin en circuitos siempre disjuntos en ejes.



Revisión del 15:42 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:

Ejercicio 04.10: