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 par, 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 > 2
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 implementación. Se podría hacer un BFS en última instancia. Creo que no hay algo mejor, habría que consultarlo.
b) Me parece que es muy similar a lo del A.
c) Hay que mirar las alternativas de BFS o DFS, que son los que se necesitan para los items anteriores.
d) Depende lo que hayan elegido, si es BFS o DFS ya deberían saber su complejidad para este momento de la matería :).
e) Como n esta acotado por m, dado que G debe ser conexo, con BFS o DFS teníamos complejidad O(m + n) que se reduce a O(m). Cumpliendo la complejidad pedida

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/commons/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 C el camino maximo. Como no es hamiltoniano -> C tiene menos de n nodos. Sea v un vertice que no pertenece a C. Entonces si a es el primer vertice de C y b el ultimo, existe dos unicas posibles orientaciones: a->v y v->b. Entonces el resto de los vertices de C tienen que estar orientados hacia v, pero aunque el anteultimo vertice este orientado hacia v o viceversa, se puede lograr extender el camino incluyendo a v -> C+v es el camino maximo -> ABS

Ejercicio 08.15:

Es inmediato usando el siguiente teorema que permite determinar cuándo un grafo no es hamiltoniano:

Sea G un grafo conexo. Si existe un subconjunto W de los vértices de G tal que G\W tiene c componentes conexas, y c > |W|, entonces G no es hamiltoniano.

Volviendo al ejercicio, si al grafo bipartito le quitamos la partición con el menor número de nodos, el grafo resultante tendrá más componentes conexas que el número de vértices removidos. Luego, por el teorema anterior, resulta que el grafo no puede ser hamiltoniano.

---

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.

---

Otra demo (por el absurdo): Supongamos que G es hamiltoniano. Sea C el ciclo hamiltoniano. C contiene a todos los nodos de G una univa vez (por def), por lo que la longitud de C es n, que es impar por hipotesis. Pero entonces G no puede ser bipartito. El absurdo provino de suponer G hamiltoniano.

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á yendo de uno de esos nodos al nuevo nodo agregado, y del nodo agregado, al consecutivo que recién dijimos.

O, más facil:

por, (COR) Si $\forall \ v\in V,d(v)\geq n/2\Rightarrow G$ contiene un circuito hamiltoniano, que es lo mismo que $d($grado minimo$)\geq n/2\Rightarrow G$ Hamiltoniano. Entonces por enunciado, $d($grado minimo$)\geq n-2$

$n-2\geq n/2\Leftrightarrow n\geq 4$

Ejercicio 08.17:

Enunciado: Sea G un grafo con $n\geq 3$ y $u$ y $y$ dos nodos no adyacentes tal que $d(u)+d(v)\geq n$. Probar que G es hamiltoniano sí y sólo si G + el eje $uv$ es hamiltoniano.

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)

Esto basicamente es la demostracion del teorema Bondy-Chaval

• https://planetmath.org/proofofbondyandchvataltheorem

[Sacado del libro de North-Holland.. para leerlo tranquilos :P]
Teorema 4.3: si G es un grafo de tal que $n\geq 3$ y $\forall v,\ d(v)\geq {\frac {n}{2}}\Rightarrow 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

Otros recursos:

• http://www.proofwiki.org/wiki/Ore%27s_Theorem
• http://www.proofwiki.org/wiki/Dirac%27s_Theorem

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.

Si tenemos un grafo de $m={\frac {n(n-1)}{2}}$ en cada paso vamos a sacar $n$ ejes así que como cota superior no podemos tener más de ${\frac {n(n-1)}{2n}}$ circuitos hamiltonianos disjuntos en ejes que es lo mismo que: $\lfloor {\frac {(n-1)}{2}}\rfloor$.

La cota inferior se puede ver en https://math.stackexchange.com/questions/881420/number-of-edge-disjoint-hamiltonian-cycles-in-a-complete-graph-with-even-number.

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.

---

Usando la sugerencia, al buscar el grafo complemento se llegan a 2 posibles grafos. $G_{1}^{c}$: un circuito simple de 6 vértices y $G_{2}^{c}$: 2 $K_{3}$. Luego tenemos que $G_{1}$ es una estrella de 6 puntas y $G_{2}$ un bipartito $K_{3,3}$

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)