3
$\begingroup$

I meet a problem but when I google, there are all Hamiltonian Path Problem: How to find a path to visit every node in directed graph(not necessarily once)?

This problem is different from Hamiltonian Path.

For example:

1 --> 2 -->  3 ↔ 4 
             ↕ 
             5

I have a path $1\rightarrow 2\rightarrow3\rightarrow4\rightarrow3\rightarrow5$ to visit all nodes in this graph, however this graph has no hamiltonian path.

My questions:

  1. What's the terminology of this problem?

  2. Is there algorithm or theorem to determine whether a general graph has such path? If a graph has such graph, how to find the detailed path?

Thanks

$\endgroup$
1
  • $\begingroup$ Its important to note that not always there is such a path (try to think of an example, after you read D.W's answer). However, in the case there is one, D.W 's algorithm is guaranteed to find it. $\endgroup$
    – nir shahar
    Apr 23, 2021 at 17:27

3 Answers 3

3
$\begingroup$

You probably haven't found anything in your searches because this problem is fairly easy to solve, without needing any fancy methods.

If the graph is strongly connected, then it is easy. Let $s$ be the starting node. Pick any vertex $v$ you haven't visited yet, and append a path $s \leadsto v$ followed by some path $v \leadsto s$ (both must exist, since the graph is strongly connected). Repeat, appending to the end of the path, until every vertex has been visited.

If the graph isn't strongly connected, decompose it into a dag of scc's. Then you can reduce the problem to finding a path through this dag (within a scc, use the algorithm of the first paragraph). You can find a path to visit every node in a dag iff the dag is itself a path, i.e., it has the structure $v_1 \to v_2 \to \dots \to v_k$, and then it is trivial to write down this path.

This is not a Hamiltonian path, since it may visit the same vertex multiple times.

$\endgroup$
4
  • $\begingroup$ You should add that this is not exactly the construction of a Hamiltonian path, since you could visit the same vertex multiple times (though it seems to answer OP's question). $\endgroup$
    – Nathaniel
    Apr 23, 2021 at 7:38
  • $\begingroup$ @Nathaniel, good point. Done. $\endgroup$
    – D.W.
    Apr 23, 2021 at 7:38
  • $\begingroup$ Cool! Thanks for your solution. Another question: If every edge has positive weight, I want to find a shortest such path, can I also have an efficient algorithm? $\endgroup$
    – maplemaple
    Apr 23, 2021 at 7:39
  • 1
    $\begingroup$ @maplemaple, no, by reduction from the Hamiltonian path problem (consider the case where all edges have weight 1). This site isn't intended for interactive use or follow-up questions, so if you'd like a more detailed answer, please try to work out why based on this hint, and if you can't figure it out, ask a new question with the 'Ask Question' button. $\endgroup$
    – D.W.
    Apr 23, 2021 at 7:42
2
$\begingroup$

If you are allowed to visit vertices more than once, many graph theorists use the term walk instead of path, i.e., a path is a walk where each vertex is visited only once (others use the pair path and simple path for walk and path).

The shortest walk visiting every vertex may be called a Hamiltonian walk (see MathWorld), although this notion is not nearly as widely known as Hamilton paths. As a consequence a graph is Hamiltonian if and only if it has a Hamilton walk and this walk has length $n$ (number of vertices) and thus finding a Hamiltonian walk is also hard (as apposed to a walk of arbitrary length).

$\endgroup$
2
$\begingroup$

I think what you're looking for, like I was, is the Minimum Spanning Tree. Here is an article about it.

$\endgroup$
1
  • $\begingroup$ The graphs in this question are directed, so "tree" might not be appropriate, but "spanning (closed) walk" is a good suggestion! $\endgroup$ Jul 12, 2021 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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