4第二章第四节图论2009.5.27改78-102

§2-4 图论模型

图论产生于哥尼斯堡（Konigsberg）七桥问题，原德国（现立陶宛）哥尼斯堡（现加里宁格勒），那里有一条河，称为普雷格尔（Pregel）河，河上有七座桥。当地人们试图沿河上每一座桥走一遍，且每一座桥只走一次再返回原出发地，但没有人能够成功。这就是被称为哥尼斯堡七桥问题的一个难题。著名数学家 Enler 将其转化为图（1736年），从而，哥尼斯堡七桥问题转化为图论上的一笔画问题。

1、基本概念及几个问题：

在图论中,由顶点集V(G) (Vertex) 以及边 E(G)(Edge),顶点之间的连线,组成的图形称为图（Graph）

图上顶点与顶点间可能有边，也可能无边，我们称为有、无关系。

图2-18

借用代数中的“关系”概念：设有

二个集合A、B，A与B的乘积为A×B=｛(x,y)∣x∈A, y∈B｝， A×B 的子集R?A×B称为 A与B的一个关系。 例如： 同学关系；师生关系 ；父子关系等。 特殊的关系有：等价关系R，满足 1. 自反性（(x,x)?R）；2. 对称性（(x,y)?R则 (y,x)?R）3. 传递性（(x,y)?R,(y,z)?R则 (x,z)?R）。

图可以表示为G(V , E)或 (V(G) , E(G) )=G或G(V , R) (R是V与V的一个关系)。

图分为有向图，对应边有方向，从而，对应的关系不满足对称性；无向图，对应边无方向。

如：集合A=｛北京、天津、上海、重庆 ｝以及二地之间的航线可得一图（图2-19）。按水路则可得另一图。

７８

图2-19

图是由顶点与部分顶点间连线组成。

例 集A=｛张三（A）、 李四（B）、王五（C）、赵六（D）｝, 张三是李四、王五的老师，赵六是李四的老师，李四是王五的学生。用图表示即图2-20。 这是一个有向图, 对应的关系R=｛(A,B), (A,C), (D,B), (B,C)｝. 图的边可用 uv （u、v 为端点）或e表示； 顶点相邻：如果二个顶点与同一条边相邻； 环边：如果一条边的二个端点重合, 图2-21中的e2；

重边：端点重合的二条边如图2-21中e3,e4； 轨道：由顶点到边到顶点┅┅最后到顶点组成的图。如v0e1v1e 2 …vn-1 en 是一个轨道； 迹（链）：边不重的轨道 （顶点可能重合）；

简单图：没有环边也没有重边的图 路（轨）：顶不重的轨道。闭合路或迹叫圈。

对于图我们只关心有、无边、是否相邻，不关心形状，即同一图可以有不同的形状，如图2-22的(a),(b)表示同一个图。

子图： 设图G1=(V(G1), E(G1 ) ) ，G2 = (V(G2) , E(G2) )，G1称为G2的子图，如果 V(G1)?V(G2) , E(G1)?E(G2)。

偶度点： 与偶数条边相邻的点；奇度点： 与奇数条边相邻的点。 2、几个问题：

1） Euler

圈

(环游)： 自图的任一点出发，每条边经过且仅经过一次再回到出发点的图；Euler图（途径）（或一笔画）：从图的任一点出发，每条边经过且仅经过一次的图；E图：每一顶点为偶点的图； E链：经过每一边的链；M图：仅有二

个奇点的图（与E链的区别：M图必有二个奇点，E链未必）。 问：Euler 圈，E图，M图是否存在？如何求出？

７９

图2-20

图2-21

图2-22

2） Hamilton 路：包含图的所有顶点的路；

Hamilton 回路（圈）： 包含图的所有顶点的圈。

3) 中国邮路问题：一邮递员从邮局出发去各街道投递信件，然后再回到邮局，每条街道至少经过一次，求一条路使其走过的路线最短。

本问题在1962年由山东大学管梅谷先生提出，所以称为中国邮路问题。 4) 货郎担问题(又名旅行售货商问题)：一货郎挑着担子走村串巷卖东西, 求一

条经过每一村的最短的路。

5） 平面图：能画在平面上且相异边不相交的图，典型的例子是房屋和井（见图2-29）。

6） 偶图与对集：二个点集，以及边是由分别与另一个集合中点相连的图。 7） 四色问题：任何一张地图，都可以用不超过四种颜色涂色使之任意相邻区

域为不同颜色。

8）最小生成树

下边分段介绍这些问题。 3、Enler图与中国邮路问题

定理2-1：图G为Euler环游（或Euler 图）的充分必要条件是连通图G中任一顶点全为偶度点。

证明：必要性：不妨设W为G的Euler环游，则每一顶点v的度数k必为偶数（Euler环游为圈）

充分性：分三步1. 若对于图G的任一顶点v， d(v)≥2 则G至少含有一个圈。

2. G由n个无公共边的圈组成

由1. G至少有一圈 K0 ， 我们从G中删去 K0 (若顶点v的度数为2，则此顶点被删去，否则不删去)， 剩下的图仍满足定理条件，故可重复上述步骤有限次，如 n-1次，则剩下一个圈Kn ,从而G由一些圈组成且每条边仅属于一个圈。

3. G为Euler 环游

设G为G1,G2?Gn 的并 （Gi由2.得到的圈）， Gi无公共边。只要证明：?1?k?n, 存在闭路w恰含k个圈。

用归纳法 若k=1 明显为Euler环游，取w=G1即可。

设 1≤k≤n时G为Euler环游，即存在闭途径w?包含k个圈。由于G为连通图，故在剩余的n-k个圈中必含有一个圈C, 与w?有公共顶点（否则将不连通），不妨设有相同的起点（且为终点），于是 w=w?∪C 恰含{Gi} 中k+1个圈。

推论：（一笔画定理） 一个连通图G为Euler途径（即一笔画成）的充要条件是它

８０

图2-23

至多含有二个奇度点。

