0
$\begingroup$

$N$ towns are given, which we can get to by passing through the northern and southern gates. If you enter a town through a gate, you have to use another gate to leave the town. The merchant would like to plan his journey in such a way that starting from any town, he visits all towns exactly once and returns to the starting town.

The connection network of towns is given as a list of tuples $G$ (towns are numbered from $0$). The i-th tuple contains two lists: the first list contains the numbers of towns that can be reached from the i-th town via the i-th town's northern gate, the second one - similarly, only with the southern gate. It is guaranteed that we will be able to get to at least one city from each gate.

When you travel to a city, you have to go through this gate, from which we can get to the city you came from.

For example for $G=[([1],[2]),([2],[0]),([0],[1])]$ if we want to get from city $0$ to city $1$, we have to go through the north gate in city $0$ (because $1$ is in the first list in the tuple) and we have to go through the south gate in city $1$ (because the number of the city we came from - $0$, is in the second list in the tuple)

I need to find an algorithm that, given a list $G$, returns a list of the numbers of the cities visited consecutively by the merchant (or None if no such route is possible).

Example:

G = [ ([1], [2, 3, 4]),    
 ([0], [2, 5, 6]),        
 ([1, 5, 6], [0, 3, 4]),    
 ([0, 2, 4], [5, 7, 8]),    
 ([0, 2, 3], [6, 7, 9]),    
 ([1, 2, 6], [3, 7, 8]),    
 ([1, 2, 5], [4, 7, 9]),    
 ([4, 6, 9], [3, 5, 8]),    
 ([3, 5, 7], [9]),    
 ([4, 6, 7], [8]) ]

the result is the list [ 0, 1, 5, 7, 9, 8, 3, 2, 6, 4 ]

The first thing that popped into my head, because it is quite obvious, is that this is a Hamiltonian cycle problem (because we have to visit each vertex of the graph exactly once and return to the starting vertex). However, the condition related to gates indicates that we are dealing with a directed graph (at least that's what I think), which complicates things.

Would anyone have an idea how to solve this problem in a reasonable time (I know the Hamiltonian cycle problem is NP-complete, but suppose the number of vertices is not large)?

$\endgroup$
2
  • $\begingroup$ When I enter a city, I need to know the gate from which I entered, so that I can choose the other gate to leave. But $G$ specifies only the exiting gates of the cities we're leaving. It doesn't specify the gates of the destination cities when we enter from a specific road. Do we assume that when leaving from the northern gate of a town, you enter the next town also from its northern gate, so then you need to use the southern gate to move further? $\endgroup$
    – frabala
    May 16 at 17:27
  • $\begingroup$ yeah, I misunderstood the assignment, I edited the question. $\endgroup$
    – PK96
    May 18 at 18:04

1 Answer 1

1
$\begingroup$

You can introduce a network $G_{new}$ such as follows:

For each vertex i (or town) in G introduce two vertices $i'$ (for north gate) and $i''$ (for south gate) which are connected to each other; i.e. There exist both arcs $i'i''$ and $i''i'$. Moreover, if we can move between $i$ and $j$ from northern gate of vertex $i$ then add $i'j'$ and $i'j''$ arcs and if we can move between $i$ and $j$ from southern gate of vertex $i$ then add $i''j'$ and $i''j''$ arcs.

Now, it is sufficient to introduce a Hamiltonian cycle on $G_{new}$, where for all vertices $i'$ and $i''$, we should traverse exactly one of the arcs $i'i''$ or $i''i'$; e.g. add the constraint $X_{i'i''}+X_{i''i'}=1$ to an optimization model of the Hamiltonian cycle problem.

$\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.