第4篇 图论之图论的应用

第4篇图论主讲人：任长安计算机与信息科学系2009.07引言

图论是在民间游戏当中孕育和诞生的，作为数学的一个分支已有两百多年的历史。图论的起源可以追溯到1736年由瑞士数学家欧拉(LeonhardEuler，1707-1783)撰写的一篇解决“哥尼斯堡七桥问题”的论文。哥尼斯堡是东普鲁士的一座城，流经该城的Pregel河将城市分为彼此之间由七座桥相连接的四个部分，如图1（a）所示。当时，一些好奇的市民尝试这样一个有趣的游戏：从一个地方出发，通过每座桥一次且仅一次，最后回到出发地，这样的路线是否存在？引言

欧拉在论文中给出了解决这个问题的很容易理解的简单证明，他将这个问题转化为图1（b）所示的问题，将被河流分割的城市四个部分用点从A、B、C、D来表示，而将七座桥用称为边的线段来表示，于是问题转化为：任何一点出发，是否存在通过每条边一次且仅一次又回到出发点的路？欧拉的结论是不存在这样的路。显然，问题的结果并不重要，最为重要的是欧拉解决这个问题的中间步骤，即抽象为图的形式来分析这个问题，当时来说，这是一种全新的思考方式，由此欧拉在他的论文中提出了一个新的数学分支，即图论，因此，欧拉也常常被图论学家称为“图论之父”。

引言

图1哥尼斯堡七桥问题引言

在欧拉之后，图论得到了迅速的发展。一些图论中的著名问题如四色问题(1852年)和哈密尔顿环游世界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫(G.R.Kirchoff)将树的概念和理论应用于工程技术的电网络方程组的研究。1857年英国的凯莱(A.Cayley)也独立地提出了树的概念，并应用于有机化合物的分子结构的研究中。1936年匈牙利的数学家哥尼格(D.Konig)发表了第一部集图论二百年研究成果于一书的图论专著《有限图与无限图理论》，这是现代图论发展的里程碑，标志着图论已经作为一门独立的学科。

引言

现代电子计算机的出现与广泛应用极大地促进了图论的发展和应用。在计算机科学中计算机科学的核心之一就是算法的设计与理论分析，而算法是以图论与组合数学为基础；图论与组合数学关系也非常密切，已正式成为计算机诸多分支中一种有力的基础工具。因而，作为计算机专业人员，了解和掌握图论的基本原理和方法是必要的。现在，它已成为系统科学、管理科学、运筹学、化学、经济学、网络理论、信息论、控制论等学科和理论研究中的重要数学工具，受到数学界和工程技术界越来越多广泛的重视。主要内容

1图的基本概念及表示2图的应用3树第9章图的应用本章讨论几类具有理论研究与实际应用意义的特殊图，包括欧拉图、汉密尔顿图、平面图、二分图、最短路径和关键路径问题等。这些图在计算机科学中具有广泛的应用，如数据库的实现、优化算法、工作分配、计算机网络等方面。本章主要介绍这些图的基本性质及其相关应用。

第9章图的应用主要内容：9.1欧拉图9.2哈密尔顿图9.3二分图与匹配9.4平面图9.5最短路径与关键路径9.1欧拉图图论的研究与应用中，常常需要以一种特殊的方式对图进行遍历，如经过图的每一条边或每一个结点一次且仅一次的遍历。欧拉图与哈密尔顿图就是讨论这些问题的经典图模型。在图论的开篇中，我们曾经提到过“哥尼斯堡七桥”问题。在该问题中，欧拉意识到陆地大小形状以及桥的长度等与求解问题是无关的，于是将实际的问题转化为多重图的模型。得到简化的图模型后，欧拉进一步注意到图的每一个结点的度数为奇数，如果从任何一结点出发，由于要构成回路，就必须回到该结点。但由于度数是奇数，且每条边

9.1欧拉图仅能遍历一次，故不可能再回到该结点，即不能构成回路。欧拉进一步得出了一个图存在欧拉回路的充分必要条件，有下面的定义与定理：一、欧拉图的定义

定义9.1.1

给定无孤立点图G，若存在一条回路，经过图中的每边一次且仅一次，该回路称为欧拉回路(Eulercircuit)。具有欧拉回路的图称为欧拉图(Eulergrpah)。若存在一条迹（通路），经过图中每边一次且仅一次，该条路称为欧拉迹（通路）(Eulertrail)。

9.1欧拉图定理9.1.1图G是欧拉图当且仅当G是连通的且每个结点的度数为偶数。

有了欧拉回路的判别定理，因此哥尼斯堡七桥问题立即有了确切的答案，因为有四个结点的度数皆为奇数，故欧拉路必不存在。

推论9.1.1连通图G是半欧拉图，当且仅当G恰有两个奇数度结点。且图中的欧拉迹一定始于一个奇数度结点而止于另一个奇数度结点。

9.1欧拉图而对于有向图，可以类似地有如下定义与定理：

定义9.1.2给定有向图G，通过图中每边一次且仅一次的一条单向回路（迹），称作单向欧拉回路（欧拉迹）。如果图G具有一条欧拉回路（欧拉迹），则称G为有向欧拉图（半欧拉图）。

定理9.1.2有向图G为欧拉图，当且仅当是连通的，且每个结点入度等于出度。一个有向图G具有单向欧拉路，当且仅当它是连通的，而且除两个结点外，每个结点入度等于出度，但这两个结点中，一个结点的入度比出度大1，另一个结点的入度比出度小1。

9.1欧拉图二、欧拉图的应用【例9.1.1】一笔画问题（笔不离开纸,不重复地画遍纸上图形的所有的边）请问图9.1中的各图能否一笔画出，如果不能，则需要几笔？

9.1欧拉图

【例9.1.2】设某封闭式小区的路网结构如图9.3所示，请证明能否设计出一条路线使得清洁车从小区大门出发清扫每条道路恰好一次，且在清扫完最后一条道路后正好返回小区大门处。9.1欧拉图9.1欧拉图【例9.1.3】中国邮路问题

中国邮路问题是我国数学家管梅谷先生在20世纪60年代提出来的。该问题描述如下：一个邮递员从邮局出发，到所管辖的街道投递邮件，最后返回邮局，若必须走遍所辖各街道中每一条至少一次，则怎样选择投递路线使所走的路程最短？

9.1欧拉图下面用图论的语言来描述：用图论的语言来描述，即在一个带权图G中，能否找到一条回路C，使C包含G的每条边最少一次且C的长度最短？

该问题求解思路大体包括三个方面：

1)若G没有奇数度结点，则G是欧拉图，于是欧拉回路C是唯一的最小长度的投递路线。

2)若G恰有两个奇数度结点vi和vj，则G具有欧拉迹，且邮局位于结点vi，则邮递员走遍所有的街道一次到达结点vj；从vj返回vi可选择其间的一条最短路径。这样，最短邮路问题转化为求vi到vj的欧拉迹和vj到vi的最短通路问题。

3)若G中奇数度结点数多于2，则回路中必须增加更多的重复边(路径）。这时，怎样使重复边的总长度最小？已有定理给出了判定条件，读者若有兴趣则请查阅相关文献。9.2哈密尔顿图

与欧拉回路非常类似的问题是哈密尔顿回路问题。哈密尔顿(WilliamRowanHamilton,1805-1865)是爱尔兰著名数学家，哈密尔顿发明了一种“周游世界”的游戏，有力地推动了图论的发展。哈密尔顿爵士是一位多产的数学家，他兴趣广泛，包括诗歌、天文学、光学以及数学（特别是代数），有趣的是，他在10岁时就学会了包括希腊语、阿拉伯语、波斯语在内的几乎所有的当时的语言。哈密尔顿的一个主要贡献就是他在柏林的运河边散步时发现的四元数相乘的方式。

1857年，哈密尔顿在给他的朋友的一封信中，首先谈到关于十二面体的一个数学游戏9.2哈密尔顿图

（如图9.5所示），能不能在图中找到一条环，使它含有这个图的结点一次且仅一次？他把结点看作是一座城市，连接两个结点的边看成是交通线，于是它的问题是能不能找到旅行路线，沿着交通线经过每一个城市恰好一次，再回到原来的出发地？他把这个问题称为周游世界问题。这个游戏扩展到一般的图上就是：给定一个图，是否能找到一个环，它通过图G的每个结点一次且仅一次?哈密尔顿的十二面体图上存在一条哈密尔顿环，按照结点编号的顺序：1-2-3…20-1。与欧拉图不同，确定一个图是否为哈密尔顿图是很困难的，目前还不存在有效的算法。但许多哈密尔顿图的充分条件都被证明,这里介绍其9.2哈密尔顿图中的两个。9.2哈密尔顿图一、哈密尔顿图的定义定义9.3给定图G，若存在一条通路经过图中的每一个结点恰好一次，这条路称作哈密尔顿通路(Hamiltonpath)。若存在一条回路，经过图中的每一个结点恰好一次，这个回路称作哈密尔顿回路(Hamiltoncycle)。具有哈密尔顿通路的图称为半哈密尔顿图，具有哈密尔顿回路的图称为哈密尔顿图(Hamiltongraph)。9.2哈密尔顿图

定理9.3设图G为n阶图，1)若G的每一对结点的度数之和都不小于n–1，那么G中有一条哈密尔顿路；2)若G的每一对不相邻的结点的度数之和不小于n，且n≥3，那么G为一哈密尔顿图。上述定理可作为判定哈密尔顿图的充分条件，但并非必要条件。下面介绍一个哈密尔顿图存在的必要条件。9.2哈密尔顿图定理9.4

若G是哈密顿图，则对于任意非空真子集S

V(G)，均有

ω(G-S)≤｜S｜其中,ω(G-S)为从G中去掉S中的结点及与这些结点关联的边后得到的图的连通分支数目。注：此定理给出的是必要条件，而不是充分条件。事实上，某些图满足条件，却不是汉密尔顿图。哈密尔顿图具有很好的应用意义，比如说旅行商人问题（TravelSalersProblem，TSP），时间分配问题等。9.2哈密尔顿图二、哈密尔顿图的应用1、旅行商问题同哈密顿图有密切关系的一个问题是旅行商人问题,也称为货郎担问题。这个问题有两种提法。一种是货郎到各村去卖货，再回到出发处，每村都要串到(仅到一次)，为其设计一条路线，使得所走路程最短。本问题的数学模型是在有权图G上求一个哈密顿环，使得

：W(C)==min{W(Ci)|W(Ci)为生成环的Ci的权}另一种提法是货郎每村都串到的次数不限，这在实际问题中更有应用意义。9.2哈密尔顿图从算法理论上讲，这两种提法的难度是相当的。下面考虑后一种提法，其难度相当大，其理由有二：(1)如何判定G是否为哈密顿图，至今尚无有效算法，也不知这种算法是否存在。(2)已知G是哈密顿图，至今亦无求G的哈密顿环的有效算法，这种算法的存在性问题也未解决。因此，货郎担问题的有效算法的存在问题，是当今图论中面临的一个难题。进化算法是对于求解大规模TSP问题较为有效的近似算法，是一种近年研究较多的模拟达尔文进化理论的算法，读者若有兴趣，请查阅相关文献。

9.2哈密尔顿图2、时间分配问题

考虑在七天内安排七门课程的考试，要求同一位教师所任教的两门课程考试不安排在接连的两天里，请应用有关图论性质证明：如果教师所担任的课程都不多于四门，则存在满足上述要求的考试安排方案。

解:设G为七个结点的图，每一个结点对应一门功课的考试，如果这两个结点对应的课程的考试是由不同教师担任的，那么这两个结点之间有一条边，因为每个教师所任的课程不超过4，故每个结点的度数至少是3，任两个结点度数的和至少是6，故根据定理9.3，G总包含一条哈密尔顿路，它对应于一个七门考试课目的一个适当安排。9.2哈密尔顿图3、座位安排问题

令有a、b、c、d、e、f、g7个人，已知下列事实：a会讲英语； b会讲英语和汉语；c会讲英语、意大利语和俄语； d会讲日语和汉语；e会讲德语和意大利语； f会讲法语、日语和俄语；g会讲法语和德语。试问这7个人如何排座位，才能使每个人都能和他身边的人交谈？9.3二分图与匹配某公司现有一些工作需要完成，其雇员可以胜任各种不同的工作，如何分配才能达到最大的工作效率呢？也就是如何建立雇员集合与工作集合间的一种一一映射关系，以满足各种条件？又如，学院需要给一批优秀的学生奖励一批学校推荐的书籍，每个学生的可能仅对学校推荐的部分图书感兴趣，那么，学院应该如何分配这些图书，以尽可能能够满足学生的要求并尽可能将学校推荐的图书奖励给学生？其实，这样的问题在大公司或现代管理中尤其重要。这类问题以图的匹配为理论模型，而二分图的匹配是其重要内容。9.3二分图与匹配一、二分图定义9.4

若无向图G=<V,E>的点集V可以划分成两个子集V1和V2，使V1∪V2=V，V1∩V2=Φ，并使图中每一条边的端点一个在V1中，另一个在V2中，则称图G为二分图（或二部图）。在二分图中，V1的每一个结点都和V2的每一个结点相关联，则称为完全二分图，记为km,n。其中|V1|=m，|V2|=n。9.3二分图与匹配例如，图9.8所示就是一个二分图。对于二分图的判定，有下面的定理：定理9.5图G是二分图当且仅当G中所有的环长度均为偶数。9.3二分图与匹配二、二分图的匹配虽然在任意的非平凡图中都可以找到匹配，但是大多数匹配问题都涉及到二分图。

定义9.3.2

设G为二分图，X,Y为其两个子集，E为边集，M

E。如果M中任何两条边都没有公共端点，称M为G的一个匹配（Matching）。G的所有匹配中边数最多的匹配称为最大匹配（Maximalmatching）。如果X或Y中任一结点均为匹配M中边的端点，那么称M为X或Y-完全匹配(Perfectmatching)。若M既是X-完全匹配又是Y-完全匹配，则称M为G的完美匹配。9.3二分图与匹配【例9.3.1】

图9.9中各图的粗线表示匹配中的边（简称匹配边）。（b）中匹配是最大的，X-完全的，（c）中匹配是完美的（从而也是最大的）。9.3二分图与匹配注意:最大匹配总是存在但未必唯一。此外，X(Y)-完全匹配及完美匹配必定是最大的，但反之则不然；X(Y)-完全匹配未必存在。对前面所述的安排工作问题，若令V1为全体人员的集合，V2为全部工作的集合，则从V1到V2的完美匹配即是给每个人都分配一项工作。反之亦可使每项工作都有一人做。下面介绍一个求二分图中最大匹配的算法——匈牙利算法，它是1965年由Edmonds提出的。此算法解决的实际问题是分工问题：某公司有工作人员x1，x2，…，xn，他们去做工作y1，y2，…，yn，每人适合做其中的一项或几项工作，问能否每人都分配一项合适的工作。9.3二分图与匹配这个问题的数学模型是：G是二分图，结点集划分为X∪Y=V，X=｛x1，x2，…，xn｝，Y=｛y1，y2，…，yn｝，当且仅当xi适合干工作yj时，(xi，yj)∈E。问G中是否有最大匹配?

要能理解这个算法，首先需要有下面的定义与定理。定义9.3.3

设M是G的一个匹配，若在G中有一条路，它的边在E—M和M中交错地出现，则称该路为关于M的交错路。若关于M的交错路的起点和终点不是关于M饱和的，则称该路为关于M的增广路。（注：M-饱和点：M中包含的边所关联的顶点。）9.3二分图与匹配由增广路的定义可以看出，若图G中存在关于M的增广路P，显然P中属于E—M中的边比属于M中的边多一条，则M′=M⊕P是匹配，且｜M′｜＞｜M｜，故M一定不是最大匹配。定理9.3.2

在图G中，M是最大匹配的充要条件是G中不存在关于M的增广路。

对这一定理的证明，实际上给出了一个寻找最大匹配的办法。即先给任一匹配，从中找出一条增广路，然后修改匹配，重复这一过程直到不存在增广路为止。这就是匈牙利算法：9.3二分图与匹配

1)从G中取一个初始匹配M；

2)若X中每一点关于M饱和，则结束，M即为完美匹配；否则，取X中未被M匹配的一结点u，记S=｛u｝，T=Φ；

3)若N(S)=T，则结束，无完美匹配；否则，取y∈N(S)-T；

4)若y关于M饱和，设边(y，z)∈M，S∪｛z｝→S，T∪｛y｝→T，转2)；否则，取可增广路P(u，y)，令ME(P)→M，转1)。9.3二分图与匹配现在讨论完美匹配的存在条件。首先需要定义一个概念：图G的任意一个结点子集A

V，所有与A中结点相邻的结点全体，称为A的邻集，记为N(A)。定理9.3.3

(Hall定理)设二分图G(V1，V2)，G中含有从V1到V2的完美匹配的充要条件是，对于任何A

V1，有｜N(A)｜≥｜A｜。

当二分图是平衡的时候，Hall定理被称为婚姻定理，其含意是：如果一个村子里每一位姑娘恰好认识k个小伙子，每个小伙子也恰好认识k位姑娘，则每位姑娘能和她所认识的一个小伙子结婚，并且每个小伙子也能和他所认识的一位姑娘结婚。

9.3二分图与匹配【例9.3.2】有n台计算机和n个磁盘驱动器。每台计算机与m(m>0)个磁盘驱动器兼容，每个磁盘驱动器与m台计算机兼容。则为每台计算机匹配一台与它兼容的磁盘驱动器可能吗？

定理9.3.4如果G(V1，V2)是一个k—正则二分图(k＞0)，则G有一个完美匹配。

【例9.3.3】

Bernoulli-Euler错放信笺问题：某人给六个人各写了一封信，准备了六个写有收信人地址的信封，问有多少种投放信笺的可能，使每封信笺与信封上写的收信人不相符?9.3二分图与匹配

解:首先将问题转化为图论中的问题，以结点xi表示信笺，结点yi表示信封(i=1，2，3，4，5，6)，xl与yk有边，表示信笺与信封不相符。于是问题变为求的二分图G=K6，6中有多少个完美匹配。

现设G中完美匹配的个数为φ(6)。x1与y2相配时，完美匹配的个数等于从图G中删除结点x1与y2后所得的图Gx1，y2中完美匹配的个数，这个数记为ψ(5)。在Gx1，y2中，若x2与y1相配，则ψ(5)=φ(4)；若x2不与y1相配，则ψ(5)=φ(5)。于是G中x1与y2相配时，可得φ(5)+φ(4)个完美匹配；同理，x1与yj(3≤j≤6)相配时，亦有φ(5)+φ(4)个完美匹配，故φ(6)=5(φ(5)+φ(4))；同理可得9.3二分图与匹配

φ(5)=4(φ(4)+φ(3))，

φ(4)=3(φ(3)+φ(2))，φ(3)=2(φ(2)+φ(1))，而φ(2)=1，φ(1)=0，故得φ(6)=265，即可能有265种投放错误。

一般地，对n封信有递推公式：

φ(n)=(n-1)(φ(n-1)+φ(n-2))，φ(2)=1。9.4平面图

如果一个图能够在平面上画出且各边不相交，即嵌入平面，则称该图为平面图，所画出的图称为该图的一个平面嵌入。可以用平面图来求解如下问题：要在三座房屋H1，H2，H3和三个设施（水、电、气）之间建立管线连接，问是否可能使这些线路互不相交？如果用结点表示工作点，用边表示传输管线，那么上述问题便可描述为：图K3,3是否可以在一个平面上图示出来，而使图中各边均不相交？这个问题其实就是判断K3,3是否为平面图。事实上，计算机科学中的印刷电路板设计或运筹学中的场地布局、交通道路等问题中，平面图都起着至关重要的作用。9.4平面图

与平面图紧密相关的一个主题就是图的着色，这是图论中最为重要最具影响力的主题，也具有很好的应用。如常见的会议或考试日程的安排等、与调度和指派等有关的问题。本节将结合应用对平面图的性质进行讨论。一、平面图及其性质一个图表面看起来不是平面的，但通过移动结点与像橡皮筋一般弯曲边，最后画出的图可能就是平面图。如有图9.10所示，图G未画成平面图，但图G1、G2是G的两种平面嵌入，可见G是平面图。

9.4平面图

前面提及的K3,3是平面图吗？K5呢？

9.4平面图

如图9.11所示，无论如何移动结点与改变边的画法，K3,3中存在边的交叉，G1为K3，3一种画法，边(2,5)与(3,4)存在交叉；如图G1,对于K5亦是如此，边(2,4)与(3,5)存在交叉，如图G2。不难看出，上述边的交叉主要原因在于K3,3中结点5与2或者K5中结点2与4分别位于环1-4-3-6-1与1-3-5-