Hamiltonian Circuits Flashcard

Front

What is a Hamiltonian Circuit?

Back

A Hamiltonian Circuit is a path in a graph that visits every vertex exactly once and returns to the starting vertex.

Front

What is the Nearest Neighbor Algorithm?

Back

The Nearest Neighbor Algorithm is a heuristic for solving the Traveling Salesman Problem by starting at a vertex and repeatedly visiting the nearest unvisited vertex until all vertices are visited.

Front

What is a Eulerian Path?

Back

A Eulerian Path is a trail in a graph that visits every edge exactly once but may not return to the starting vertex.

Front

What is a Complete Graph?

Back

A Complete Graph is a graph in which every pair of distinct vertices is connected by a unique edge.

Front

What is the Cheapest Link Algorithm?

Back

The Cheapest Link Algorithm is a heuristic for finding a Hamiltonian Circuit by repeatedly adding the cheapest available edge that does not form a cycle until all vertices are included.

Front

What is the difference between Hamiltonian and Eulerian paths?

Back

Hamiltonian paths visit every vertex exactly once, while Eulerian paths visit every edge exactly once.

Front

What is a Tree in graph theory?

Back

A Tree is a connected graph with no cycles, where any two vertices are connected by exactly one path.

Front

What does it mean for two graphs to be Isomorphic?

Back

Two graphs are Isomorphic if there is a one-to-one correspondence between their vertices and edges that preserves the connectivity.

Front

How do you determine if a graph has a Hamiltonian Circuit?

Back

A graph has a Hamiltonian Circuit if there exists a cycle that visits every vertex exactly once and returns to the starting vertex.

Front

What is the significance of the starting vertex in Hamiltonian algorithms?

Back

The starting vertex is crucial as it determines the path taken by algorithms like Nearest Neighbor and Cheapest Link.