Eulerian and Hamiltonian Walks (HSC SSCE Mathematics Standard): Flashcards
📚Flashcards
Practise the cards
10 cards from this deck
ShowHide
Practise the cards
10 cards from this deck
Eulerian trail
Eulerian trail
Path using every edge exactly once, diff. start/end vertices
Eulerian circuit
Eulerian circuit
Path using every edge exactly once, same start/end vertex
Condition for Eulerian trail to exist
Condition for Eulerian trail to exist
Connected graph with exactly 2 odd-degree vertices
Condition for Eulerian circuit to exist
Condition for Eulerian circuit to exist
Connected graph where all vertices have even degree
Hamiltonian path
Hamiltonian path
Path visiting every vertex exactly once
Hamiltonian cycle
Hamiltonian cycle
Hamiltonian path that returns to starting vertex
Main focus of Eulerian walks
Main focus of Eulerian walks
Edges - every edge must be used exactly once
Main focus of Hamiltonian walks
Main focus of Hamiltonian walks
Vertices - every vertex must be visited exactly once
How to identify Eulerian walks
How to identify Eulerian walks
Use vertex degree rules (count odd-degree vertices)
How to identify Hamiltonian walks
How to identify Hamiltonian walks
No simple rule - must inspect graph carefully