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

Propiedades

(Para todo G: grafo, D: digrafo)

• (DEF) G tiene circuito euleriano <=> $\exists$ circuito en G que recorre todos los ejes de G 1 vez
• (TEO) G tiene circuito euleriano <=> G es conexo y todo vertice tiene grado par
• (COR) G tiene camino euleriano <=> G es conexo y tiene exactamente 2 vertices de grado impar
• (TEO) D tiene circuito euleriano orientado <=> para todo vertice v, d_in(v) = d_out(v)

• (DEF) G tiene circuito hamiltoniano <=> $\exists$ circuito en G que recorre todos los vertices de G 1 vez
• (OBS)
  • 1. G tiene circuito hamiltoniano -> para todo vertice v, d(v) >= 2
  • 2. Sea v en V.
    • Si d(v) = 2 -> Los 2 ejes incidentes a v deben aparecer en todo circuito hamiltoniano en G
    • Si d(v) > 2 -> Al intentar construir un circuito hamiltoniano, luego de pasar por v, ya no se tienen en cuenta los otros ejes incidentes a v
  • 3.Al intentar construir un circuito hamiltoniano, se puede obtener un circuito para un subgrafo de G <=> este contiene todos los vertices de G
• (TEO) D es un torneo -> D contiene un circuito hamiltoniano
• (TEO) Si $\forall$ v,w en V, d(v)+d(w) >= n-1 -> G contiene un camino hamiltoniano
• (COR) Si $\forall$ v en V, d(v) >= (n-1)/2 -> G contiene un camino hamiltoniano
• (TEO) Si $\forall$ v,w en V, v y w no son ady y d(v)+d(w) >= n -> G contiene un circuito hamiltoniano
• (COR) Si $\forall$ v en V, d(v) >= n/2 -> G contiene un circuito hamiltoniano
• (COR) Si n >= 3 y m >= (n-1)(n-2)/2 -> G contiene un circuito hamiltoniano

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)
=>) Probamos de forma constructiva con este algoritmo:
1. Partimos de v0 por un eje
2. Mientras existan ciclos simples sin marcar seguimos marcando ciclos
Como v0 esta en todo ciclo simple y el grafo es euleriano, el algoritmo marca todos los ejes.
<=) Sup. que existe un circuito C tq v0 no esta en C. Ejecuto el algoritmo anterior y cuando termina los ejes de C -> estan marcados -> ABS

b) d(v0) = 2 * #Circuitos simples de G
d(v) = 2 * #Circuitos simples de que pasan por v en la particion en circuitos simples que consideramos -> d(v0) >= d(v) para todo v en G

Ejercicio 08.08:

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

Ejercicio 08.09:

a) (Tiene que salir con algo parecido a este teorema)
Un grafo conexo es euleriano <=> para todo v, d(v) es par
=>) Un vertice que aparece k veces en un circuito euleriano (o k+1, si es el vertice de inicio y final se cuenta 2 veces) debe tener grado 2k -> OK
<=) Sea W = {v0,e0,..,e(l-1),vl} (vi vertices, ei ejes) el camino mas largo que usa cada eje solo una vez. Como no se puede extender, contiene todos los ejes en vl. Como la cantidad de ejes es par -> vl=v0 -> W es un circuito. Sup. que no es euleriano -> G tiene un eje e =(u,vi) para algun u fuera de W. Entonces el camino {u,e,vi,ei,..,e(l-1),vl,e0,..,e(i-1),vi} es mas largo que W -> ABS

b) Se puede encontrar con el siguiente algoritmo:

Algoritmo de Euler:
P.1 Leemos el grafo G conexo con todos los vértices pares
P.2 C = {v}, siendo v un vértice cualquiera de G
P.3 Mientras que en G queden aristas
P.3.1 Sea v un vértice de C, no aislado en G
P.3.2 Sea D un ciclo empezando en v
P.3.3 Eliminar de G las aristas de D
P.3.4 Sustituir en C el vértice v por el ciclo D
P.4 Retorna C

c)

Ejercicio 08.10:

Si tiene un circuito euleriano orientado entonces partiendo del nodo X se puede pasar por todos lados y volver a X. Quiere decir que de cualquier nodo se puede ir a cualquier otro por un camino dirigido, y eso es la def. de fuertemente conexo.

La reciproca no vale, ya que por ej. este grafo es fuertemente conexo pero no tiene circuito:

 o←←o
↓  ↙↑
↓↙  ↑
 o→→o

Ejercicio 08.11:

a)Depende la implementacion. Se podria hacer un BFS en ultima instancia. Igual nose si hay una mejor solucion.
b) Me parece que es muy similar a lo del A.
c) Esto se los dejo de tarea.
d) Depende lo que hayan elegido.
e) Me parece que la idea debe ser usar que n esta acotado por m, y con BFS o DFS teniamos complejidad O(m+n) que se reduce a O(m). Pero habria que preguntar por las dudas.