证明：充分性 若去掉二个奇度点间的一条路经（如图2-24）则图为Euler环游，不妨设该环游从其中一个奇度点出发且回到该奇度点，再沿去掉的一条边到另一个奇度点，即知该图为Euler途径。

必要性 若G为Euler环游，则由定理知每个顶点为偶度点。否则，设u0, v0为Euler途径的起止点，则G+u0v0有Euler 途径，从而仅有u0, v0为奇度点。

例7：七桥问题

可化为图2-18，由于A,B,C,D皆为奇度点，故不能一笔画成。

另外图2-25中的（a）,(c)是Euler途径，(b)不是Euler途径

定理2-2： 若图G有2k个奇度点，则该图可以用k笔画成。

例8在一个晚会上握过奇数次手的人的个数是偶数。

以人为顶点，握过手则在这二个顶点（人）间联一条边。显然，该图的奇度点个数为偶数个。

例9 图2-26有8个奇度点，故需4笔画成。 例10 中国邮路问题

一邮递员从邮局出发去各街道投递信件，然后再回到邮局，每条街道至少经过一次，求一条路使其走过的路线最短。

若所研究的问题为Euler环游，则问题显然，且Euler环游为最佳路线。否则以如下问题（如图2-27，非E图）为例说明中国邮路问题的解法：

第一步，将图变为Euler环游。 （由于 v2, v3, v6, v7为奇度点，故非E图）。 首先，增加边使每一奇度点变为偶度点；

其次，若某二点间重边数多于一条，则去掉偶数条；最后检查含有重边的圈： a）若各圈长度＞2重边长，则方案最优，否则b)调整，将原来重复的边去掉，没有重复的边加上边（变成重边）。

８１

图2-24

图2-25

图2-26 图2-27

如此可将问题转化为Euler环游问题。

第二步，对于G为Euler环游情况，求出Euler回路。 Fleury算法——求Euler环游的算法 1． 2．

取v0 ∈V(G), 记w0=v0；

设Wi=v0e1v1e2 ? eivi 已选定，则从E－{e1?

ei}中选取一条边ei?1 使 a) ei?1与ei相邻 ； b)除非不得已，ei?1不是G－{e1?ei}的桥（桥：e称为图G的桥，如果e不在G的任一圈（或去掉e，图不连通）； 3．

重复2）直到不能进行，即得一条Euler环游。

图2-28

第三步，求图的Euler途径。

定理2-3 若G是Euler环游，则Fleary算法终止时即得到Euler回路。

例11扫雪问题（AMCM-90B美国数学建模竞赛90B题）是考虑二辆扫雪车清扫路面积雪问题。

图2-29

地图(图2-29)中的实线表示马里兰州威考密科县中扫雪区域中的二车道马路，虚线表示州属高速公路。一场雪后，从位于*标记地点以西4公里的二处车库派出二辆扫雪车。求用二辆扫雪车清扫路面上的雪的有效的方法，扫雪车可以利用高速公路进入扫雪区。

假设扫雪车既不会发生故障也不停顿，在交叉路口不需要特别的扫雪方法。 大致做法：

８２

1)量出各条道路长度(可用丝线沿道路曲线测量)，得到一个加权图，从而问题转化为中国邮路问题。若只有一辆扫雪车，且（1）地图为Euler图情形，则可按Fleury算法求出Euler途径即为最佳扫雪方案。

2）若地图不是Euler图的情形，则要在某些边重复，即增加一些重边使之变为Euler图。问题则转化为求一个新边集E?, 使G?(V,E?E?)为Euler图前提下，??(e)最

e?E?小。

(1)若只有二个奇度点，则只要在该二点间加一“边”即可：若相邻，则在该二点间联一条边即可；非相邻，则用下面Dijkstra算法求出最短路线，然后在该线路上的每一边加一重边即可得到一Euler图。

Dijkstra算法： ② 对每一v?Si 用min{L(v), L(ui)+W(uiv)} 代替 L(v), 设ui?1 为L(v)中最小者（v?Si ）令Si+1=Si∪{ui?1} ，转③；

③ 若i=∣V(G)∣-1 止；若 i<∣v(G)∣-1,则转②

此时，每个顶点所标L(v)即为到u的最短距离，此算法的复杂度 O(V2)（顶点数V的平方的一个同阶量）。

Dijkstra算法不仅给出了二点间的最短距离，而且由此可得到最短路线。

(2)多于二个奇度点，则易知其奇度点个数为偶数个。可将所有的奇度点之间分别

4联一条“边” 并使得所联 “边” 的总长度为最短（这

21里边的意义同（1））。 这样得到的图即为最短路线（其中重边即为需要重复走的路段）。

755① L(u0)=0， L(v)=∞ v≠u0， S0={u0},i=0 ，转②；

3623412517223374图2-30

2 下面用实例（如图2-30）说明做法：

341）求奇度点集 X1={①②③④}； 32）用Dijkstra算法求出对应点间最短距离：

８３

图2-31

1 2 3 4 1 0 4 5 7 2 4 0 2 5 3 4

5 2 0 3 7 5 3 0

3）构作加权完全图 K(X1,E0)（完全图：任意二顶点间都有边的图）。图2-29(对奇度点集)；

4）求出最佳匹配 {①②，③④}

①②+③④最小，此时保证：①过每一奇度点，增一边（使每一奇度点变为偶度点）②增加的边的总长最短；

5）求出①--②最短路①-⑦-② ，

③--④最短路 ③-④；

6）在相应边上加一同权新边，即得Euler图G?； 7）求出G?上Euler路（用Fleury算法） 4．货郎担问题, Hamilton路问题

1859年，著名数学家Hamilton（U.K）提出了所谓“周游世界游戏”：用正十二面体的20个顶点代表二十个大城市北京，东京，华盛顿等大都市名称(图2-32)。要求玩的人从某大城市出发，沿着正12面体的棱通过每个大城市恰一次，再回到出发城市。这种游戏曾风靡欧洲一时，后来Hamilton以25个金币的高价把该项专利卖给了一个玩具商。

若将图中前面的五边形“拉开”，使之变成平面图则得到下边的图形（图2-32b）。

