Hamiltonian cycle in a Graph in less than 128 words

A Hamiltonian cycle is a cycle that contains all the tops of the graph.

There is no general algorithm (i.e. valid for any graph) and effective (i.e. no algorithm in the number of computational steps or a polynome the size of the graph) to find out if there is a Hamiltonian cycle in a graph.

Hamiltonian cycle source wikipedia

DIRAC Condition: If for all the tops u of the graph G degree (u) 'n /2 then G contains a Hamiltonian cycle

ORE Condition: If for any pair u and v of non-neighbors deg(u) 'deg(v) 'then G contains a Hamiltorian cycle

If a graph verifies diraC's condition then it verifies the orE condition (the reciprocal is false).

Leave a Reply

Your email address will not be published. Required fields are marked *