Diferencia entre revisiones de «Práctica 8: Caminos Eulerianos y Hamiltonianos (Algoritmos III)»
Línea 19: | Línea 19: | ||
==Ejercicio 08.05:== | ==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:== | ==Ejercicio 08.06:== | ||
==Ejercicio 08.07:== | ==Ejercicio 08.07:== |
Revisión del 01:32 20 nov 2006
Ejercicio 08.01:
a)
b)
Ejercicio 08.02:
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:
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)