Introduction to the Chinese Postman Problem of finding a closed walk that visits every edge at least once. Algorithms for finding solutions in the case of an Eulerian graph, a semi-Eulerian graph, and a graph with 4 odd vertices.
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.
If a graph is Eulerian, then any Eulerian circuit is a solution to the Chinese postman problem.
Remember that an Eulerian circuit starts and ends in the same location, and visits every edge exactly once. The Chinese Postman problem looks for a circuit that visits every edge at least once, so a circuit that visits every edge exactly once is necessarily a shortest possible solution.
If a graph is semi-Eulerian, then by definition it does not have an Eulerian circuit, which means to visit every edge at least once we will have to repeat at least one edge.
We know that a semi-Eulerian graph has an Eulerian trail starting at one of the odd vertices and ending at the other. To find a solution to the Chinese Postman problem in this case, we first find an Eulerian Trail and then find the shortest possible path from the end of the trail back to its start.
In most exam scenarios, you will be asked to find the total weight of a solution and not necessarily find the Chinese postman tour itself. in the two-odd vertex scenario, the total weight of the solution will be the sum of all the weights of all the edges in the graph plus the weight of the shortest path between the two vertices of odd degree because those edges are going to have to be repeated.
In the example above, the vertices C and F both have degree 3, and they're the only ones with odd degree. The shortest path between them goes CDF with weight CD equals 5 and DF equals 5 for a total repeated weight of 10. the total weight of all the edges in the graph is 44, so the weight of the optimal solution is 44+10=54
The last case that IB exams will expect you to consider is the Chinese Postman problem when exactly four vertices are odd.
You can think of this case as an extension of the semi-Eulerian case, where two vertices were odd. In this case, we have two pairs of odd vertices so we're going to have to repeat two paths.
Consider the following graph with odd vertices A,B,C and D.
The shortest path between
A and B is 4
C and D is 6
A and C is 5
B and D is 1
A and D is 4+1=5
B and C is 1+6=7
We can pair them in 3 ways:
AB and CD, total weight 4+6=10
AC and BD, total weight 5+1=6
AD and BC, total weight 5+7=12
The smallest of these is 6, so the weight of the optimal solution is 37 (the sum of all weights in the graph) +6=43
Nice work completing Chinese Postman Problem, here's a quick recap of what we covered:
Exercises checked off
Introduction to the Chinese Postman Problem of finding a closed walk that visits every edge at least once. Algorithms for finding solutions in the case of an Eulerian graph, a semi-Eulerian graph, and a graph with 4 odd vertices.
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.
If a graph is Eulerian, then any Eulerian circuit is a solution to the Chinese postman problem.
Remember that an Eulerian circuit starts and ends in the same location, and visits every edge exactly once. The Chinese Postman problem looks for a circuit that visits every edge at least once, so a circuit that visits every edge exactly once is necessarily a shortest possible solution.
If a graph is semi-Eulerian, then by definition it does not have an Eulerian circuit, which means to visit every edge at least once we will have to repeat at least one edge.
We know that a semi-Eulerian graph has an Eulerian trail starting at one of the odd vertices and ending at the other. To find a solution to the Chinese Postman problem in this case, we first find an Eulerian Trail and then find the shortest possible path from the end of the trail back to its start.
In most exam scenarios, you will be asked to find the total weight of a solution and not necessarily find the Chinese postman tour itself. in the two-odd vertex scenario, the total weight of the solution will be the sum of all the weights of all the edges in the graph plus the weight of the shortest path between the two vertices of odd degree because those edges are going to have to be repeated.
In the example above, the vertices C and F both have degree 3, and they're the only ones with odd degree. The shortest path between them goes CDF with weight CD equals 5 and DF equals 5 for a total repeated weight of 10. the total weight of all the edges in the graph is 44, so the weight of the optimal solution is 44+10=54
The last case that IB exams will expect you to consider is the Chinese Postman problem when exactly four vertices are odd.
You can think of this case as an extension of the semi-Eulerian case, where two vertices were odd. In this case, we have two pairs of odd vertices so we're going to have to repeat two paths.
Consider the following graph with odd vertices A,B,C and D.
The shortest path between
A and B is 4
C and D is 6
A and C is 5
B and D is 1
A and D is 4+1=5
B and C is 1+6=7
We can pair them in 3 ways:
AB and CD, total weight 4+6=10
AC and BD, total weight 5+1=6
AD and BC, total weight 5+7=12
The smallest of these is 6, so the weight of the optimal solution is 37 (the sum of all weights in the graph) +6=43
Nice work completing Chinese Postman Problem, here's a quick recap of what we covered:
Exercises checked off