问题转化为：在图上找一条从某点出发的道路经过所有顶点一次且仅一次回到起点。

含图上一切顶点的道路称为Hamilton路；闭的Hamilton路称为Hamilton圈。 寻找Hamilton路（圈）是图论上难点之一，至今未发现Hamilton路存在的充要条件，下面是一些主要结论：

充分条件1：（Ore,1960, [5],P.64） 设图的顶点数为n(≥3), 若对于任意u,v∈V(G) ，d(u)+d(v)≥n ，则G为 Hamilton圈 ；若对于任意u,v∈V(G) ，d（u）+d(v)≥n-1， 则该图存在Hamilton路。

８４

(a)(b)图2-32

充分条件2： （Dirac, [4],P.42）设图G的顶点数n(≥3), w为度数最小的顶点，若deg(w)≥n/2, 则G为Hamilton图。

充分条件1，2的本质：每个顶点的度数均充分大。

充分条件3： G为n个顶点（n≥3）的连通图，?k≤(n-1)/2的正整数，次数小于k的顶点数≤k, 则G为Hamilton图。

例12 亚瑟王（传说中的英国国王）在宫中召见他的2n个骑士，而骑士中有些有怨仇。若已知每个骑士最多与n－1个骑士有仇，问能否将这2n名骑士在一个（著名的）圆桌上安排就餐，且使每个骑士不与他的仇人相邻。（其谋士摩尔林做到了这一点）。

解：化为图论问题：以2n个图的顶点表示骑士，若二骑士之间无仇则在二顶点之间画一条边，得到一图G(V，E)。 问题转化为：是否能在图G(V，E)上寻求一条Hamilton圈。

由条件，每一顶点的度数≥n， 故?u， v∈V， d(u)+d(v)≥n+n=2n， 由Ore知存在一条Hamilton圈。

上述条件为充分而非必要条件。如周游世界游戏（图2-30）不满足条件，但存在Hamilton圈。

引入如下概念：

图的闭包：若图G的任意顶点u，v若满足d(u)+d(v)??V (顶点数)，则当这二点之间无边时，连一条边。依次做下去直到不存在这样的顶点，这样得到的图称为图G的闭包，记为C(G) （如图2-33）。

定理2-4：（充要条件）图G为Hamilton图的充分必要条件是C(G)为Hamilton图。

注：此条件仍不能判断周游世界游戏为H图。

目前，对如何判别一个图为Hamilton图仍是世界难题。 与之相关的问题是：

货郎担问题：一货郎挑担到n个村去卖货，能否找到一条

最近的路，使货郎经过各村庄一次再回到出发地。（假设各村之间路程为已知）

它可以视为加权Hamilton圈问题，记G(V，E，w)（ w为相应边的权）。 Hamilton图可视为特殊的货郎担问题，即各边权值相等皆为1。

由于Hamilton图的判别仍是未解决的问题，因此，货郎担问题当然无法解决。

思路1：将通过各顶点的道路方案“历数”，比较并找出最佳路线。但这是不现实的：如有20个村庄，

图2-33

vi?1vivj?1vj８５

图2-31

任二个村之间都有路相通，则要比较上也要计算770年。（[5]，P.4）

12×20！=2.43×1018次，这在每秒千万次的计算机

思路2：当已知c=v1v2?vvv1为一回路，则可用下边的“改良圈算法”进行优化，得到一条最佳路线。

改良圈算法：

（1）检查c上是否有i≠j， 使vi-1vj∈E(G)， vivj+1∈E(G)且w(vi-1vj)+w(vivj+1)

（2）用c1代替c，转入（1）直至终止。 该算法计算复杂度为O(V)。

此算法前提：vivj+1及vi-1vj有边，否则无法“改良”。特别，当图为完全图时，此算法有效。

例13一学者从北京(Pe)到伦敦(L)、 墨西

Pe2

L605156706813MCT27835216168515736PaNY哥城(Mc)、 纽约（NY）、巴黎（Pa）、

图2-34

东京（Tokyo）讲学（各地之间的距离见图2-34，单位：百公里），现为其设计一路程方案，使之

花费最少。

取初始圈

c=(Pe)(T)(L)(Mc)(NY)(Pa)(Pe) 总路程13+60+56+21+36+51=237（百公里） 。 用改良圈算法计算（如图2-35），计算结果：

c1

=(Pe)(T)(L)(Pa)(NY)(Mc)(Pe)=210

c2

=(Pe)(T)(Mc)(NY)(Pa)(L)(Pe)=193

c3

图2-35

=(Pe)(T)(Mc)(NY)(L)(Pa)(Pe)=192

c3为最佳路线。

思路3. 可用“最邻近方法”或称“贪婪算法” 。

８６

方法：从v0出发，比较v0到v1，┅，vn 的边长，先到距v0最近的点，依次下去可得一条较好的线路。

例14.有一商店v1 ，售货点4个，他们之间路程如图2-36。

按贪婪算法解得最佳路线为 v1v4v3v5v2v（长度为40），但v1v5v2v3v4v（长度为37 ）11

更优。

此算法未必能得到最佳路线，但算法简单，容易实现。 思路4. 最近插入法

方法：设已得到一部分顶点的Hamilton圈Vk 。在剩余点中寻找距Vk中点最近的点加入vk得Vk+1。而新点加在哪里，可采用比较方法，即将该点加至不同位置，取路径最短者。

又解例14. 用“最近插入法”：

先取v1作为V1。 显然下一点取v4，加入V1得到V2=v1v4v1回路。再看距v1，v4最近的点。比较v1v2=14 ， v1v3=12，v1v5=10，v4v2=13，v4v3=6 ，v4v5=11故增加v3。

又比较不同的路线长度v1v3v4v1=12+6+7=25 ，v1v4v3v1=7+6+12=25，二者相同，不妨取新回路为V3=

v1v4v3v1；再计算出距{v1，v4，v3}最近点 v5 ，找出最佳回路：V4=v1v4v3v5v1 ={v1，v4，v3，v5}；剩唯一点v2 ，最后比较得最佳回路 v1v4v3v2v5v1，总距离37。

