Chapter 4

Question 1

Define Eulerian graph

Answer 1

1. graph that contains a trail that includes every edge, start and finish node is same
2. connected graph with all nodes of even valency

Question 2

Define semi Eulerian graph

Answer 2

1. graph that contains a trail that includes every edge, start and finish node is different
2. connected graph with only 2 nodes of odd valency

Question 3

What is route inspection algorithm used for

Answer 3

Find shortest path in network that traverses every arc at least once, and returns to starting point

Question 4

Outline route inspection algorithm

Answer 4

1. Identify nodes with odd valency
2. Find sum off all possible pairings
3. Pick lowest weight combination
4. add onto weight of graph