Diferencia entre revisiones de «Práctica 8: Caminos Eulerianos y Hamiltonianos (Algoritmos III)»

De Cuba-Wiki
Línea 33: Línea 33:
==Ejercicio 08.16:==
==Ejercicio 08.16:==
==Ejercicio 08.17:==
==Ejercicio 08.17:==
Dem: Si G es hamiltonianio entonces, trivialmente, tambien G+uv. Sup. que G+uv is hamiltonian 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]
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.18:==
==Ejercicio 08.18:==

Revisión del 02:12 18 nov 2006

Ejercicio 08.01:


a)
b)

Ejercicio 08.02:

Ejercicio 08.03:

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

Ejercicio 08.04:

Ejercicio 08.05:

Ejercicio 08.06:

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.10:

Ejercicio 08.11:


a)
b)
c)
d)
e)

Ejercicio 08.12:

Ejercicio 08.13:

Ejercicio 08.14:

Ejercicio 08.15:

Ejercicio 08.16:

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.18:

Ejercicio 08.19:

Ejercicio 08.20:


a)
b)
c)
d)

Ejercicio 08.21:


a)
b)
c)
d)
e)

Ejercicio 08.22:

Ejercicio 08.23:


a)
b)
c)

Ejercicio 08.24:


a)
b)
c)

Ejercicio 08.25: