Discrete UE Hamiltonian Paths & Circuits Review

Front

What is a Hamiltonian Path?

Back

A Hamiltonian Path is a path in a graph that visits each vertex exactly once and does not return to the starting vertex.

Front

What is a Hamiltonian Circuit?

Back

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

Front

What distinguishes a Hamiltonian Path from a Hamiltonian Circuit?

Back

A Hamiltonian Path does not return to the starting vertex, while a Hamiltonian Circuit does.

Front

What is the requirement for a graph to have a Hamiltonian Circuit?

Back

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

Front

What is the requirement for a graph to have a Hamiltonian Path?

Back

A graph must have a Hamiltonian Path if there exists a path that visits every vertex exactly once.

Front

Can a Hamiltonian Path exist in a graph with disconnected vertices?

Back

No, a Hamiltonian Path cannot exist in a graph with disconnected vertices.

Front

What is the difference between Eulerian and Hamiltonian paths?

Back

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

Front

What is an example of a real-world application of Hamiltonian Paths?

Back

Hamiltonian Paths can be used in routing problems, such as the traveling salesman problem, where a salesman must visit multiple cities.

Front

What is a necessary condition for a graph to have a Hamiltonian Circuit?

Back

There is no simple necessary condition for Hamiltonian Circuits; however, sufficient conditions include having a connected graph with at least three vertices.

Front

What is a necessary condition for a graph to have a Hamiltonian Path?

Back

A necessary condition is that the graph must be connected.