Ciclos Hamiltonianos en grafos aleatorios

--- title: Ciclos Hamiltonianos en grafos aleatorios tags: Graphs, Talk description: View the slide with "Slide Mode". header-includes: - \usepackage[ruled,vlined,linesnumbered]{algorithm2e} slideOptions: theme: league transition: 'slide' spotlight: enabled: true --- # Ciclos Hamiltonianos en grafos aleatorios  Por: Carlos Emiliano Solórzano --- Ciclo Hamiltoniano --- :::info __Definición:__ Un ciclo Hamiltoniano es un ciclo que pasa por cada vertice de un grafo $G$ exactamente una sola vez. ::: ![](https://i.imgur.com/3kbCpcf.gif =250x) El problema de encontrar un ciclo Hamiltoniano en un grafo dado es un problema NP-hard. Se quiere encontrar un algoritmo que, considerando a la entrada como un grafo aleatorio, pueda encontrar una solución eficientemente. --- Grafo Aleatorio --- Para el algoritmo se considera el modelo de grafo aleatorio de Erdös–Rényi para grafos simples no dirigidos $G_{n, p}$. En este cada arista de los $\frac{n(n-1)}{2}$ pares posibles es generado con una probabilidad $p$. ![](https://www.fitzner.nl/simulator/files/ERdef.gif =500x) --- El algoritmo que se presenta funciona con una operación llamada _rotación_. Con esta, dado un camino simple $$P=v_1, v_2, ..., v_k$$ en un grafo $G$ y siendo $(v_k, v_i)$ una arista de $G$. Entonces $$P'=v_1, v_2, ..., v_i, v_k, v_{k-1},..., v_{i+2}, v_{i+1}$$ es el nuevo camino, el cual también es simple. --- ![](https://i.imgur.com/8ixckAZ.png) ![](https://i.imgur.com/3qHYHSO.png) --- Un primer algoritmo --- Una primera solución al problema considera que se tiene una lista de aristas adyacentes para cada vertice $v$ en el grafo. Las cuales están ordenados de forma aleatorio. Se escoge entonces un vertice al azar, el cual se convierte en la _cabeza_ del camino. El cual se hace crecer tomando las aristas que tiene la cabeza a su disposición. En caso de que encuentre una arista $(v_k, v_i)$ el camino rota y se toma a $v_{k+1}$ como la cabeza. --- <section style="text-align: left;"> Primer Algoritmo ---- __Entrada:__ Un grafo $G=(V,E)$ con $n$ vertices. __Salida:__ Un ciclo hamiltoniano o fracaso. 1. Comienza con un vertice aleatorio como la cabeza del camino. 2. Repite hasta el cicle se cierre o la lista de vertices sin usar quede vacía: a) Sea el actual camino $P=v_1, v_2, ..., v_k$ donde $v_k$ es la cabeza y sea $(v_k, u)$ la primer arista de la lista de la cabeza. b) Retira a $(v_k, u)$ de la lista de $v_k$ y de $u$. c) Si $u\neq v_i$ para $1\leq i \leq k$, añade $u=v_{k+1}$ al final del camino y se convierte en la cabeza. d) De otra forma, $u=v_i$, haz una rotación del actual camino con $(v_k, v_i)$ y $v_{k+1}$ es la nueva cabeza. Termina si el camino es de tamaño $n$ y la arista es $(v_n, v_1)$. 3. Regresa un ciclo Hamiltoniano si fue encontrado o fracaso. </section> --- Algoritmo modificado --- El algoritmo falla si la cabeza de este se queda sin aristas adyacentes, sin embargo en este algoritmo es difícil de analizar cúando ocurre eso. Para esto se propone una modificación en el algoritmo, esta vez introduciendo dos listas: * used-edges($v$), la cual contiene las aristas adyacentes a $v$ que se han visto en el transcurso del algoritmo con $v$ a la cabeza. * unused-edges($v$), contiene aquellas aristas adyacentes a $v$ que no se han usado todavía. Aunque menos eficiente, el algoritmo es más fácil de analizar para grafos aleatorios. --- <section style="text-align: left; font-size: 22px;"> Algoritmo Modificado ---- __Entrada:__ Un grafo $G=(V,E)$ con $n$ vertices y listas de aristas asociados. __Salida:__ Un ciclo hamiltoniano o fracaso. 1. Comienza con un vertice aleatorio como la cabeza del camino. 2. Repite hasta el cicle se cierre o la lista de vertices sin usar quede vacía a) Sea el actual camino $P=v_1, v_2, ..., v_k$ donde $v_k$ es la cabeza. b) Ejecuta i, ii, iii con probabilidades $1/n$, $\vert used-edges(v) \vert /n$, y $1-1/n -\vert used-edges(v) \vert /n$ respectivamente. * i. Invierte el camino con $v_1$ como la cabeza. * ii. Escoge uniformemente aleatoriamente una arista de used-edges($v_k$); si la arista es $(v_k, v_i)$ rota el actual camino con $(v_k, v_i)$ y sea $v_{k+1}$ la cabeza. * iii. Elige la primer arista de unused-edges($v_k$), llamalo $(v_k, u)$. Si $u\neq v_i$ para $1\leq i \leq k$, entonces añade $u=v_{k+1}$ y es la nueva cabeza. De otra forma $u=v_i$, realiza una rotación con $(v_k, v_i)$ y $v_{i+1}$ es la nueva cabeza. (Esto cierra el ciclo Hamiltoniano si $k=n$ y la arista elegida es $(v_n, v_1)$) c) Actualiza las listas de used-edges y unused-edges. 3. Regresa un ciclo Hamiltoniano si fue encontrado o fracaso. </section> --- Algunas diferencias con el algoritmo original: * Si una arista $(u, v)$ fue usada antes puede volver a ser usada. * Un vertice no visitado por el actual vertice cabeza, pudo haber sido visitado por otro vertice. --- Se propone entonces el lema siguiente: :::info **Lema 1:** Suponiendo que se corre el algoritmo modificado en un grafo aleatorio según el modelo descrito. Sea $V_t$ la cabeza del algoritmo en el paso $t$. Entonces para cualquier vertice $u$, considerando que queda al menos una arista disponible en el veritce cabeza en el paso $t$, $$Pr(V_{t+1}=u\vert V_t=u_t, V_{t-1}=u_{t-1},..., V_0=u_0)=1/n$$ ::: --- Demostración --- Para la demostración se pueden analizar los sigueintes casos 1. $u$ es el primer vertice de $P$. 2. $u$ es un vertice en $P$ diferente al primero, 3. $u$ no se encuentra en $P$. --- **Caso 1.** Este caso permite la única posibilidad de que $v_1$ se convierta en la cabeza del camino dado que la rotación siempre convierte a la cabeza a un vertice $v_{i+1}$. Este es el caso cuando el algoritmo elige la opción i, con una probabilidad de $1/n$ y $u$ siendo la única opción. --- **Caso 2.** Suponiendo que se trata de un $v_i\in P$. Este caso se puede a su vez dividir en dos subcasos, esto es cuando $v_k$ ha visitado previamente a $v_{i-1}$ y cuando no. El primer subcaso se da cuando $(v_k, v_{i-1})$ se encuentra dentro de used-edges($v_k$) y por tanto el algoritmo ha de elegir a la opción ii. La probabilidad entonces es la siguiente: $$Pr(V_{t+1}=u\vert (v_k, v_{i-1})\in used-edges(v_k))= Pr(u\vert ii)\cdot Pr(ii)$$ $$=\frac{1}{\vert used-edges(v_k)\vert}\cdot \frac{\vert used-edges(v_k)\vert}{n}=\frac{1}{n}$$ --- El segundo subcaso entonces se da en la opción iii, pues no se ha visitado. Suponemos que no contamos cada vez el numero de elementos restantes en la lista unused-edges($v_k$), pero si un contador para los que se han visitado, entonces $\vert unused-edges(v_k)\vert$ tendrá a lo más $n-\vert used-edges(v_k)\vert-1$ vertices sin visitar. Su probabilidad entonces es de, $$Pr(V_{t+1}=u\vert (v_k, v_{i-1})\not \in used-edges(v_k))= Pr(u\vert iii)\cdot Pr(iii)$$ $$=\frac{1}{n-\vert used-edges(v_k)\vert-1}\cdot\left(1-\frac{1}{n}-\frac{\vert used-edges(v_k)\vert}{n}\right) =\frac{1}{n}$$ --- **Caso 3.** El tercer caso es cuando $u$ no se encuentra en $P$, entonces corresponde a elegir la opción iii en el algoritmo. El calculo de su probabilidad es la misma del segundo subcaso anterior, dando nuevamente $1/n$. La diferencia es que en este caso no se realiza la rotación y el camino crece. Por tanto cualquier vertice se puede convertir en la cabeza con probabilidad $1/n$. --- <style> .present{ font-size: 30px; } .present h1 { font-size: 50px; } </style>