Hamiltonian and Semi-Hamiltonian Graphs Lecture

Introduction

• Hamiltonian Graphs: Focus on vertices.
  • The goal is to visit every vertex exactly once and return to the starting vertex, forming a closed path.
• Semi-Hamiltonian Graphs: Similar to Hamiltonian but do not return to the starting vertex, forming an open path.

Comparison with Eulerian Graphs

• Eulerian and Semi-Eulerian Graphs: Focus on edges.
  • You cannot repeat edges.
  • Eulerian Graph: Can traverse the entire graph using every edge exactly once and return to the start.

Example Exploration

• Attempted path: A → B → H → G → D → E → F → A
  • Missed vertex C.
• Alternate attempt: C → B → H → D → E → F → A
  • Visited all vertices but did not return to the start.

Analysis

• The graph discussed is a Semi-Hamiltonian Graph because it uses an open path visiting every vertex once.
• There is no simple method to test for a Hamiltonian graph.
  • Requires checking all permutations of vertex paths to find a closed path using each vertex once.
  • Could create a computer program to test all combinations.

Creating a Hamiltonian Graph

• By adding an edge, the graph becomes Hamiltonian.
• Example Hamiltonian circuit: C → B → H → G → D → E → F → A → C

Conclusion

• Determining Hamiltonian graphs is complex and lacks a straightforward mathematical method.
  • Requires exhaustive testing of vertex permutations.
• A Semi-Hamiltonian graph is simpler to identify as it only requires an open path through all vertices.