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

Supongamos que NO. Entonces existe un vértice v tal que w(G-v) = d(v)/2. Sea d(v) = 2k, entonces w(G-v) = k' > 2k/2 = k. Es claro, que al ser k' > k, y al estar v conectado con k' componentes conexas, al menos habra una componente conexa con la cual solo habra un eje conectado a v. A la vez como el grado de v es par, debe haber otra componente conexa con la cual tiene una cantidad impar de ejes incidentes en v. Pero con que haya una componente conexa, a la cual se conecta con solo una arista, ya basta para ver que no es un grafo euleriano, ya que partiendo de v, y usando esa arista se podra entrar a esa componente conexa, pero nunca salir usando otra arista que no sea la de v. Por lo tanto llegamos al ver que no es euleriano llegamos a nuestro amigo, el Absurdo....

Ejercicio 08.06:

n = #nodos Si tiene exactamente n-2 nodos de grado impar, tiene camino pero no circuito. Para tener circuito necesita que los n nodos sean de grado par.

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)