Dado $K_n$ definir secuencia $S_4$ escribiendo todos los vértices en el orden de recorrerlo por el círculo de Euler
Cuántos ciclos Hamilton distintos hay en esta secuencia $S$ ?
Respuestas
¿Demasiados anuncios?
Sin duda puede variar. Como un camino Eulerean utiliza todos $\frac{n(n-1)}{2}$ aristas y una trayectoria hamiltoniana utiliza $n$ no puedes tener más de $\frac{n-1}{2}$ . ¿Puedes tener tantos? No hay caminos eulereos si $n$ es par y $>2$ . Dependiendo de su definición, puedo definir una trayectoria euleareana que no tenga ningún segmento que sea hamiltoniano
Alex Bolotov
Puntos
249
La pregunta no parece muy precisa.
En cualquier caso,
Es bien conocido que $K_{2k+1}$ puede descomponerse en $k$ ciclos hamiltonianos.
Así que podemos encontrar un recorrido de Euler con exactamente $\dfrac{n-1}{2}$ ciclos hamiltonianos para impar $n$ .
Incluso para $n$ podemos hacer un "recorrido incompleto" con $\dfrac{n}{2}-1$ (Véase el enlace anterior) ciclos hamiltonianos.
Dave
Puntos
217
No hay necesariamente cualquier Ciclos hamiltonianos en su secuencia.
Como Ross ya ha señalado, siempre $n$ es par y $n > 2$ entonces todos los vértices tienen grado impar y no existe ningún circuito euleriano. Por tanto, sólo tenemos que preocuparnos de cuándo $n$ es impar y $n > 3$ .
Para $K_5$ dispuesto como en la imagen, un circuito euleriano sin ciclos hamiltonianos viene dado por
$$1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 5 \rightarrow 4 \rightarrow 1 \rightarrow 5 \rightarrow 3 \rightarrow 1.$$
Supongamos $K_{n-2}$ tiene un circuito euleriano sin ciclos hamiltonianos. Primero etiquete los vértices de $K_n$ como $1, \ldots, n$ . Nuestro circuito euleriano sin ciclos hamiltonianos para $K_n$ se obtiene viajando primero $1 \rightarrow 2$ entonces recorriendo el circuito euleriano sin ciclos hamiltonianos para $K_{n-2}$ a través de los vértices $2, \ldots, n-1$ llegando de nuevo a $2$ . Entonces para $k = 2, 4, 6, \ldots, n - 3$ Viajamos $$k \rightarrow n \rightarrow k + 1 \rightarrow 1 \rightarrow k + 2.$$ Por último, viajamos $n-1 \rightarrow n \rightarrow 1.$
Por inducción se deduce que $K_n$ contiene un circuito euleriano sin ciclos hamiltonianos para todos los impar $n$ .
