一笔画与中国邮递员问题

一、引述

一笔画问题：

• 节点可以重复走
• 边不可以重复走
• 要求把所有边都走一次

欧拉图(Euler graph)：

• 从任何节点开始，都可以一笔画

• 每一个节点都是偶数价（价数指的是从该节点能够伸出去的边的数目）

  

半欧拉图(semi-Eulerian graph):

• 只有两个节点是奇数价的，其他都是偶数价的

  

• 半欧拉图必须从一个奇数价节点开始，到另一个奇数价结束，才可以一笔画。

tip:一笔画问题中，因为途经点必须有进有出，所以途径点必须是偶数价的，由于起点和终点可以只进不出或者只出不进，所以起点和终点可以是奇数价的。

实例分析

例1：确定其为欧拉图、半欧拉图或者不是欧拉图。

a.半欧拉图

b.B-A-F-E-B-C-D-E-C

例2 一个连通图有5个节点，节点的价分别是4，6，3，p，2

a.解释一下为什么图一定不是欧拉图

b.解释一下为什么图必然是半欧拉图

c.求边的数量（用p表示）

d.画一个两个节点的图，要求其既不是欧拉图也不是半欧拉图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-K7Pg0HWG-1658797650807)(imgs/image-20220725205109029.png)]

a.看到有奇数价的节点，必然不是欧拉图

b.由握手引理可知，奇数价的节点个数必然是偶数个，因此p必为奇数，两个奇数价的节点的图为半欧拉图。

c.由握手引理可知，总价数为边数的两倍，反推边数为$ \frac {p+15} {2} $

d.两点无边不连通就不是欧拉或者半欧拉，无论怎么连边都是全欧拉或者半欧拉

注：欧拉图必然是连通图（d引例）

假如不能一笔画，引发了一个问题（中国邮递员问题）

邮局出发，走完每条路，回到邮局

欧拉图的问题是所有路径长加和问题。而半欧拉图则复杂

根据半欧拉图的定义，起点只能选择T或者Q，否则不能一笔画，那么意味着必然有一些路要重走。

解决办法：补成全欧拉图，中国邮递员问题就变成了补最少的路，使原图变成全欧拉图的问题。

握手引理告诉我们，每加一条边，肯定会有两个节点的价数上升一。可以选择补S到T和S到Q的边来使得图变成全欧拉。

补的这两条边就是邮递员要重走的边，这样就能让中国邮递员从邮局出发最后返回邮局，代价最小。

为什么选择这两条，而不是其他，补成全欧拉的边的方法不止一种，但是要选择代价最小的，也即既要给T和Q增加价数，又要保证全局路径最短，如何确定？穷举

更复杂的例子：

要求邮局设置点为A，可以发现其奇数价节点的个数为4（A、E、F、G），需要补边来敲定代价最小的重复走的路，组合有AE/FG、AF/EG、AG/EF

代价分别计算为

AE+FG = 26 + 22 =48
AF+EG = 35 + 7 = 42
AG+EF = 19 + 20 = 39

于是敲定补边AG和EF

考虑更复杂的场景：不限定起始和终止点，这样可以把图当作半欧拉图处理，只需要补一条边。

这样选择以AF两个点作为始终点，将EG两点的边作为补边重复走，即可使总代价最少。