4
$\begingroup$

To find a Hamilton cycle is a NPC problem, but Euler is not. Considering one can always transform the vertex as edge or vice versa conceptually. Then the vertex can be used to describe the information which originally edge does.

What properties make the Euler graph more easily to be resolved?

For example, in genome assembly problem, one can either consider a Kmer as vertex or edge(de bruijn graph), it's just two perspectives to look at the same thing. I think their should be additional or missing information between two kind of explanation.

$\endgroup$

marked as duplicate by Juho, Gilles Dec 16 '13 at 11:45

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from stackoverflow.com Dec 16 '13 at 3:47

This question came from our site for professional and enthusiast programmers.

2
$\begingroup$

Suppose you are trying to find a Hamiltonian cycle on a graph.

You can solve this efficiently in the manner you describe (i.e. converting vertices into edges and then solving for an Euler path) if and only if the graph is a line graph.

There are a number of characterisations of line graphs.

For example, a graph is a line graph if and only if it does not contain any of these 9 graphs below as a subgraph:

enter image description here

An alternative characterisation is that a graph is a line graph if and only if you can partition the graph into cliques such that every vertex belongs to exactly two cliques.

This characterisation is perhaps more useful as you can apply Euler's proof to these cliques.

$\endgroup$
0
$\begingroup$

Euler proved the that a connected graph has a closed path traversing every edge if every vertex is of even degree, and he proved that a connected digraph has a closed path traversing every edge if every vertex has in-degree equalling out-degree. He gave an explicit construction in both cases. The construction can be easily systematized. Others have sped the algorithm up.

$\endgroup$
  • $\begingroup$ thanks, yes, I also know the fact. I mean, for example, in genome assembly problem, one can either consider a Kmer as vertex or edge(de bruijn graph), it's just two perspectives to look at the same thing. I think their should be additional or missing information between two kind of explanation. $\endgroup$ – user11964 Dec 9 '13 at 19:52

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