Route Inspection Flashcards Preview

A Level Further Maths Decision 1 > Route Inspection > Flashcards

Flashcards in Route Inspection Deck (10)
Loading flashcards...
1

Eulerian Graph

A connected graph where all the orders are even
Traversable

2

Semi-Eulerian graph

A connected graph where exactly 2 orders are odd
Semi-traversable

3

Traversable

A graph in which it is possible to travel along every arc just once, returning to the start node and without taking your pen off the paper

4

When is a graph not traversable?

If it has more than 2 nodes with odd degree

5

Route inspection problem

Can be used to find the shortest route in a network that traverses each arc at least once and returns to its starting point

6

Route inspection problem Eulerian

The weight of the network
Sum each arc's weight, noting each down

7

Route inspection problem semi-Eulerian

The weight of the network plus the length of the shortest route between the two odd nodes

8

Route inspection algorithm

1. Write down any vertices with odd degree
2. Write down all possible combinations of vertex pairs
3. Write down the shortest route between each pair and sum to find for the combination
4. Write down the arcs in the combination with the smallest sum and add to the network

9

What to remember if an arc is removed

To take that away from the total length as well as adding the arcs traversed twice

10

What happens if you are given 2 possible end nodes?

Write out all the possible combinations of pairings from each