La generación de un circuito Euleriano de un grafo completo con constante de la memoria

Question

(esta pregunta es acerca de tratar de utilizar algunos combinatoria para simplificar un algoritmo y ahorrar memoria)
Deje $K_{2n+1}$ ser un grafo no dirigido en $2n+1$ vértices. Me gustaría generar un circuito Euleriano de este gráfico (visita cada arista exactamente una vez).

Una solución es ejecutar el DFS basado en el algoritmo que se puede encontrar un circuito Euleriano en cualquier grafo Euleriano (un gráfico con todos los vértices, incluso de grado).

Sin embargo, tengo la esperanza de que es posible utilizar la agradable estructura de $K_{2n+1}$ para evitar la construcción de la gráfica y la ejecución del algoritmo. Hay un camino para la construcción de uno de estos circuitos en O(n) tiempo con O(1) de la memoria?

Motivación: La motivación detrás de esto es un algoritmo que recibe una lista L y necesidades para calcular el $B(A(x), A(y))$ por cada desordenada par ${x,y}$ de los distintos elementos de L (sólo estoy considerando la posibilidad de pares no ordenados desde $B(u,w)=B(w,u)$). El resultado de la operación es muy grande y tarda casi la mitad de la memoria disponible. Ejemplo de un circuito que me permita minimizar el número de llamadas de operación $A$.

Nota: Este es un tipo de "espontáneos" de la versión de la generación de la secuencia de Bruijn. Una vez escuché que es posible generar un de-secuencia de Bruijn con constante de la memoria, pero no sé cómo hacerlo.

Answer 1

Sí es posible.

El número de los vértices $1,2, \dots 2n+1$.

Considerar la secuencia de $1, 2n, 2, 2n-1, 3, 2n-2, \dots, n,n+1$, ignorar $2n+1$ en el momento.

Esto le da un camino hamiltoniano en $K_{2n}$.

Ahora agregue $1$ a cada vértice $\mod 2n$, para obtener el $2,1,3,2n,4, 2n-1 \dots, n+1, n+2$. Esto puede ser visualizado como la escritura de los números $1,2, \dots, 2n$ en un círculo y la rotación de la ruta. (ver figura a continuación).

Repita este proceso de adición de $1$, $n$ veces. Esto proporciona un conjunto de $n$ borde discontinuo caminos hamiltonianos en $K_{2n}$. (Podemos demostrar que la demostración de que (wlog) $1$ es la primera adyacentes a$2n$,$2,3$,$4,5$, etc)

Para cada una de estas rutas, agregar $2n+1$ al final y unirse de nuevo a la primer vértice de la ruta.

Esto le da una Euler tour de $K_{2n+1}$, que comienza y termina en el vértice $2n+1$.

Este puede ser calculado en la memoria constante.

Tenga en cuenta que esto sigue básicamente el (clásico/folklore) de la construcción que $K_{2n+1}$ puede ser descompuesto en $n$ borde discontinuo ciclos Hamiltonianos. Ver esto por ejemplo, la Moderna Teoría de grafos, página 16.

En caso de que el libro no es accesible, aquí está una foto de la parte pertinente de esa página: