hamiltonian.H File Reference

Hamiltonian sufficiency testing for graphs. More...

#include <tpl_graph.H>

Include dependency graph for hamiltonian.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >
	Tests Ore's sufficient condition for Hamiltonian graphs. More...
class	Aleph::Test_Dirac_Condition< GT, SN, SA >
	Tests Dirac's sufficient condition for Hamiltonian graphs. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Hamiltonian sufficiency testing for graphs.

This file provides algorithms to test sufficient conditions for a graph to contain a Hamiltonian cycle. A Hamiltonian cycle visits every vertex exactly once and returns to the starting vertex.

Definitions

• Hamiltonian Cycle: A cycle visiting every vertex exactly once
• Hamiltonian Path: A path visiting every vertex exactly once
• Hamiltonian Graph: Contains a Hamiltonian cycle

Ore's Theorem (Sufficiency Condition)

For an undirected simple graph G with n ≥ 3 vertices: If for every pair of non-adjacent vertices u and v, deg(u) + deg(v) ≥ n, then G is Hamiltonian.

Note

This tests sufficiency, not necessity. A graph may be Hamiltonian without satisfying Ore's condition.

Complexity

Operation	Time
Sufficiency test (undirected)	O(V²)
Sufficiency test (directed)	O(V² + E)

Usage Example

List_Graph<Node, Arc> g;
// ... build complete graph K5 ...
 
Test_Hamiltonian_Sufficiency<decltype(g)> test;
if (test(g))
  std::cout << "Graph satisfies Ore's condition (is Hamiltonian)\n";

See also

eulerian.H Eulerian path/cycle detection

tpl_find_path.H Path finding algorithms

Author

Leandro Rabindranath León

Definition in file hamiltonian.H.