WikiGalaxy
Graph Hamiltonian Path and Circuit
Introduction to Hamiltonian Paths and Circuits
A Hamiltonian path in a graph is a path that visits each vertex exactly once. A Hamiltonian circuit is a Hamiltonian path that is a cycle, meaning it starts and ends at the same vertex. These concepts are fundamental in the study of graph theory and have applications in various fields such as computer science, logistics, and biology.
Example 1: Simple Hamiltonian Path
Graph Structure:
Consider a simple graph with vertices A, B, C, and D. The edges are: A-B, B-C, C-D, and D-A.
Hamiltonian Path:
One possible Hamiltonian path is A -> B -> C -> D.
// Graph representation
class Graph {
int V;
List[] adjListArray;
Graph(int V) {
this.V = V;
adjListArray = new LinkedList[V];
for (int i = 0; i < V; i++) {
adjListArray[i] = new LinkedList<>();
}
}
void addEdge(int src, int dest) {
adjListArray[src].add(dest);
adjListArray[dest].add(src);
}
boolean isHamiltonianPath() {
// Implementation to check Hamiltonian Path
return true; // Placeholder
}
}
Example 2: Hamiltonian Circuit
Graph Structure:
Consider a cycle graph with vertices A, B, C, D, and edges A-B, B-C, C-D, D-A.
Hamiltonian Circuit:
A Hamiltonian circuit can be A -> B -> C -> D -> A.
// Graph representation for Hamiltonian Circuit
class GraphCircuit {
int V;
List[] adjListArray;
GraphCircuit(int V) {
this.V = V;
adjListArray = new LinkedList[V];
for (int i = 0; i < V; i++) {
adjListArray[i] = new LinkedList<>();
}
}
void addEdge(int src, int dest) {
adjListArray[src].add(dest);
adjListArray[dest].add(src);
}
boolean isHamiltonianCircuit() {
// Implementation to check Hamiltonian Circuit
return true; // Placeholder
}
}
Example 3: Non-Hamiltonian Graph
Graph Structure:
Consider a graph with vertices A, B, C, D, and E, and edges A-B, B-C, C-D. This graph does not include all vertices in any path.
No Hamiltonian Path or Circuit:
This graph lacks a Hamiltonian path or circuit due to the disconnected vertex E.
// Graph representation for non-Hamiltonian
class NonHamiltonianGraph {
int V;
List[] adjListArray;
NonHamiltonianGraph(int V) {
this.V = V;
adjListArray = new LinkedList[V];
for (int i = 0; i < V; i++) {
adjListArray[i] = new LinkedList<>();
}
}
void addEdge(int src, int dest) {
adjListArray[src].add(dest);
adjListArray[dest].add(src);
}
boolean hasHamiltonianPath() {
// Check for Hamiltonian Path
return false; // Placeholder
}
}
Example 4: Directed Hamiltonian Path
Graph Structure:
Consider a directed graph with vertices A, B, C, and D, and directed edges A->B, B->C, C->D.
Hamiltonian Path:
A possible Hamiltonian path is A -> B -> C -> D.
// Directed graph representation
class DirectedGraph {
int V;
List[] adjListArray;
DirectedGraph(int V) {
this.V = V;
adjListArray = new LinkedList[V];
for (int i = 0; i < V; i++) {
adjListArray[i] = new LinkedList<>();
}
}
void addEdge(int src, int dest) {
adjListArray[src].add(dest);
}
boolean isHamiltonianPath() {
// Implementation to check directed Hamiltonian Path
return true; // Placeholder
}
}
Example 5: Complex Hamiltonian Circuit
Graph Structure:
Consider a complete graph with vertices A, B, C, D, and E, where each vertex is connected to every other vertex.
Hamiltonian Circuit:
A possible Hamiltonian circuit is A -> B -> C -> D -> E -> A.
// Complete graph representation
class CompleteGraph {
int V;
List[] adjListArray;
CompleteGraph(int V) {
this.V = V;
adjListArray = new LinkedList[V];
for (int i = 0; i < V; i++) {
adjListArray[i] = new LinkedList<>();
}
}
void addEdge(int src, int dest) {
adjListArray[src].add(dest);
adjListArray[dest].add(src);
}
boolean isHamiltonianCircuit() {
// Implementation to check Hamiltonian Circuit
return true; // Placeholder
}
}
