On Sat, 14 Oct 2017, david.coud...@inria.fr wrote:
I took some more time to thought about the will of unifying these behaviors
(which is a good idea) and I now
believe it is not a good idea to use the same method / term to check if the
graph has a hamiltonian cycle
or a hamiltonian path. Doing so, we are making methods more complicated and
introduce confusion. For
instance, the 'backtrack' algorithm is for path only, so why should it be
associated to a method for
checking if the graph has a hamiltonian cycle ?
OK, but then I suggest we also add is_semi_eulerian() and deprecate
path-parameter in is_eulerian().
The Wikipedia page about Hamiltonian graphs gives the following definitionsr:
* A graph that contains a Hamiltonian cycle is called a Hamiltonian graph.
* A graph that contains a Hamiltonian path is called a traceable graph.
Common names should always be mentioned as aliases in the docstring.
It seems that "traceable graph" is more common (by googling), but then it
seems very natural to have is_eulerian/is_semi_eulerian and
is_hamiltonian/is_semi_hamiltonian. Opinions?
Furthermore, one can also find in some articles the notion of "semi-hamiltonian
graph": A graph is
semi-hamiltonian if it contains a hamiltonian path but no hamiltonian cycle.
Duh. And then there is the concept of hypohamiltonian.
--
Jori Mäntysalo
