The Route Inspection Algorithm (Edexcel A-Level Further Mathematics): Flashcards
📚Flashcards
Practise the cards
10 cards from this deck
ShowHide
Practise the cards
10 cards from this deck
Alternative name for Route Inspection Algorithm
Alternative name for Route Inspection Algorithm
Chinese Postman Problem
What does Route Inspection Algorithm find?
What does Route Inspection Algorithm find?
Shortest closed path visiting every edge at least once
When is a graph Eulerian?
When is a graph Eulerian?
All vertices have even degrees
Number of odd-degree vertices in any graph
Number of odd-degree vertices in any graph
Always an even number
Criterion for optimal pairing selection
Criterion for optimal pairing selection
Minimises total weight of added paths
Why duplicate edges in Route Inspection?
Why duplicate edges in Route Inspection?
Make all vertices have even degrees
How to calculate total route distance
How to calculate total route distance
Sum of original edge weights + sum of added edge weights
What structure results after duplicating edges?
What structure results after duplicating edges?
Eulerian circuit
First step in Route Inspection Algorithm
First step in Route Inspection Algorithm
Check vertex degrees, identify odd vertices
Real-world applications of Route Inspection
Real-world applications of Route Inspection
Postal routes, garbage collection, street cleaning