中国邮递员或路线检查|第1套（简介）

中国邮递员问题 是 欧拉电路 无向图的问题。欧拉回路是一个封闭的行走，一旦开始和结束位置相同，它就会覆盖每条边。定义了连通无向图的中国邮递员问题。问题是找到至少访问一次图的每条边的最短路径或回路。

如果输入图包含欧拉回路，则问题的解决方案是欧拉回路 无向连通图有欧拉圈如果“ 所有顶点都有偶数阶 “.

不管图是加权的还是未加权的，中国邮递员路线始终与欧拉回路相同（如果存在）。在加权图中，邮递员行程的最小可能权重是通过欧拉回路得到的所有边权重之和。我们不能走更短的路线，因为我们必须至少参观一次所有的边缘。

如果输入图不包含Euler回路 在这种情况下，任务简化为以下内容。 1） 在无权图中，使给定图转化为欧拉圈图所需的最小复制边数。

2） 在加权图中，要复制的边的最小总权重，使给定的图转化为具有欧拉圈的图。

Algorithm to find shortest closed path or optimal Chinese postman route in a weighted graph that maynot be Eulerian.step 1 : If graph is Eulerian, return sum of all          edge weights.Else do following steps.step 2 : We find all the vertices with odd degree step 3 : List all possible pairings of odd vertices           For n odd vertices total number of pairings          possible are, (n-1) * (n-3) * (n -5)... * 1step 4 : For each set of pairings, find the shortest          path connecting them.step 5 : Find the pairing with minimum shortest path          connecting pairs.step 6 : Modify the graph by adding all the edges that           have been found in step 5.step 7 : Weight of Chinese Postman Tour is sum of all          edges in the modified graph.step 8 : Print Euler Circuit of the modified graph.          This Euler Circuit is Chinese Postman Tour.   

插图：

               3        (a)-----------------(b)     1 /  |                  |  1      /   |                  |        (c)  | 5               6|   (d)         |                  |   /     2   |         4        |  /1        (e)------------------(f)As we see above graph does not contain Eulerian circuitbecause is has odd degree vertices [a, b, e, f]they all are odd degree vertices . First we make all possible pairs of odd degree vertices[ae, bf], [ab, ef], [af, eb] so pairs with min sum of weight are [ae, bf] :ae = (ac + ce = 3 ),  bf = ( bd + df = 2 ) Total : 5We add edges ac, ce, bd and df to the original graph andcreate a modified graph.

Optimal chinese postman route is of length : 5 + 23 = 28 [ 23 = sum  of all edges of modified graph ]Chinese Postman Route :  a - b - d - f - d - b - f - e - c - a - c - e - a This route is Euler Circuit of the modified graph. 

参考资料： https://en.wikipedia.org/wiki/Route_inspection_problem http://www.suffolkmaths.co.uk/pages/Maths%20Projects/Projects/Topology%20and%20Graph%20Theory/Chinese%20Postman%20Problem.pdf

本文由 尼桑·辛格 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。