5．好算法与NP完全问题

下面就此问题作一个简单介绍

1965年，Hartmanis和Stearns 在所谓Turing机的意义下，（它是一个数字概念，也是后来真正计算机诞生的理论基础）提出了所谓计算复杂度的概念。

定义2-1（1965，Edmonds）某问题在Turing 机([3],[5])上的计算时间作为输入长n的函数有某个多项式为其上界，则称该问题有多项式时间算法。

好算法：若给定一问题，如果某算法使得：对于输入长度为n，存在一个多项式P(n)，，使该问题使用本算法至多经过不超过P(n) 次的运算，可得到其解，则称此算法为好算法。

坏算法：若给定一问题，如果某算法使得：对于输入长度为n，至少要经过n的某指数函数次运算得到其解，则称此算法为坏算法。

如某问题的计算复杂度为2n ，则若某问题能在1小时完成2机器的100倍速度，则新机器在一小时内可处理 2n=2的办法解决问题的目的不能实现。

８７

n0n0图2-36

，现改进计算机为原

×100，此时 n=n0+log2100

即计算机运算速度提高100倍，仅能增加7个参数长度，从而使我们试图用改进计算机

而类似的对于某n2算法，n2=100n02 则n=10n0 ，即当计算机的速度提高100倍，就可以使n0的数值提高10倍。

如：前面我们介绍过，线性规划有多项式算法，从而可以在计算机上实现有效的求解。另外，Dijkstra算法、改良圈算法等是好算法。

但有些问题没有多项式算法，如货郎担问题（或旅行售货商问题）。

也有许多问题，虽没有多项式算法，但可以将其转化为判定问题(如果某问题的答案为是或不是,则称该问题为判定问题)。

一个判定问题D在不确定Turing机上在多项式时间内被解决是指： 对于问题D, 存在多项式P(n),使得对D的输入长为n时, 若其答案为”是”,则存在一个猜想, 对于它, 机器在P(n)时间内停机于 “YES” 状态； 若其答案是“否”, 则对于每个猜想,在P(n) 时间内Turing机皆停机于 “NO” 状态。

注：这里不确定Turing机概念中 “不确定” 三个字的含义是：上述的 “若答案为 ?是?,则存在一个猜想, 对于它, 机器停机于“YES”状态”一语中, 我们只是相信有这么一个猜想存在, 但并未给出一个确定的方法可以找到这个猜想。也许我们侥幸碰上了这么一个猜想,但这种幸运是罕见的；或者这个问题的答案是否定的, 这时, 要逐个验算猜想, 而猜想可有?P(n)?1个（?表示纸带上带符集合，输入符是带符的子集）,要用P(n)?P(n)?1时间来完成, 这是一个可怕的指数时间, 会随着n的增大而爆炸性增大, 所以用这种方法来求解, 实际上是不现实的, 也就是说, 用Turing机如此解决问题不可能实际地得出确定的答案。

不确定Turing机对于解决问题实际上是个无效的工具, 它只有理论上的价值, 借助于它, 我们可以建立 NP问题的概念.

P问题：对于一个判断问题D，存在一个多项式时间算法，解决该问题，则此类问题称为P类问题集合，记为P.

定义2-2 在多项式时间内能被不确定Turing机解决的判定问题之集合叫做NP 类判定问题集合, 记做NP。

对于上述的货郎担问题可以转化为判定问题：给出一个边长为自然数的图和一个自然数k，问是否有长度不超过k走遍所有顶点的巡回路线？

对于这个判定问题，可以在所谓不确定Turing机上找到多项式算法。于是，货郎担问题是一个NP问题。

下面介绍NP完全问题：

首先，若某问题A能在多项式时间内归结为问题B，则记为A∝B。

定义2-3：（C完全问题）考虑由判定问题组成的集合类C，若B∈C且对于任何A

８８

∈C，有A∝B，则称B为C完全问题。 显然，C完全问题?C。

定义2-4：(NP完全问题，记为CNP) 对B∈NP，若?A∈NP,A∝B，则B∈NPC。 显然, P?NP。.但P=NP是否成立?这是一个尚未解决而其意义十分深远的问题。先介绍：

定理2-5：若B∈P， A∝B，则A∈P。

由此知：(1) 一个NP完全问题∈P，则所有NP完全问题∈P。

(2) 一个NP完全问题?P 的充分必要条件是 P≠NP。

因此，能否找到一个NP问题，说明其∈P或?P（即证明P=NP或P≠NP）仍是个世界难题。

从1972年，多伦多大学 Cook找到了第一个NPC问题，陆续繁衍出大批的NPC问题，目前已达2000多个（见[6]）。 对NPC问题，目前更倾向于P不等于NP的看法，即这些问题也许根本不存在多项式时间算法。

6．树，最小生成树

定义2-5：无圈连通图称为树；只有孤立顶的树称为平凡树；每个连通片都为树的图称为林。

定理2-6：对于树，如下结论等价： ⅰ）G为树；

ⅱ）G中任二顶之间有且仅有一条路 ； ⅲ）G中无圈，且|E|=|V|-1 ； ⅳ)G连通且|E|=|V|-1 ； ⅴ)G连通，?e∈E，G-e不连通 ； ⅵ）G无圈，?e?E，且以V中点为顶，G+e恰有一圈。 定义2-6：若G1是G的子图，若V1?V,E1?E,E1?E，则称G1为G的生成子图。 若G1又是树，称G1为G的生成树。

一个图的生成图很多，如仅10个顶的完全图有1010-2（1亿）个生成树。

定理2-7：(Caylay) n个顶点的完全图的生成树共n个。

十九世纪中期，克希霍夫（Kirchhoff,1847年）在研究电网时巧妙的应用了生成树的概念；凯莱（A.Cayley,1857年）利用树的概念成功的解决了有机化学中的同分异构体。使树的理论获得发展。

求生成树可用BFS（Breadth First Search）方法。

８９

n?2算法如下：

