2022黑龙江事业单位职业能力倾向测验之数量关系：如何用一笔画的原理来解决最短路径问题

在行测考试有一些数学题目是给定的图形能不能一笔画的问题，其实这些就是来源于著名的七桥问题。下面给大家介绍一下什么叫七桥问题，18世纪，东普鲁士的首府哥尼斯堡普莱格尔河横贯城区，这条河有两条支流，在城中心汇成大河，在河的中央有两座美丽的小岛。人们漫步于这七座桥之间，久而久之，就形成了这样一个问题：能不能既不重复又不遗漏的一次相继走遍这七座桥呢?对于这一看似简单的问题，没有人能符合要求的从这座桥上走一遍。这就是闻名遐迩的“哥尼斯堡七桥问题”。

七桥问题抽象出来，把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。并由此得到了如下图所示的几何图形。若我们分别用A、B、C、D四个点表示为哥尼斯堡的四个区域。这样著名的“七桥问题”便转化为是否能够用一笔不重复的画出过此七条线的问题了。

使得一个图形可以一笔画，必须满足如下两个条件：

(1)图形必须是连通的。

(2)图中的“奇点”个数是0个或2个。

奇点是指从一个点所引出的线(包括直线，曲线)有奇数条。上图中点A有3条线，A点是奇点，点B有5条线，B点是奇点，C有3条线，C点是奇点，D有3条线，D点是奇点，图中总共有4个奇点，不可能一笔画。

对于连通的图形是一笔画的又可以分成两类。

a.当奇点数是0个，无论从哪点出发都能一笔画完如下图，比如A-O-B-C-O-D-A一笔画完，再比如O-B-C-O-D-A-O一笔画完

b.当奇点数是2个，一笔画完，需要从一个奇点出发点，另一个奇点是终点，A-0-C-O-D或者D-0-C-B-O-O-A，否则无法一笔画完。

小结一下:当奇点是0时，从哪点出发都能一笔画完，当奇点数是2时可以一笔画完，但是是从奇点出发到奇点结束。从非奇点出发就不可以一笔画。如果一个连通的图形，奇点数超过了2个，想要转化成一笔画只能去让奇点变成非奇点，可以增加线条或者减少线条来改变奇点的性质转化成2个奇点或者0个奇点。

对于上图此时奇点是4个，增加或减少线条来改变奇点的个数，连接BC，就剩下两个奇点，从A点或D点出发即可一笔画完，如果再把AD连接起来，图中0个奇点，从任何一点出发即可一笔画完。

【例1】某社区道路如下图所示，社区民警早上9点整从A处的办公室出发，以每分钟50米的速度对社区内每一条道路进行巡查(要求完整走过整个社区内的每一段道路)，问他最早什么时候能完成任务返回办公室?

A.9∶54 B.9∶50 C.9∶47 D.10∶00

【答案】A。解析：从A点出发，走遍每段路，速度是恒定的，要求时间最短，只能路程之和尽可能短，能一笔画是最好的，如下图所示，因为图中点E，点D，点B，点C都是奇点共计是4个奇点，显然此图无法一笔画，因为只有增加线条(重复走某条路，)让奇点变成非奇点。A点是非奇点的，从A点出发回到A点，只能是0个奇点，所以需要增加两条线，即ED和BC，此时就是0个奇点，A-E-D-E-F-C-B-C-H-O-M-N-B-O-N-A。相当于把所有路加起来再额外加ED和BC,原来的路是三横三纵，还有NO的长度，MO=150,MN=200,根据勾股定理NO=250，横纵都是150+200=350。所以总路程就是350×6+250+150+200=2700。需要的时间就是2700÷50=54(分钟)，9∶00出发巡逻需要最短是54分钟，所以答案是A。

小结：遍历所有的路径的最短路径问题本质就是一笔画问题，注意的是从指定点出发还是任一点出发，指定的点是否又是奇点。