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}}
<pre>
 
PROPIEDADES IMPORTANTES PARA ESTA PRACTICA:
==Propiedades==
..
(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
</pre>
* (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''' <=> <math>\exists</math> 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 <math>\forall</math> v,w en V, d(v)+d(w) >= n-1 -> G contiene un camino hamiltoniano
* (COR) Si <math>\forall</math> v en V, d(v) >= (n-1)/2 -> G contiene un camino hamiltoniano
* (TEO) Si <math>\forall</math> v,w en V, v y w no son ady y d(v)+d(w) >= n -> G contiene un circuito hamiltoniano
* (COR) Si <math>\forall</math> 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:==
==Ejercicio 08.01:==
Línea 43: Línea 26:
==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 36:
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 65: Línea 48:


<br>b) d(v0) = 2 * #Circuitos simples de G
<br>b) d(v0) = 2 * #Circuitos simples de G
<br>  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
<br>  d(v)  = 2 * #Circuitos simples de que pasan por v en la particion en circuitos simples que consideramos.
<br>-> d(v0) >= d(v) para todo v en G


==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 76:


==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:
<pre>
o←←o
↓  ↙↑
↓↙  ↑
o→→o
</pre>
==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 113: Línea 87:


==Ejercicio 08.13:==
==Ejercicio 08.13:==
<br>He aqui un circuito hamiltoniano:
<br>http://upload.wikimedia.org/wikipedia/commons/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
==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 122:
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.
----
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:==
<br>a)
<br>a)
Línea 193: Línea 129:
<br>c)
<br>c)
<br>d)
<br>d)
==Ejercicio 08.21:==
==Ejercicio 08.21:==
<br>a)
<br>a)
Línea 210: Línea 145:
<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)»