1） 取v∈V(G)，标l(v)=0 取l=0； 2） 当所有标号为l的顶u的相关联的顶均

已标号止；否则把与u相邻的未标号的顶标以l+1，记录这些边（图2-37中用粗线，注意不重复标记）。且以l+1代l，转2）。 3） 止。

该算法终止得到的标记边即为生成树。 例15．设1，2，?，n表示n个城市。若i，j城市之间的铁路造价为Cij，设计一个线路图，使总造价最低。

即求连通（加权）图的生成树使其权最小，称最优树。

若n较小，求出所有生成树再比较找出最优树即可。若n较大，将所有生成树皆求出再比较是不现实的。因为一个完全图的生成树共有nn?2个，为幂指数函数。一般情况下，可用Kruskal 算法找出最小生成树。

Kruskal 算法（求最小生成树）

1） 选e1∈E，使?(e1)?min{?(ei),i?1,2,?,n}；

2） 若e1?ei已选好，则从E-{e1?ei}中选取ei?1，使得： ⅰ）G[{e1?ei，ei?1}] 无圈 ⅱ）求ei?1使ω（ei?1）=min{ω(e)|e∈E-{e1?ei}且{e1?ei，ei?1}无圈}；

3) 继续到第 |V|-1个e （e|E|-1）选出。

由定理2-6，边的个数=|V|-1表示图为连通图，故Kruskal 算法的结果为G的最小生成树。

定理2-8 Kruskal算法得到的生成子图为最优树。 7．迷宫，扫雪问题

迷宫问题有二类：1）从入口进入迷宫中心（有财宝，怪物，点将台）；2）在迷宫中迷路后再走出来。如神话中的英雄Theseus（瑞典王子）被绑架到迷宫中心，公主亚利阿特涅给他一团线，让他边走边放。王子最后借助这一条线指示的路线逃出。

图论提法：从图的一个顶点出发，游历图中每一条边，二次且仅二次。 下属方法是实现上述问题的有效方法：

1）Tarry算法 当到达一个交叉点v时，二件事情已知：ⅰ）与v相邻的且离开v的方向、已经走过的边的集合； ⅱ）我们初次到达v时所经过的边（进入边）。此时，

９０

233432121021图2-37

当到达v时，继续沿着一条尚未按v到v?方向走过的边（v，v?）前进，除非不得已，不要选进入边。

可以证明：按Tarry算法一定可以从v0到v0且每条边恰走二次。

2）沿墙向右拐：无圈时，沿墙向右拐不失为一种走迷宫的方法。（有圈时可能形成死循环）。

胡同?边死胡同、交叉点?顶点 图2-38

3） 纵深搜索法（DFS：Depth First Search，1973，Hopcroft&Tarjan） (1) 标志一切边 “未用过”，对每一顶v?V(G),k(v)?0,令i?0,v?s； (2) i?i?1,k(v)?i；

(3) 若v无未用过的关联边，转（5）；

(4) 选一条未用过的与v关联的边e=uv，标志e “用过了”；若k(u)≠0，转（3）；否则(k(u)=0), f(u)?v,v?u，转（2）；

(5) 若k(v)=1,止；

(6) v?f(v),转（3）；

易知DFS过程中，图的每一边恰通过二次。

再讨论例11（ AMCM—90B）扫雪车问题 分几种情况：

若只有一辆扫雪车，双行道（相对于一辆车可清扫一半路面），则可用上述算法按走迷宫的算法（由于道路不熟）。

单车道双车扫雪： 相当于 “多个邮递员的中国邮路问题”（它是一个NPC问题）：多个邮递员送信，将区域分为若干块使送信的总时间最少。

双车道双车扫雪：将街道分为二部分，使得两部分都连通且总长相等，则每车清扫的部分可以看成一个单车扫雪车问题，按上述算法扫雪即可。

但这并不总是可以的。

即使对于权为“1”的Euler图情况，要寻求等长闭行迹c1，c2使E(c1)∪E(c2)=E(G)

９１

且E(c1)∩E(c2)=Ф，W(c1)=W(c2)，被称为“Euler二等分问题”，是NPC问题，它的更特殊例子是 “PART问题”（它的最初提法：一大学分东西二区，每班住一区，问：是否存在分法使东西各区人数相等？）也是一个NPC问题。

其他情况

1． 要求每边恰通过一次，同时完工，但未必回到出发点。（一笔画）

2． 不要求同时完工，但要求最后一个完工者最早完工，且每条街道恰扫一次。

8．分工问题与偶图（二分图）

分工问题

某公司有员工x1?xn及n项工作y1?yn， 每个员工适合做其中某些工作。问能否使每一人分到一项适合工作？若否，最多几人能分配合适工作？怎样分配？（最初提法：n个姑娘，n个小伙，每个姑娘只认识一部分小伙子，问是否存在适当的方法使每一个姑娘都能和理想的小伙子成婚）。

图论中与之相关的概念是匹配。

匹配：图G的边的子集M称为G的一个匹配。若ei，ej∈M， ei ，ej不相邻，M中的一条边之二个端点叫做在M之下相配。M中的每个端点称为被M许配；G中每个顶点被M许配的，称M为完备匹配。G中无匹配M? │M?│>|M|，则称M为最大匹配。

二分图：图G称为二分图，若V（G）=X∪Y， X∩Y=?， X中顶点不相邻且Y中顶点不相邻。

完全二分图：X中每一顶与Y中任一顶相邻的二分图，记为Km，n

邻集：A?V(G)， V(G)中与A中顶相邻之顶集N(A)称为A的邻集。注：v和v自身不叫相邻。

设G1，G2为G的子图， G1∪G2(并)： G1，G2所有边组成的图；G1∩G2(交)： G1，G2公共边组成的图 ；G1－G2（差集）：从G1中去掉G2的边后得到的图，若G1中去掉一边时出现孤立点，则把该孤立点也去掉；G1?G2 ：G1∪G2－G1∩G2. (环和，对称差，也可以G1?G2记之为图2-39 )；

交替道路：从二分集G(X,Y,E)的匹配集M到E?M交替出现的路；交替树：G=(X,Y,E)

９２

设u∈X未被M匹配，T称为G的M交替树，若① u∈T ②?v∈T,有唯一的u到v的交替道路，u称为根；M增长道路：交替树T终点也未被M匹配，则称T为M增长道路。

定理2-9：(Hall，1935) V(G)=X∪Y 是二分图，则G中存在完备匹配（把X中顶皆许配的匹配）的充分必要条件是?s ? X ， | N(s)|≥|s|( N(s)为s的邻顶集)。

?v∈V(G)， d(v)=k 则称G为k次正则图。

推论：G是k次正则二分图，则G有完备匹配。 求完备匹配的匈牙利算法（Edmonds，1965） 设G=(X，Y，E)为二分集，X，Y为其二个顶点集） （1）

从G中的任一匹配M开始；

（2） 若M与X所有顶点匹配，则终止。

否则，?u∈X，未匹配，记S={u}?X，T= ??Y ；

（3） 若N(S)=T， 由定理2-9， 由于|N(S)|=|T|=|S|－１<|S|，故G无完备匹配，算法终止。否则，取y∈N(S)－T?Y；

（4）若y为被M许配的，设yz∈M， 则S∪{z}→S， T∪{y}→T 转3）；否则即得u到y的一条增长道路 E(P)； （5）令M1=M?E(p)代替M，转2）。

例2-15．求图2-40的最大匹配

首先取初始匹配 M={x2y2， x3y3， x5y5}， （1） x1未被匹配 S={x1} N(S)={y2， y3}, T=?， y2∈N(S)－T 被匹配 S→{x1， x2} ，N(S)={y2， y3， y4， y5}， T={y2}, y4∈N(S)－T， 则E(p)=x1y2x2y4为增长道路。 （2）M1=M?E(p)={x1y2， x2y4， x3y3， x5y5} （3） S={x4}未匹配， N(S)={y2， y3} ,T=?， y2∈N(S)－T, S→{x4， x1}, T={y2} N(s)={y2， y3} ; y3∈N(s)－T , x3y3∈M1， S→{x1， x3， x4} (*) ,N(S)={y2， y3} T={y2， y3} , N(S)－T=? , 无完备匹配。

讨论：若G增加x1y1，则于（*） N(S)={y1， y2， y3} , T={y2， y3} , y1∈N(S)－T 未匹配, 所以

E(p)=x4y2x1y1为M增长道路，M1?E(p)={x4y2， x2y4， x1y1， x3y3， x5y5}为完备匹配。

9．平面图

1）Euler公式与正多面体

９３

图2-40

Euler公式：G是连通平面图 则v－e+f=2 ， 其中v 顶点数， e 边数，f面数（这里一个多边形或图的外面均称为一个面）。

证明：对f用归纳法

f=1，G无圈， 又G为连通图，故G是树，于是 v=e+1=> v-e+f=v-e+1=2 成立。 设f=k时，v－e+f=2成立。

现证f=k+1成立。 由于f=k+1≥2知G有圈， 设e0为G的某个圈的边，则G－e0

仍连通。G中被e0分割的二个面在G－e0中变成了一个面。于是，G－e0有k个面，故由归纳假设 V(G－e0)－e(G－e0)+k=2 但V(G－e0)=V(G)， e(G－e0)=e(G)－1 所以上式变为 V(G)－(e(G)－1)+k=2 ，即V(G)－e(G)+k+1=2，亦即V(G)－e(G)+f(G)=2。▌

注：（1） Euler公式对凸多面体亦适用（为平面图）如：正六面体 v=8，e=12，f=6 v-e+f=2

（2） 当G非连通且连通分支为ω时有v-e+f=ω+1

正多面体，一个正多面体各面的边数相同 n， 各顶点的棱数相同 m， 显然n，m≥3， 2E=mv=nf(=棱的二倍，正多面体的面为n边形)， 又v-e +f=2

N M V E 可解得：

3 3 4 6 4nv=， 3 4 6 12 2n?mn?2m3 5 12 30 2mn4 3 8 12 e= ，

5 3 20 30 2n?mn?2mf=

4m2n?mn?2nF(f面体) 4 8 20 6 12

讨论：m=3 ，分母为 6-n，分子为正，可知3≤n≤5 ；

n=3 分母为6-m，分子为正，可知3

≤m≤5。

故可讨论m=3，n=3，4，5； n=3，m=3，4，5

又m=4时n=3；m=5时 n=3；m=6时 n取任何≥3的自然数均无意义。

同理，n=4，m=3；n=5，m=3；n=6时，m取任何≥3均无意义， 故得上表。

由此知,正多面体只有五种:正四面体、正六面体、正八面体、正十二面体、正二十面体。

2．平面图

二个例子： 1）古代独裁者

９４

(a)(b)图2-41

相传古代有一位独裁者，临死时留下遗嘱，把土地分给他的五个儿子，这五个儿子在自己的领地上各修建了一座宫殿，他们还企图修一些道路，使得每二座宫殿之间有一条道路直接相通，又要求道路不能相互交叉。结果这五个愚蠢的王子煞费苦心，终告失败（图2-41（a））。

2） 房屋和井

有3户人家，旁边有三口井。欲修从每一房屋到每一井的路线，使它们互不相交（图2-41（b））。

这二个例子具有代表性，我们将用Euler公式证明其非平面图。

定义2-7：一个图称为可嵌入曲面S， 如果把它的图示画在S上，可以使任二条边不相交。可嵌入平面的图称为平面图，否则称为非平面图。

例2-16：任意树为平面图； K5(每顶点4度，5个顶点，10条边)可以嵌入环面(图2-30，31)；

K33（二分图，每顶点3度，6顶点，9条边）可嵌入Mobius带(图2-42，43)。

定理2-10. G是平面图的充分必要条件是 G可嵌入球面。

定理2-11. K5，K33不是平面图。

证明：对K5， V(K5)=5， E(K5)=10 由于K5为连通图且为简单图，故每个面至少有三条边，所以3f≤2×10(每二个相邻面公用一条边), 另一方面，由Euler公式 f=2

