4
$\begingroup$

(this question is about trying to use some combinatorics to simplify an algorithm and save memory)
Let $K_{2n+1}$ be a complete undirected graph on $2n+1$ vertices. I would like to generate a Eulerian circuit of this graph (visit each edge exactly once).

One solution is to run the DFS-based algorithm that can find a Eulerian circuit in any Eulerian graph (a graph with all vertices of even degree).

However, I'm hoping it's possible to use the nice structure of $K_{2n+1}$ to avoid constructing the graph and running the algorithm. Is there a way to construct one such circuit in O(n) time with O(1) memory?

Motivation: The motivation behind this is an algorithm which receives a list L and needs to calculate $B(A(x), A(y))$ for each unordered pair ${x,y}$ of distinct elements of L (I'm only considering unordered pairs since $B(u,w)=B(w,u)$). The result of operation A is very large and takes almost half of the available memory. Such a circuit will allow me to minimize the number of calls to operation $A$.

Note: This is a sort of "undirected" version of generating a de-Bruijn sequence. I once heard it's possible to generate a de-Bruijn sequence with constant memory, but I don't know how to do that.

$\endgroup$
5
$\begingroup$

Yes it is possible.

Number the vertices $1,2, \dots 2n+1$.

Consider the sequence $1, 2n, 2, 2n-1, 3, 2n-2, \dots, n,n+1$, ignore $2n+1$ at the moment.

This gives a hamiltonian path in $K_{2n}$.

Now add $1$ to each vertex $\mod 2n$, to get $2,1,3,2n,4, 2n-1 \dots, n+1, n+2$. This can be visualized as writing the numbers $1,2, \dots, 2n$ in a circle and rotating the path. (see figure below).

Repeat this process of adding $1$, $n$ times. This gives you a set of $n$ edge-disjoint hamiltonian paths in $K_{2n}$. (We can show that by proving that (wlog) $1$ is first adjacent to $2n$, then $2,3$, then $4,5$ etc)

To each of these paths, add $2n+1$ at the end and join back to the first vertex of the path.

This gives you an Euler tour of $K_{2n+1}$ which starts and ends at vertex $2n+1$.

This can be computed in constant memory.

Note that this basically follows the (classic/folklore) construction that $K_{2n+1}$ can be decomposed into $n$ edge-disjoint Hamiltonian cycles. See this for instance, Modern Graph Theory, page 16.

In case that book is not accessible, here is a snapshot of the relevant part of that page:

alt text

$\endgroup$
0
$\begingroup$

That is a very nice and simple algorithm!

If someone is interested I implemented a python version that you can find on GitHub. I also implemented a tour that is (probably) not optimal for even sized cliques (for a $n$ node graph, $n/2$ edges appear twice). For now the code looks like this:

def build(n):
    if n % 2 == 0:
        return almost_eulerian(n)
    else:
        return eulerian(n)

def eulerian(n):
    middle = (n-1)//2
    path_shape = [ u for i in range(middle) for u in (i,n-2-i) ]
    hamiltonian_paths = []

    # Increment the path shape to "rotate" the hamiltonian path 
    for i in range(middle):
        hamiltonian_paths += [ (path_shape[p]+i)%(n-1) for p in range(len(path_shape)) ]
        hamiltonian_paths += [n-1] # Everything is rotated, this node is here to make a junction from one hamiltonian path to the next

    # Close the tour
    hamiltonian_paths += [hamiltonian_paths[0]]
    return hamiltonian_paths

def almost_eulerian(n):
    path_shape = [ u for i in range(n//2) for u in (i,n-1-i) ]
    hamiltonian_paths = []
    for i in range(n//2):
        path = [ (path_shape[p]+i)%n for p in range(len(path_shape)) ]
        hamiltonian_paths += path
    hamiltonian_paths += [hamiltonian_paths[0]]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.