Chapter 4 - Route Inspection (Chinese Postman)

Cards (6)

  • A Hamiltonian cycle is a path that passes through all vertices exactly once
  • Eularian Graph = A graph which contains a trail that includes every edge and starts + finishes at the same vertex. Every node has an even degree
  • Semi-Eularian Graph = A Graph which only 2 nodes have odd valencies, trail that includes every edge but starts and finishes at different vertices
  • All even degree = Weight of network is the weight of the shortest route
  • 2 odd degree = Total weight plus shortest path between 2 odd nodes
  • More than 2 odd nodes = Consider pairings of the 4 vertices to find the ones with the shortest extra weight. Cannot do the route inspection algorithm with more than 4 odd nodes