Edición de «Práctica 8: Caminos Eulerianos y Hamiltonianos (Algoritmos III)»

De Cuba-Wiki
Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si inicias sesión o creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.

Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.

Revisión actual Tu texto
Línea 1: Línea 1:
{{Back|Algoritmos y Estructuras de Datos III}}
==Propiedades==
==Propiedades==
(Para todo G: grafo, D: digrafo)
(Para todo G: grafo, D: digrafo)
* (DEF) G tiene '''circuito euleriano''' <=> <math>\exists</math> circuito en G que recorre todos los ejes de G 1 vez
* (DEF) G tiene '''circuito euleriano''' <=> <math>\exists</math> 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
* (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
* (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)
* (TEO) D tiene '''circuito euleriano orientado''' <=> para todo vertice v,  d_in(v) = d_out(v)
Línea 43: Línea 41:
==Ejercicio 08.05:==
==Ejercicio 08.05:==
Supongamos que NO.
Supongamos que NO.
Entonces existe un vértice '''v''' tal que w(G-'''v''') > d(v)/2.
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.
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'''.
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'''.
Línea 53: Línea 51:
n = #nodos
n = #nodos


Si tiene exactamente n-2 nodos de grado par, tiene camino pero no circuito.
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.
Para tener circuito necesita que los n nodos sean de grado par.


Línea 68: Línea 66:


==Ejercicio 08.08:==
==Ejercicio 08.08:==
<br>a) Para todo n impar, n > 2
<br>a) Para todo n impar, n >1
<br>b) K2
<br>b) K2


Línea 92: Línea 90:


==Ejercicio 08.10:==
==Ejercicio 08.10:==
<br>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:
La reciproca no vale, ya que por ej. este grafo es fuertemente conexo pero no tiene circuito:
Línea 103: Línea 100:


==Ejercicio 08.11:==
==Ejercicio 08.11:==
<br>a)Depende la implementación. Se podría hacer un BFS en última instancia. Creo que no hay algo mejor, habría que consultarlo.
<br>a)Depende la implementacion. Se podria hacer un BFS en ultima instancia. Igual nose si hay una mejor solucion.
<br>b) Me parece que es muy similar a lo del A.
<br>b) Me parece que es muy similar a lo del A.
<br>c) Hay que mirar las alternativas de BFS o DFS, que son los que se necesitan para los items anteriores.
<br>c) Esto se los dejo de tarea.
<br>d) Depende lo que hayan elegido, si es BFS o DFS ya deberían saber su complejidad para este momento de la matería :).
<br>d) Depende lo que hayan elegido.
<br>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
<br>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:==
==Ejercicio 08.12:==
Línea 114: Línea 111:
==Ejercicio 08.13:==
==Ejercicio 08.13:==
<br>He aqui un circuito hamiltoniano:
<br>He aqui un circuito hamiltoniano:
<br>http://upload.wikimedia.org/wikipedia/commons/2/2c/Grafo_ejemplo_4_ciclo_hamiltoniano.png
<br>http://upload.wikimedia.org/wikipedia/es/2/2c/Grafo_ejemplo_4_ciclo_hamiltoniano.png
<br>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
<br>(Creo que tomando el camino de 5 vertices de afuera no se puede llegar a un circuito)


==Ejercicio 08.14:==
==Ejercicio 08.14:==
<br>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
<br>Sup. no existe camino hamiltoniano. Sea v el 1er vertice del camino tq w->v є E.
* Si v no є C:
<pre> a->..->b </pre>
b->w є E -> C+w es camino orientado mayor que C -> ABS
* Si v є C:
<pre>
a->..->v'->v->-..->b
        w/
</pre>
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:==
==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.
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..
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.
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.
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:==
==Ejercicio 08.16:==
Se puede probar de manera constructiva.
Se puede probar de manera constructiva.
Se prueban los nodos para n=4, (el peor caso seria cuando todos tienen grado 2).
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.
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.
 
O, más facil:
 
por, (COR) Si <math>\forall\ v \in V, d(v) \ge n/2 \Rightarrow G</math> contiene un circuito hamiltoniano, 
que es lo mismo que <math>d(</math>grado minimo<math>) \ge n/2 \Rightarrow G</math> Hamiltoniano.
Entonces por enunciado, <math>d(</math>grado minimo<math>) \ge n-2</math>
 
<math>n-2 \ge n/2 \Leftrightarrow n \ge 4</math>
 


==Ejercicio 08.17:==
==Ejercicio 08.17:==
'''Enunciado:''' Sea G un grafo con <math>n \ge 3</math> y <math>u</math> y <math>y</math>  dos nodos no adyacentes tal que <math>d(u) + d(v) \ge n</math>.
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)
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


<br>[Sacado del libro de North-Holland.. para leerlo tranquilos :P]
<br>[Sacado del libro de North-Holland.. para leerlo tranquilos :P]
<br>Teorema 4.3: si G es un grafo de tal que <math>n \ge 3</math> y <math> \forall v,\ d(v) \ge \frac{n}{2} \Rightarrow G</math> es hamiltoniano
<br>Teorema 4.3: si G es un grafo de tal que n>=3 y para todo v, d(v)>=n/2 -> G es hamiltoniano
<br>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.
<br>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.
<br>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
<br>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) ABS
 
Otros recursos:
* http://www.proofwiki.org/wiki/Ore%27s_Theorem
* http://www.proofwiki.org/wiki/Dirac%27s_Theorem


==Ejercicio 08.18:==
==Ejercicio 08.18:==
Línea 175: Línea 149:
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.
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.
Por lo tanto la idea es ver cuantos circuitos hamiltonianos hay, tal que usen distintos ejes.
Si tenemos un grafo de <math>m = \frac{n(n-1)}{2}</math> en cada paso vamos a sacar <math>n</math> ejes así que como cota superior no podemos tener más de <math>\frac{n(n-1)}{2n}</math> circuitos hamiltonianos disjuntos en ejes que es lo mismo que: <math>\lfloor\frac{(n-1)}{2}\rfloor</math>.
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:==
==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.
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. <math>G^{c}_{1}</math>: un circuito simple de 6 vértices y <math>G^{c}_{2}</math>: 2 <math>K_{3}</math>. Luego tenemos que <math>G_{1}</math> es una estrella de 6 puntas y <math>G_{2}</math> un bipartito <math>K_{3,3}</math>


==Ejercicio 08.20:==
==Ejercicio 08.20:==
Línea 193: Línea 158:
<br>c)
<br>c)
<br>d)
<br>d)
==Ejercicio 08.21:==
==Ejercicio 08.21:==
<br>a)
<br>a)
Línea 210: Línea 174:
<br>c)
<br>c)
==Ejercicio 08.25:==
==Ejercicio 08.25:==
[[Category: Prácticas]]
Ten en cuenta que todas las contribuciones a Cuba-Wiki pueden ser editadas, modificadas o eliminadas por otros colaboradores. Si no deseas que las modifiquen sin limitaciones, no las publiques aquí.
Al mismo tiempo, asumimos que eres el autor de lo que escribiste, o lo copiaste de una fuente en el dominio público o con licencia libre (véase Cuba-Wiki:Derechos de autor para más detalles). ¡No uses textos con copyright sin permiso!

Para editar esta página, responde la pregunta que aparece abajo (más información):

Cancelar Ayuda de edición (se abre en una ventana nueva)

Plantilla usada en esta página:

Obtenido de «https://www.cubawiki.com.ar/index.php/Práctica_8:_Caminos_Eulerianos_y_Hamiltonianos_(Algoritmos_III)»