－v+E=2－5+10=7，所以3f=3×7>20 ， 矛盾说明K5非平面图；对K33， V(K33)=6，E(K33)=9，f=2－v+E=5， 由于K33为二分图，故每个面至少4条边从而4f≤18 但4×5≥2×9 矛盾。

为说明一般图是否为平面图，

图2-43

先引入： 图2-42

９５

初等收缩（Kuratowsky，1930）：图G上的相邻二点，u，v用新点ω代替得到的新图。（此时ω与原来和u，v相邻的点相邻）称为图G的初等收缩。

同胚：二个图称为同胚，若一个图可以从另一个图的边上“加上”一些新点得到；规定图自己和自己同胚。

图2-44（a）与K5同胚，图2-44(b)（又称

显然，收缩与同胚互逆。 定理2-11（Kuratowsky，1930）G是平面图的充分必要条件是G中无子图与K5或K33同胚（或可收缩到K5或K33上）。

如：最小的妖怪（Petersen 图）不是平面图（有与K33同胚的子图）， “最小的妖怪”是“妖怪”（Snark graph，图2-45）的子图，特点：V=10，每顶有三条边，无桥， 任意删除三条边不会使之变为二个有边图。

d图2-44

Petersen图，也称最小的妖怪）有与图2-44 (c)(K33)同胚的子图。

图的厚度：若图G=

?Gi?1i

图2-45

E(Gi)∩E(Gj)=? ，Gi （为平面

图），则称G1?Gd为图G的平面分解。?(G)=min{d|(G1?Gd)是G的平面分解}称为图的厚度或层次。

定理2-12. θ(G)≥[

E3V?6 ] （V>2）。

此结论可应用于：设计电路板，需要电路在平面上实现，制成印刷电路，问一个电

９６

路至少在几块电路板上实现？

目前，还无确定图的厚度的公式，也无有效算法。

平面图在工程技术上有广泛应用，因此，它和Harmilton图问题一道形成了图论的十分活跃的课题。 从历史上看，Kuratowsky定理的提出（1930）打破了图论研究的沉闷局面，成了图论振兴的转折点。

10．着色与四色问题

定义2-8：图G的一个k顶着色是指把V(G)分成k部分{V1，?，Vk}，Vi中的顶着以 i色，若每个Vi中无相邻顶，则称此k顶着色为正常k顶着色。

若G可以k顶着色，但不能k－1着色，则记k=X(G)称为G的顶色数。 显然，任一图可以V正常着色 结论：X(G)≤Δ+1 (Δ=max{d(v)}) 应用1. 考试安排问题：

某校共有n门课需要进行考试，每个学生不止选修一门课，为使每个学生都能参加自己所选课程的考试，问至少需几天才能安排完？ 记每一门课为一个顶，当且仅当二门课被同一学生选修时连一条边，得到一个图G(如图2-46)。

G正常着色对应于：同一学生不会在同一时间参加他选的二门课的考试。因此，X(G)即为安排完考试所需的最少天数。

应用2．存储问题：有的货物放在一起不安全（如羊和白菜，狼和羊等），问至少几个库房存放才是安全的？将货物看作顶点，不能放在同一库房的货物之间联一条边，得到一个图，问题转化为k顶着色问题。

定义2-9：平面图G嵌入平面后，它的k面着色，是指将面集合分成k部分{F1，F2，┅Fk} ，Fi均涂以i颜色；若每个Fi中的面二二无公共边，则称此着色为k面正常着色。

若G能k面正常着色，不能k－1面着色，则称k=X*(G)为G的面色数。 图的对偶：若将图G的面对应顶，面相邻则在二对应点间联一边，得到的图称为图G的对偶，记为G*。

显然， X(G*)=X*(G) (∵f(G)=V(G*))

四色定理：（1852 伦敦大学学生 Guthrie）1. 对任何平面图G， X*(G)≤4 ; 2. 对任何平面图G， X(G*)≤4。

这个问题，困扰了数学家们100年，1878年由格思里（Francis Guthrie）首先提出。直到1976年，伊利诺大学 Appel和Haken在Koch的协作下，用计算机证明了四色猜想（用了1亿个逻辑判断，花了1200个机时。说明其证明之艰难）。

９７

图2-46

1879年，伦敦数学会 Kemple 发表了四色问题（4CC） (Four Colour Conjective)的证明，提出了一些天才的想法，但后来发现其证明有错。但是，以后人们还是沿着Kemple的思想直至1976的最后解决（1977年有人又给出一个计算机证明，用50小时）。

在Kemple的证明中，首先提出了“颜色互换法”，用这一方法可以很简单的证明直线图可用二正常着色及X(G)≤5。

例2-17（二色图）平面上n条直线将平面分成若干个区域，则可用二种颜色对其涂色使其为正常涂色。

证明：用归纳法： n=1显然，设n=k成立，即可用二种颜色着色，增加一条直线（第n+1条），将该直线一侧二种颜色互换即知结论成立（图2-47）。

定理2-12(Heawood，1890) G为简单平面图，则X(G)≤5。 首先我们说，任一平面图可以“拉直”为“直线图”（如图2-48）

命题（1948，Fary）简单平面图G都可以“直线化”。

定理2-12的证明：对v用数学归纳法：若v≤5 则显然可用五种颜色涂色（各涂一色即可）。

设v=k 可用五种颜色涂色，来证明v=k+1时结论真。

首先，存在v∈G，d(v)≤5。（事实上，由于G是平面图，则每一面至少有3个边，于

f?图2-47

V7图2-48

是

23，

13f≤2E。

13若?v,d(v)?6则6V?2E23，从而，

E,V?3E,?V?E?f?E?E?E?0，与Euler公式矛盾）

设d(v0)≤5，且设G－v0(将相应的边也去掉) 已按规定涂好五种颜色。 1) d(v0)<5， 则将v0涂以不同于其他邻顶颜色即可

９８

