FM - Decision 1 - 4) Route inspection

Question 1

Definition of an Eulerian graph

Answer 1

• A connected graph with all even vertices
• Contains a trail that includes every edge and starts and finishes at the same vertex

Question 2

Definition of a semi-Eulerian graph

Answer 2

• A connected graph with exactly two odd vertices
• Contains a trail that includes every edge and starts and finishes at the two different odd vertices

Question 3

Way to find the length of the shortest route in a network that traverses every arc at least once and returns to its starting point

Answer 3

• If all vertices are even, length = total weight of network
• If exactly two odd vertices, length = total weight of network + length of shortest path between the two odd vertices
• If more than two odd vertices, length = total weight of network + lengths of shortest paths of the pairings of odd vertices (consider all possibilities)