Práctica 8: Caminos Eulerianos y Hamiltonianos (Algoritmos III)

Ejercicio 08.01:

a)
b)

Ejercicio 08.03:

1.Si 2.Si 3.No 4.No

Ejercicio 08.04:

Probamos las 2 implicaciones por separado:

=>) Como G es conexo y tiene circuito euleriano, cada nodo tiene grado par y por lo tanto G contiene algun ciclo C. Si sacamos los ejes de C pueden pasar 2 cosas: Si C era el único circuito, luego trivial. Si no nos queda G' donde cada nodo también tendrá grado par, y por lo tanto volvemos a aplicar esto recursivamente.

(Una demostración más formal se puede hacer usando inducción, ya que justamente como dije arriba, es cuestión de aplicar recursivamente una función que nos saque un circuito).

<=) Sea G conexo y particionable en K circuitos: C1, C2, ... , Ck Si sacamos los ejes de C1, luego como G es conexo nos quedan nodos que habían en común entre C1, y otro Ci (Esto es casi trivial probarlo). Luego hay que nuevamente ir recorriendo los ciclos, sabiendo que tendremos nodos compartidos con ciclos no recorridos anteriormente, y esto se podrá hacer k veces, y luego habremos encontrado nuestro circuito euleriano.

Ejercicio 08.07:

a)
b)

Ejercicio 08.08:

a) Para todo n impar, n >1
b) K2

Ejercicio 08.09:

a)
b)
c)

Ejercicio 08.11:

a)
b)
c)
d)
e)

Ejercicio 08.17:

Dem: Si G es hamiltoniano entonces, trivialmente, tambien G+uv lo es. Sup. que G+uv es hamiltoniano pero G no lo es. Entonces, como en la dem. del teorema 4.3, obtenemos (4.4). Pero esto contradice la hipotesis (4.5) [Ver North-Holland]

Ejercicio 08.20:

a)
b)
c)
d)

Ejercicio 08.21:

a)
b)
c)
d)
e)

Ejercicio 08.23:

a)
b)
c)

Ejercicio 08.24:

a)
b)
c)