Tuesday, 24 April 2012





       A Hamiltonian cycle in a dodecahedron. Like all platonic solids, the dodecahedron is Hamiltonian.

Hamilton path    - a simple path in a graph that passes through every vertex exactly once.
Hamilton circuit - a simple circuit in a graph that passes through every vertex exactly once and end back at the 1st vertex.
Dirac's Theorem - if graph is a simple graph with n vertices with n >=3 such that the degree of every vertex in G is at least n / 2, then G has a Hamilton circuit.
Ore's Theorem    - if graph is a simple graph with n vertices with n=> 3 such that deg(u) + deg(v) >= n
for every pair of  nonadjacent vertices U and V in graph, then the graph has a Hamilton circuit
                           (DISCRETE MATHEMATICS AND ITS APPLICATIONS by Kenneth H.Rosen)

No comments:

Post a Comment