Hamiltonian Paths and Cycles (Extension) (VCE SSCE General Mathematics): Flashcards
📚Flashcards
Practise the cards
10 cards from this deck
ShowHide
Practise the cards
10 cards from this deck
Focus of Hamiltonian concepts
Focus of Hamiltonian concepts
Vertices (points in a graph)
Hamiltonian path definition
Hamiltonian path definition
Route visiting each vertex exactly once
Hamiltonian cycle definition
Hamiltonian cycle definition
Visits all vertices once, returns to start
Eulerian vs Hamiltonian key difference
Eulerian vs Hamiltonian key difference
Eulerian: edges; Hamiltonian: vertices
Hamiltonian path: must use all edges?
Hamiltonian path: must use all edges?
No, only needs to visit all vertices
Hamiltonian cycle: must use all edges?
Hamiltonian cycle: must use all edges?
No, only needs to visit all vertices
Test for Hamiltonian path/cycle existence
Test for Hamiltonian path/cycle existence
No simple test; use trial and error
Hamiltonian path real-world application
Hamiltonian path real-world application
Road trip visiting locations once, no return
Hamiltonian cycle real-world application
Hamiltonian cycle real-world application
Delivery routes returning to start point
What Hamiltonian cycle forms
What Hamiltonian cycle forms
A closed loop or circuit