Probabilidad de encontrar un circuito de Hamilton en un gráfico

Question

En resumen, me gustaría saber la probabilidad de que exista un circuito hamiltoniano dentro de un gráfico, o el número de circuitos que se espera que existan. (Sin encontrar realmente todos los circuitos). Si ejecuto un algoritmo para encontrar todos los circuitos, ¿cuántos debería esperar encontrar, si es que hay alguno? Me parece bien una aproximación si simplifica sustancialmente los cálculos.

Si tengo un número determinado de vértices y el número medio de aristas, ¿es esta información suficiente? Cada vértice puede tener muchas aristas de salida, pero no hay dos vértices que compartan más de una arista. Además, un vértice no puede pertenecer a dos circuitos. Una vez encontrado un circuito, los vértices que lo componen se eliminan del grafo.

Mi gráfico de ejemplo tiene 10.000 vértices y cada vértice tiene tres salidas hacia otros vértices.

Y una pregunta de seguimiento: ¿Cómo podría formular la pregunta para averiguar el número medio mínimo de aristas de salida por vértice que me diera un nivel arbitrario de certeza de que encontraría al menos un circuito? Dicho de otro modo, si quiero un 50% de certeza para encontrar un circuito, y tengo 10.000 vértices, ¿cuál es el número mínimo de bordes de salida que debe tener cada vértice? (no la media, sino el mínimo real)

Tengo algunas notas en el bloc de notas donde he resuelto esto, pero realmente apreciaría la orientación de alguien más conocedor. Gracias.

Answer 1

La respuesta depende mucho de cómo se defina "gráfico cúbico aleatorio" con $n$ vértices (necesariamente $n$ es par), podemos intentar lo siguiente para encontrar los circuitos de Hamilton:

Fijar un vértice $a_1$ Elige uno de sus vecinos $a_2$ al azar. Entonces, asumiendo que tenemos $a_1a_2\ldots a_k$ con $k\ge 2$ , lanza una moneda para decidir cuál de los otros dos (es decir $\ne a_{k-1}$ ) vecinos de $a_k$ para elegir como $a_{k+1}$ y continuar. Puede ser adecuado asumir que $a_ka_{k+1}$ puede ser cualquiera de los $3(n-k)$ aristas a un "nuevo" vértice, o cualquiera de los $k-3$ aristas aún no utilizadas a uno de los vértices $a_2,\ldots, a_{k-2}$ o cualquiera de los dos bordes no utilizados para $a_1$ . Esto nos hace suponer que la probabilidad de alcanzar un nuevo vértice es $\frac{3(n-k)}{3(n-k)+(k-3)+2}=1-\frac{k-1}{3n-2k-1}$ . Y cuando $k=n$ la probabilidad de volver con éxito a $a_1$ es $\frac{2}{n-1}$ . Esto sugiere que hay alrededor de $$\tag13\cdot 2^n\cdot\prod_{k=2}^{n-1}\frac{3(n-k)}{3n-2k-1}\cdot \frac2{n-1}=3^{n-1}2^{n+1}(n-2)!\frac{(3n/2-3)!\cdot 2^{3n/2-3}}{(3n-5)!\cdot (n/2)!\cdot2^{n/2}}\cdot\frac1{n-1}$$ Ciclos de Hamilton.

O: Hay $\frac12(n-1)!$ Ciclos de Hamilton en el gráfico completo $K_n$ . Para cada una de ellas, la probabilidad de que la primera arista esté también en $G$ es $\frac3{n-1}$ para las aristas posteriores, la probabilidad de que la arista esté en $G$ , dado que el borde anterior está en $G$ es $\frac{2}{n-2}$ ; deberíamos hacer una consideración especial para la arista final, pero ignórala. Con este ciclo Hamilton de $K_n$ también está en $G$ con probabilidad $\frac3{n-1}\cdot\left(\frac2{n-2}\right)^{n-1}$ , lo que da un número total esperado de $$\frac12(n-1)!\cdot \frac3{n-1}\cdot\left(\frac2{n-2}\right)^{n-1}=\frac{3\cdot 2^{n-2}\cdot (n-2)!}{(n-2)^{n-1}}$$ Ciclos de Hamilton. Con Stirling, esto se simplifica a $$\tag2\approx {3\cdot \left(\frac 2e\right)^{n-2}\sqrt{\frac{2\pi}{n-2}}}\approx 0.$$

O bien: Si eliminamos una arista al azar de un grafo cúbico, obtenemos dos vértices de grado $2$ que se puede sustituir por una arista que conecte directamente a sus vecinos, con lo que se obtiene un gráfico cúbico con dos vértices menos. Sin embargo, este paso puede haber producido una arista doble, en cuyo caso podemos eliminar una de las aristas, obteniendo de nuevo vértices de grado dos, que pueden ser eliminados. Esto podría repetirse, pero para grandes $n$ podemos considerar que cada uno de estos casos especiales es raro. Así, los circuitos Hamilton de $G$ que no utilizan una arista concreta se corresponden con los circuitos Hamilton de un grafo cúbico más pequeño. Para un vértice fijo $a_0$ cada circuito Hailton evita precisamente una de las tres aristas incidentes. Por lo tanto, esto sugiere que el número esperado de circuitos para un $n$ -cúbico de vértices son esencialmente $3$ veces el número esperado del número de circuitos en un $(n-2)$ -de vértices del gráfico cúbico, por lo que su recuento debe ser $$\tag3 \sim 3^{n/2}.$$

Ahora que he obtenido heurísticamente (!) tres resultados totalmente diferentes, parece que esta respuesta debería considerarse más bien como un comentario sobredimensionado - suspiro.