World's most popular travel blog for travel bloggers.

[Solved]: Given the same set of nodes, why is it (generally) easier to find a Euler cycle than a Hamilton cycle?

, , No Comments
Problem Detail: 

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.

Asked By : user11964

Answered By : Peter de Rivaz

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19026

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback