Graph theory - Start from vertex A, go through all paths in both directions and end up in A again the shortest way

2
votes

I am trying to find the name of this problem but don't really know how to search for it. The problem is the following:

Find the path in a graph where you start from vertex A, go through all edges exactly two times per edge in BOTH directions (one time in one direction, second time in the opposite) and end up in vertex A again as a last step.

Would love it if somebody gave me some hints as to how this problem is called (because it sounds like a well-known one) and maybe some directions for its solution.

1
c++algorithmgraphgraph-theorygraph-algorithm
I think you are describing an Eulerian cycle (en.wikipedia.org/wiki/Eulerian_path) (after splitting each edge into a pair of directed edges). However the length of any such path will be the same, namely twice the sum of the lengths of the original edges. So asking for the "shortest" such path doesn't make much sense. – stewbasic
@stewbasic: Eulerian cycles exist if and only if every vertex has even degree (undirected graph), while a path as described may exist even if there are edges with even degree (e.g. degree 1). – Lior Kogan
@LiorKogan if, as stewbasic suggests, you split each undirected edge into a pair of directed edges (since the OP requests each edge is travelled in both directions) then there will always be an equal number of inbound and outbound edges on each vertex so you can always backtrack along an edge you have just traversed (and, effectively, the total number of incident edges will always be even). – MT0
@MT0: You're right. I've missed the splitting part. – Lior Kogan

1 Answers

4
votes

If you just want to traverse each edge of a connected graph once in each direction then you can use a depth-first search:

  • Pick any vertex as the starting point.
  • From the current vertex and pick any unvisited incident edge.
    • Mark that edge as visited.
    • If the other end of the edge is an unvisited vertex then move to that new vertex, mark it as visited and then repeat the process from that new vertex.
    • If the other end of the edge is a visited vertex then immediately backtrack (traversing the edge a second time but in the opposite direction) and continue processing edges connected to the current vertex.
    • Once all incident edges to the current vertex have been visited then backtrack along the edge which initially brought you to that vertex and return to processing the edges connected to that previous vertex.

Once the DFS has completed then you will have traversed each edge exactly once in each direction.

You could equally use a breadth-first search instead of a depth-first search.

If you want to visit all the edges in a cycle (without backtracking in the middle of the path) then you are looking for an Eulerian circuit/tour and can use Hierholzer's 1873 algorithm:

Wikipedia

  • Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v. It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that, when the trail enters another vertex w there must be an unused edge leaving w. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
  • As long as there exists a vertex u that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from u, following unused edges until returning to u, and join the tour formed in this way to the previous tour.