Ejercicio 08.12:

Porque es bipartito, y una de las particiones tiene 2 nodos más que la otra.

Ejercicio 08.13:

He aqui un circuito hamiltoniano:
http://upload.wikimedia.org/wikipedia/es/2/2c/Grafo_ejemplo_4_ciclo_hamiltoniano.png
Lo del camino de 5 vertices se puede por "algo asi" como que se pasan por las caras de un dodecaedro, entonces siempre se puede extender, por la simetria

Ejercicio 08.14:

Sup. no existe camino hamiltoniano. Sea v el 1er vertice del camino tq w->v є E.

• Si v no є C:

 a->..->b 

b->w є E -> C+w es camino orientado mayor que C -> ABS

• Si v є C:

a->..->v'->v->-..->b
         w/

Como v es el 1ero -> v'->w en E -> C+w es camino orientado mas largo -> (v'->w cambio por v'->v, w->v) -> ABS

Ejercicio 08.15:

El circuito Hamiltoniano es una serie de n+1 pasos donde en el paso 1 estamos parados sobre el primer nodo, y en el paso n+1 nuevamente en el primer nodo. Es evidente que en pasos consecutivos nos moveremos de una partición a otra.. De este modo vemos que empezamos en el paso 1 en una particion (llamemosle V1), luego en el paso 3 volveremos a V1, en el paso 5 volveremos a V1, ....asi hasta llegar a n (ya que n es impar), luego en el paso n+1 deberá estar necesariamente en la otra partición, pues entonces, en el paso n+1 estará en una partición distinta de la partición de donde empezamos, por lo que no se puede formar un circuito hamiltoniano. Se puede formalizar de muchos modos, pero la idea suele ser la misma.

Ejercicio 08.16:

Se puede probar de manera constructiva. Se prueban los nodos para n=4, (el peor caso seria cuando todos tienen grado 2). Luego, se puede ver que partiendo de un grafo G que cumple la propiedad, y agregando un nodo tal que la propiedad se mantenga, se puede formar un circuito hamiltoniano usando el camino hamiltoniano de G, y buscando dos nodos consecutivos a los cuales el nodo agregado este conectado. Al haber dos nodos consecutivos a los cuales el nodo agregado esta conectado, el circuito hamiltoniano se formará llendo de uno de esos nodos al nuevo nodo agregado, y del nodo agregado, al consecutivo que recien dijimos.

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)

[Sacado del libro de North-Holland.. para leerlo tranquilos :P]
Teorema 4.3: si G es un grafo de tal que n>=3 y para todo v, d(v) >= n/2 -> G es hamiltoniano
Dem: Sup. que NO. como n >= 3, G no puede ser completo. Sean u,v vertices no ady. en G. Por eleccion de G, G+uv es hamiltoniano. Mas aun, como G no lo es, cada ciclo hamiltoniano de G+uv debe contener el eje uv. Entonces hay un camino hamiltoniano {v1,..,vk} en G tal que u=v1 y v=vk.
Sean S={vi | hay eje u-v(i+1)} y T={vi | hay eje v(i)-v}. Como vk no esta en S∪T -> |S∪T| < n -> |S∩T| = 0 (ya que si contuviera algun vertice vi, entonces G tendria el ciclo hamiltoniano {v1,..,vi,vk,vk-1,..,vi+1,v1} que seria ABS). Usando lo anterior obtenemos d(u)+d(v)=|S|+|T|=|S∪T|+|S∩T| < n (este es el 4.4). Pero esto contradice HI (para todo v, d(v) >= n/2, con lo cual d(u)+d(v) >= 2*n/2 = n) ABS

Ejercicio 08.18:

Si partimos de un grafo completo una posible mesa redonda se forma a partir de un ciclo hamiltoniano. Luego, otra posible mesa redonde de otro dia sera un circuito hamiltoniano que no use esos ejes, bueno, y asi sucesivamente. Por lo tanto la idea es ver cuantos circuitos hamiltonianos hay, tal que usen distintos ejes.

Ejercicio 08.19:

Sea V = {v1,v2,..,v6}. Como son todos de grado 3, entonces por ej. v1 esta conectado a v2,v3,v4. Entonces c/u de estos 3 esta conectado a otros 2 vertices. Entonces por ej. v4 esta conectado a v5 y v6. Esto implica que v2 y v3 solo les queda para conectarse a v5 y v6. Luego, el grafo resultante es de la forma del K33 (si toman v1,v5,v6 como una particion y v2,v3,v4 como la otra se dan cuenta), y se puede ver que K33 tiene circuito hamiltoniano.

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)