route inspection problem

Show Summary Details

Quick Reference

(in graph theory)

A postman needs to travel along each road, or edge (arc) in graph theory, while travelling the shortest possible route. If a closed Eulerian trail can be found, it must constitute the minimum possible since it requires each edge to be travelled exactly once, but most graphs do not have such a route available. The best approach is as follows. If all the vertices (nodes) are of even degree, then there will be a Eulerian trail. If exactly two of the vertices are odd, then use Dijkstra's method of solving the shortest path problem to identify the shortest path between those two vertices, and the postman will have to walk the edges on that route twice, and all other edges once. However, when more than two vertices are odd, there are various ways they could be paired off, and what is required is the minimum sum of shortest paths between the pairs. The edges on each of these shortest paths will have to be repeated.

Subjects: Mathematics.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.