Topics
Definition of the Chinese Postman Problem
A Chinese postman problem is any scenario where we're trying to find the shortest way to start and end at the same vertex and visit every edge in a graph at least once.
The name is very helpful for remembering what the problem actually is. Imagine a postman that starts at a post office at one of the vertices in the graph, and the postman has to travel along every edge, which you can imagine representing roads in a graph, to deliver mail to all the houses along all the roads. The postman must eventually return to the starting vertex, which is the post office, and wants to minimize the total distance that he has to cover.
The animation below shows a Chinese postman tour for a graph.
Definition of the Chinese Postman Problem
A Chinese postman problem is any scenario where we're trying to find the shortest way to start and end at the same vertex and visit every edge in a graph at least once.
The name is very helpful for remembering what the problem actually is. Imagine a postman that starts at a post office at one of the vertices in the graph, and the postman has to travel along every edge, which you can imagine representing roads in a graph, to deliver mail to all the houses along all the roads. The postman must eventually return to the starting vertex, which is the post office, and wants to minimize the total distance that he has to cover.
The animation below shows a Chinese postman tour for a graph.