Me parece que la respuesta debería ser $n!$ . Ya que puedes seleccionar primero el primer vértice, y luego seleccionar cada vértice restante hasta que los tengas todos en una permutación.
Mi libro de texto, sin embargo, dice que la respuesta es $(1/2)(n-1)!$
Desgraciadamente, no explica el porqué de esto. ¿Por qué?
La respuesta depende realmente de cómo pensemos que dos ciclos hamiltonianos son iguales. Tomemos $K_3$ como ejemplo. Llamemos a sus vértices $1$ , $2$ y $3$ . Entonces, ¿consideramos $1\to2\to3\to1$ lo mismo que $2\to3\to1\to 2$ ? En caso afirmativo, $1\to2\to3\to1$ es lo mismo que $2\to3\to1\to 2$ que es lo mismo que $3\to1\to2\to 3$ en $K_3$ . Entonces tendremos dos ciclos hamiltonianos $1\to 2\to3\to1$ y $1\to 3\to 2\to1$ . Además, si consideramos $1\to 2\to3\to1$ y $1\to 3\to 2\to1$ siendo la misma porque la segunda se obtiene invirtiendo el sentido de la primera, entonces tenemos un solo ciclo hamiltoniano en $K_3$ .
En general $K_n$ Es lo mismo. $1\to2\to\cdots\to n\to1$ es lo mismo que $2\to\cdots\to n\to1\to 2$ es el mismo que.... $n\to1\to 2\to\cdots \to n$ . Y el $1\to 2\to\cdots\to n\to1$ y $1\to n\to\cdots\to2\to1$ siendo la misma porque la segunda se obtiene invirtiendo el sentido de la primera. Así que tenemos en total $\frac{1}{2}(n-1)!$ Ciclos hamiltonianos en $K_n$ .
Sólo traer todos los números similares relacionados de los circuitos hamiltonianos en los gráficos completos con la posible interpretación intuitiva de ellos:
Total de circuitos hamiltonianos (no distintos) en el gráfico completo $K_n$ es $(n-1)!$
Esto se deduce del hecho de que partiendo de cualquier vértice tenemos $n-1$ aristas para elegir el primer vértice, $n-2$ aristas para elegir el segundo vértice, $n-3$ para elegir el tercero y así sucesivamente. Siendo estas elecciones independientes, obtenemos $(n-1)!$ número posible de opciones.
Número de circuitos hamiltonianos distintos no unidos por aristas en un grafo completo $K_n$ es $\frac{(n-1)!}{2}$
El número anterior ( $(n-1)!$ ) se divide por $2$ , porque cada circuito hamiltoniano se ha contado dos veces (en sentido inverso de cada uno como estos: $A\rightarrow B \rightarrow C \rightarrow A$ y $A\rightarrow C \rightarrow B \rightarrow A$ ).
Número de circuitos hamiltonianos disjuntos en un gráfico completo $K_n$ donde $n$ es impar es $\frac{n-1}{2}$
Podemos realizarlo disponiendo los vértices dentro del círculo de la siguiente manera: 
Sólo hay una arista que conecta dos vértices en la mitad superior de la circunferencia. Cada una de estas aristas puede dar lugar a un único circuito hamiltoniano disjunto de aristas. Podemos girar este circuito de manera que esta arista sea asignada al siguiente par de vértices en la mitad superior de la circunferencia, lo que conducirá al siguiente circuito hamiltoniano de arista única disjunta. Hay $\frac{n-1}{2}$ tales pares consecutivos en la mitad superior de la circunferencia con $\frac{n-1}{2}$ aristas que las conectan, cada una de las cuales da lugar a circuitos hamiltonianos disjuntos de aristas únicas.
Ya veo por qué lo piensas. Para n=5 (digamos a,b,c,d,e) hay de hecho n! permutaciones únicas de esas letras.
Sin embargo, el número de ciclos de un gráfico es diferente del número de permutaciones en una cadena Debido a los duplicados, hay muchas permutaciones diferentes que generan el mismo ciclo idéntico.
Hay dos formas de duplicados:
En primer lugar, en un ciclo no hay un lugar de inicio y de finalización. Eso significa que la permutación a-b-c-d-e generaría el mismo ciclo que b-c-d-e-a, c-d-e-a-b, d-e-a-b-c y e-a-b-c-d. Fíjate que hay n recorridos duplicados en lo anterior, de ahí viene el (n-1)! en lugar de n!
Segundo, en un ciclo, dirección no importa. Eso significa que las permutaciones a-b-c-d-e y e-d-c-b-a generarían el mismo ciclo. Para cada permutación, hay exactamente una permutación que es su inversa. De ahí viene el /2.
Por lo tanto, (n-1)!/2 ciclos únicos.
La forma más fácil de ver esto es dibujar todos los posibles hamiltonianos como figuras - bastante fácil de hacer para K4 digamos. Entonces te darás cuenta de que de los 8 dibujados, algunos están realmente duplicados.. sólo hay 3.
¡Supongo que si hicieras esto para K5, etc., obtendrías un patrón cuya respuesta sería 1/2(n-1)!
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