2）d(v0)=5 且V(G－v0)=k 故不妨设v0的邻顶已涂a1， a2， a3， a4， a5 五种颜色。A) 若a1， a2， a3， a4， a5中有二个顶点颜色相同（这是可能的，因它们未必都与一个顶相邻）此时，将第五种颜色涂在v0即得G的一种涂色。(图2-49（a）)

B) 否则，设v1， v2， v3， v4， v5 分别涂以颜色a1，a2，a3，

a4，a5 （如图2-49（b）），设v1，v2不在同一连通分支，且Gaa表示含v1连通分支中由a1，

12V0V0(a)(b)图2-49

'a2颜色的顶及其相邻的边组成的图，考虑将

Ga1a2中a1，a2颜色互换，互换后含v1连通分

'支中仍以五种颜色正常着色，且此时v1变为a2，与a)情况相同，即可正常涂色。

因此，若定理结论不真，v1，v2必在同一连通分支，从而，存在v1到v2的一条轨道。

同理，v1，v3之间有一条轨道，从而v0v1p(v1v3)v3v0为G中一圈。此时，v2在该圈之内（如图2-50），v5在该圈之外（设按v1,v2,?,v5逆时针方向排序）。 同理，v2，v5之间亦有一条轨道。

由于G为平面图，这是不可能的。

（事实上，若v2，v5之间有一条轨道。则由于是平面图，必在某一公共顶与v0v1p(v1v3)v3v0相交，此顶在Gaa中故应为a1或a3色，又在Ga2a5中，故又需为a2或a5色。这是不可

13图2-50

''能的）。▌

11．其他问题

例18 人、羊、狼、菜渡河问题

一个摆渡人,要用一小船把一只狼、一头羊和一筐菜从小河的左岸渡到右岸去，记人 （F），羊（G），狼（W），菜（Cabege），船最多载F、W、G、C中二个，且在无人看守的时候，决不能让狼和羊、羊和白菜在一起，应怎样才能把狼、羊和白菜安全渡过河

９９

去。

以各种可能的状态FWGC/O，FWC/G，FGW/C，FGC/W，FG/WC；O/FGWC，G/FWC，C/FGW，W/FGC，WC/FG为顶点，此岸到彼岸可能的转移路线作边，组成二分图：

FWGC/O FWC/G FGW/C FGC/W FG/WC

① ② ③ ④ ⑤

⑥ ⑦ ⑧ ⑨ ⑩ O/FGWC G/FWC C/FGW W/FGC WC/FG

目标是寻找一条从1到6的交替路。易知①→⑩→②→⑨→③→⑦→⑤→⑥为所求路线。

例19． 夫妻过河

有3对夫妻要过河，船至多可载二个人，条件是任何一个女子不能在其丈夫不在场的情况下与其他男子在一起，问如何安排这3对夫妻渡河？

由条件，可设（H,W）表示H个男子和W个女子在此岸，其中0≤H,W≤3,则易知可取的状态有10个：（0，i）,(i,i),(3,i),I=1,2,3（其中（i,i）表示第i对夫妻）,目标:从(3,3)到(0,0).

规则：1）此→彼 对应：向下，左； 彼→此 向上；

2）仅有一船，故只能此→ 彼→ 此?;

仅有一船，向下，上，左，右一次最多移两格，向斜下，斜上可移一格.

方法：1)?状态转移在坐标系中表示(见图2-52)。

2) 用例18方法,表示为二分图，寻找交替路（作为练习，略）。 3）矩阵法

先找出允许状态集合。

此 彼 此 彼

①（3，3） （0，0） ⑩（0，0） （3，3） ②（3，2） （0，1） ⑨（0，1） （3，2） ③（3，1） （0，2） ⑧（0，2） （3，1）

１００

图2-51

32WA(3,3)1H0123图2-52

④（3，0） （0，3） ⑦（0，3） （3，0） ⑥（1，1） （2，2）

⑤（2，2） （1，1）

决策集 d={（u，v）|u+v=1,2} d k?{(1，1)，(0，2)，(2，0),(1,0),(0,1)} 状态转移规律 S k+1=Sk+(－1)d k 状态转移矩阵

定义：称矩阵A=(aij)V×V是标志图G的邻接矩阵，其中V=|V(G)|

?1,vij?E(G)aij??

0,v?E(G)ij?k

(vi→vi 理解为无边,即aii=0)

v1

?0?如：?1?0?1010??1? v2 0??v3

定理2-6：设A=A(G)是图G的邻接矩阵，则A中的i，j号元表示vi到vj长度为k的轨道的条数。

证明：k=1 显然 设k≤n时 aij(k)

k

表示从vi到vj的轨道的条数 则 aij(n?1)?ai1a1j?ai2a2j???aivavj

(n)(n)(n)而从vi到vj的轨道长为n+1， 可以看成从vi到vk经n步，再从vk到vj(一步)（可能从vk到vj无路，即akj=0。则此时vi经vk到vj的轨道数为0），由归纳假设vi到vk轨道长为n的轨道共有aik条。故vi经vk到vj的轨道共有aikakj条，从而从vi到vj的轨道共有 aij(n?1)(n)

(n)

?ai1a1j?ai2a2j???aivavj条。▋

A?? 其中 0??(n)(n)(n)?0如例27 A=??A?

１０１

?0 0 0 0 0 1 0 1 1 ??0 0 0 0 0 1 1 1 0 ????0 0 0 0 1 0 1 0 0 ???0 0 0 0 0 0 0 0 0 ???A??0 0 1 0 1 0 0 0 0 ??1 1 0 0 0 0 0 0 0 ????0 1 1 0 0 0 0 0 0 ??1 1 0 0 0 0 0 0 0 ??????1 0 0 0 0 0 0 0 0

A1,10?0,A1,10?4,A1,10?68,于是,从v1到v10通过9步 到是不可能的,而经过

(9)(11)(13)11步到的路线由4种,经过13步到的路线由68种.

图论处理问题思想独特，方法变化无穷，非正常思维情况多，要学好图论方法，更好的利用于解决实际问题，要多思考多练习。

１０２

本文来源：https://www.bwwdw.com/article/dp96.html