第4篇 图论之图论的应用课件

1、第4篇 图论主讲人：任长安计算机与信息科学系2009.07引言 图论是在民间游戏当中孕育和诞生的，作为数学的一个分支已有两百多年的历史。图论的起源可以追溯到1736年由瑞士数学家欧拉(Leonhard Euler，1707-1783)撰写的一篇解决“哥尼斯堡七桥问题”的论文。哥尼斯堡是东普鲁士的一座城，流经该城的Pregel河将城市分为彼此之间由七座桥相连接的四个部分，如图1（a）所示。当时，一些好奇的市民尝试这样一个有趣的游戏：从一个地方出发，通过每座桥一次且仅一次，最后回到出发地，这样的路线是否存在？引言 欧拉在论文中给出了解决这个问题的很容易理解的简单证明，他将这个问题转化为图1（b）所

2、示的问题，将被河流分割的城市四个部分用点从A、B、C、D来表示，而将七座桥用称为边的线段来表示，于是问题转化为：任何一点出发，是否存在通过每条边一次且仅一次又回到出发点的路？欧拉的结论是不存在这样的路。显然，问题的结果并不重要，最为重要的是欧拉解决这个问题的中间步骤，即抽象为图的形式来分析这个问题，当时来说，这是一种全新的思考方式，由此欧拉在他的论文中提出了一个新的数学分支，即图论，因此，欧拉也常常被图论学家称为“图论之父”。引言 图1 哥尼斯堡七桥问题引言 在欧拉之后，图论得到了迅速的发展。一些图论中的著名问题如四色问题(1852年)和哈密尔顿环游世界问题(1856年)也大量出现。同时出现了

3、以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫(G.R.Kirchoff)将树的概念和理论应用于工程技术的电网络方程组的研究。1857年英国的凯莱(A.Cayley)也独立地提出了树的概念，并应用于有机化合物的分子结构的研究中。1936年匈牙利的数学家哥尼格(D.Konig) 发表了第一部集图论二百年研究成果于一书的图论专著有限图与无限图理论，这是现代图论发展的里程碑，标志着图论已经作为一门独立的学科。 主要内容 1 图的基本概念及表示2 图的应用3 树第9章 图的应用本章讨论几类具有理论研究与实际应用意义的特殊图，包括欧拉图、汉密尔顿图、平面图、二分图、最短路径和关键路径

4、问题等。这些图在计算机科学中具有广泛的应用，如数据库的实现、优化算法、工作分配、计算机网络等方面。本章主要介绍这些图的基本性质及其相关应用。 9.1 欧拉图图论的研究与应用中，常常需要以一种特殊的方式对图进行遍历，如经过图的每一条边或每一个结点一次且仅一次的遍历。欧拉图与哈密尔顿图就是讨论这些问题的经典图模型。在图论的开篇中，我们曾经提到过“哥尼斯堡七桥”问题。在该问题中，欧拉意识到陆地大小形状以及桥的长度等与求解问题是无关的，于是将实际的问题转化为多重图的模型。得到简化的图模型后，欧拉进一步注意到图的每一个结点的度数为奇数，如果从任何一结点出发，由于要构成回路，就必须回到该结点。但由于度数是

5、奇数，且每条边 9.1 欧拉图仅能遍历一次，故不可能再回到该结点，即不能构成回路。欧拉进一步得出了一个图存在欧拉回路的充分必要条件，有下面的定义与定理：一、欧拉图的定义 定义9.1.1 给定无孤立点图G，若存在一条回路，经过图中的每边一次且仅一次，该回路称为欧拉回路(Euler circuit)。具有欧拉回路的图称为欧拉图(Euler grpah)。若存在一条迹（通路），经过图中每边一次且仅一次，该条路称为欧拉迹（通路）(Euler trail)。 9.1 欧拉图定理9.1.1 图G是欧拉图当且仅当G是连通的且每个结点的度数为偶数。 有了欧拉回路的判别定理，因此哥尼斯堡七桥问题立即有了确切的答

6、案，因为有四个结点的度数皆为奇数，故欧拉路必不存在。 推论9.1.1 连通图G是半欧拉图，当且仅当G恰有两个奇数度结点。且图中的欧拉迹一定始于一个奇数度结点而止于另一个奇数度结点。 9.1 欧拉图二、欧拉图的应用【例9.1.1】 一笔画问题（笔不离开纸,不重复地画遍纸上图形的所有的边） 请问图9.1中的各图能否一笔画出，如果不能，则需要几笔？ 9.1 欧拉图【例9.1.2】 设某封闭式小区的路网结构如图9.3所示，请证明能否设计出一条路线使得清洁车从小区大门出发清扫每条道路恰好一次，且在清扫完最后一条道路后正好返回小区大门处。9.1 欧拉图【例9.1.3】中国邮路问题 中国邮路问题是我国数学家

7、管梅谷先生在20世纪60年代提出来的。该问题描述如下：一个邮递员从邮局出发，到所管辖的街道投递邮件，最后返回邮局，若必须走遍所辖各街道中每一条至少一次，则怎样选择投递路线使所走的路程最短？ 9.1 欧拉图 下面用图论的语言来描述：用图论的语言来描述，即在一个带权图G中，能否找到一条回路C，使C包含G的每条边最少一次且C的长度最短？ 该问题求解思路大体包括三个方面： 1) 若G没有奇数度结点，则G是欧拉图，于是欧拉回路C是唯一的最小长度的投递路线。 2) 若G恰有两个奇数度结点vi和vj，则G具有欧拉迹，且邮局位于结点vi，则邮递员走遍所有的街道一次到达结点vj；从vj返回vi可选择其间的一条最

8、短路径。这样，最短邮路问题转化为求vi到vj的欧拉迹和vj到vi的最短通路问题。 3) 若G中奇数度结点数多于2，则回路中必须增加更多的重复边(路径）。这时，怎样使重复边的总长度最小？已有定理给出了判定条件，读者若有兴趣则请查阅相关文献。 9.2 哈密尔顿图 与欧拉回路非常类似的问题是哈密尔顿回路问题。哈密尔顿 (William Rowan Hamilton, 1805-1865) 是爱尔兰著名数学家，哈密尔顿发明了一种“周游世界”的游戏，有力地推动了图论的发展。哈密尔顿爵士是一位多产的数学家，他兴趣广泛，包括诗歌、天文学、光学以及数学（特别是代数），有趣的是，他在10岁时就学会了包括希腊语、

9、阿拉伯语、波斯语在内的几乎所有的当时的语言。哈密尔顿的一个主要贡献就是他在柏林的运河边散步时发现的四元数相乘的方式。 1857年，哈密尔顿在给他的朋友的一封信中，首先谈到关于十二面体的一个数学游戏9.2 哈密尔顿图 （如图9.5所示），能不能在图中找到一条环，使它含有这个图的结点一次且仅一次？他把结点看作是一座城市，连接两个结点的边看成是交通线，于是它的问题是能不能找到旅行路线，沿着交通线经过每一个城市恰好一次，再回到原来的出发地？他把这个问题称为周游世界问题。这个游戏扩展到一般的图上就是：给定一个图，是否能找到一个环，它通过图G的每个结点一次且仅一次? 哈密尔顿的十二面体图上存在一条哈密尔顿

10、环，按照结点编号的顺序：1-2-320-1。与欧拉图不同，确定一个图是否为哈密尔顿图是很困难的，目前还不存在有效的算法。但许多哈密尔顿图的充分条件都被证明,这里介绍其9.2 哈密尔顿图 中的两个。9.2 哈密尔顿图一、哈密尔顿图的定义定义9.3 给定图G，若存在一条通路经过图中的每一个结点恰好一次，这条路称作哈密尔顿通路(Hamilton path)。若存在一条回路，经过图中的每一个结点恰好一次，这个回路称作哈密尔顿回路(Hamilton cycle)。具有哈密尔顿通路的图称为半哈密尔顿图，具有哈密尔顿回路的图称为哈密尔顿图(Hamilton graph)。 9.2 哈密尔顿图定理9.4 若G

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

12、题的数学模型是在有权图G上求一个哈密顿环，使得： W(C)= = minW(Ci)|W(Ci)为生成环的Ci的权 另一种提法是货郎每村都串到的次数不限，这在实际问题中更有应用意义。 9.2 哈密尔顿图2、时间分配问题考虑在七天内安排七门课程的考试，要求同一位教师所任教的两门课程考试不安排在接连的两天里，请应用有关图论性质证明：如果教师所担任的课程都不多于四门，则存在满足上述要求的考试安排方案。解: 设G为七个结点的图，每一个结点对应一门功课的考试，如果这两个结点对应的课程的考试是由不同教师担任的，那么这两个结点之间有一条边，因为每个教师所任的课程不超过4，故每个结点的度数至少是3，任两个结点度

13、数的和至少是6，故根据定理9.3，G总包含一条哈密尔顿路，它对应于一个七门考试课目的一个适当安排。9.2 哈密尔顿图3、座位安排问题令有a、b、c、d、e、f、g 7个人，已知下列事实：a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲日语和汉语；e会讲德语和意大利语；f会讲法语、日语和俄语；g会讲法语和德语。试问这7个人如何排座位，才能使每个人都能和他身边的人交谈？9.3 二分图与匹配某公司现有一些工作需要完成，其雇员可以胜任各种不同的工作，如何分配才能达到最大的工作效率呢？也就是如何建立雇员集合与工作集合间的一种一一映射关系，以满足各种条件？又如，学院需要给一批优秀的学生奖励

14、一批学校推荐的书籍，每个学生的可能仅对学校推荐的部分图书感兴趣，那么，学院应该如何分配这些图书，以尽可能能够满足学生的要求并尽可能将学校推荐的图书奖励给学生？其实，这样的问题在大公司或现代管理中尤其重要。这类问题以图的匹配为理论模型，而二分图的匹配是其重要内容。 9.3 二分图与匹配一、二分图定义9.4 若无向图G=的点集V可以划分成两个子集V1和V2，使V1V2=V，V1V2=，并使图中每一条边的端点一个在V1中，另一个在V2中，则称图G为二分图（或二部图）。在二分图中，V1的每一个结点都和V2的每一个结点相关联，则称为完全二分图，记为km,n。其中|V1|=m，|V2|=n。9.3 二分图

15、与匹配例如，图9.8所示就是一个二分图。对于二分图的判定，有下面的定理：定理9.5 图G是二分图当且仅当G中所有的环长度均为偶数。9.3 二分图与匹配二、二分图的匹配虽然在任意的非平凡图中都可以找到匹配，但是大多数匹配问题都涉及到二分图。 定义9.3.2 设G为二分图，X,Y为其两个子集，E为边集，M E。如果M中任何两条边都没有公共端点，称M为G的一个匹配（Matching）。G的所有匹配中边数最多的匹配称为最大匹配（Maximal matching）。如果X或Y中任一结点均为匹配M中边的端点，那么称M为X或Y-完全匹配(Perfect matching)。若M既是X-完全匹配又是Y-完全匹

16、配，则称M为G的完美匹配。 9.3 二分图与匹配【例9.3.1】 图9.9中各图的粗线表示匹配中的边（简称匹配边）。（b）中匹配是最大的，X-完全的，（c）中匹配是完美的（从而也是最大的）。 9.3 二分图与匹配注意:最大匹配总是存在但未必唯一。此外，X(Y)-完全匹配及完美匹配必定是最大的，但反之则不然；X(Y)-完全匹配未必存在。 对前面所述的安排工作问题，若令V1为全体人员的集合，V2为全部工作的集合，则从V1到V2的完美匹配即是给每个人都分配一项工作。反之亦可使每项工作都有一人做。下面介绍一个求二分图中最大匹配的算法匈牙利算法，它是1965年由Edmonds提出的。此算法解决的实际问题

17、是分工问题： 某公司有工作人员x1，x2，xn，他们去做工作y1，y2，yn，每人适合做其中的一项或几项工作，问能否每人都分配一项合适的工作。9.3 二分图与匹配 这个问题的数学模型是：G是二分图，结点集划分为XY=V，X=x1，x2，xn，Y=y1，y2，yn，当且仅当xi适合干工作yj时，(xi，yj)E。问G中是否有最大匹配? 要能理解这个算法，首先需要有下面的定义与定理。定义9.3.3 设M是G的一个匹配，若在G中有一条路，它的边在EM和M中交错地出现，则称该路为关于M的交错路。若关于M的交错路的起点和终点不是关于M饱和的，则称该路为关于M的增广路。（注：M-饱和点：M中包含的边所关联

18、的顶点。）9.3 二分图与匹配由增广路的定义可以看出，若图G中存在关于M的增广路P，显然P中属于EM中的边比属于M中的边多一条，则M=MP是匹配，且MM，故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，则结束，无完

19、美匹配；否则，取yN(S)-T；4) 若y关于M饱和，设边(y，z)M，SzS，TyT，转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位姑娘，则每位姑娘能和她所认

20、识的一个小伙子结婚，并且每个小伙子也能和他所认识的一位姑娘结婚。 9.3 二分图与匹配【例9.3.2】 有n台计算机和n个磁盘驱动器。每台计算机与m(m0)个磁盘驱动器兼容，每个磁盘驱动器与m台计算机兼容。则为每台计算机匹配一台与它兼容的磁盘驱动器可能吗？ 定理9.3.4 如果G(V1，V2)是一个k正则二分图(k0)，则G有一个完美匹配。 【例9.3.3】 Bernoulli-Euler错放信笺问题：某人给六个人各写了一封信，准备了六个写有收信人地址的信封，问有多少种投放信笺的可能，使每封信笺与信封上写的收信人不相符?9.3 二分图与匹配解: 首先将问题转化为图论中的问题，以结点xi表示信笺

21、，结点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(3j6)相配时，亦有(5)+(4)个完美匹配，故(6)=5(5)+(4)；同理可得9.3 二分图与匹配 (5)=4(4)+(3)， (4)

22、=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

23、,3是否为平面图。事实上，计算机科学中的印刷电路板设计或运筹学中的场地布局、交通道路等问题中，平面图都起着至关重要的作用。9.4 平面图与平面图紧密相关的一个主题就是图的着色，这是图论中最为重要最具影响力的主题，也具有很好的应用。如常见的会议或考试日程的安排等、与调度和指派等有关的问题。本节将结合应用对平面图的性质进行讨论。一、平面图及其性质 一个图表面看起来不是平面的，但通过移动结点与像橡皮筋一般弯曲边，最后画出的图可能就是平面图。如有图9.10所示，图G未画成平面图，但图G1、G2是G的两种平面嵌入，可见G是平面图。 9.4 平面图前面提及的K3,3是平面图吗？K5呢？ 9.4 平面图如图

24、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-1中，显然，要在这两对结点间添加边，必然要发生交叉。把图的最少交叉点次数称为图的交叉数。K3,3与K5的交叉数均为1。 9.4 平面图9.4 平面图定义 在平面图G的一个平面表示中，由边所包围的其内部不包含图的结点和边的区域，称为G的一个面(Surface)，包围该面的诸边所构成的

25、回路称为这个面的边界(Bound)，面r的边界的长度称为该面的次数(Degree)，记为D(r)。区域面积有限的面称为有限面(Finite Surface)，区域面积无限的面称为无限面(Infinite Surface)。平面图有且仅有一个无限面。如图9.12所示：9.4 平面图图9.129.4 平面图定理 平面图中所有面的次数之和等于边数的二倍。证明 因任何一条边，或者是两个面边界的公共边，或者是在一个面中作为边界被重复计算两次，故平面图所有面的次数之和等于其边数的二倍。1750年，欧拉发现，任何一个简单连通平面图，若有n个顶点、m条棱和r个面，则有n-m+r = 2。这个公式可以推广到平面

26、图上来，称之为欧拉公式。 9.4 平面图如果一个平面图(n,m)的面数用f表示，则常使用G(n,m,f)来表示该平面图。Euler发现了平面图的结点数、边数、面数之间的关系，即定理9.4.1 (欧拉定理) 令G为连通的平面图，其结点数、边数，面数分别为n，m，f，则有n -m+f=2欧拉定理所得到的公式称为欧拉公式。需要说明的是，对于非连通图，可以对其分图讨论其平面性，因此本节讨论的平面图都指连通图。9.4 平面图根据欧拉定理，容易得到如下平面图的结点与边关系的结论： 定理9.4.2 如果G是n(n2)个结点m条边的平面图，则有m3n-6. 上述定理中不等式中等式成立的条件是每一个面都由3条边

27、围成（称这些面的次数为3），此时，平面图的面数不能再增加，称这样的平面图为极大平面图（注意到：如果一个面的次数大于3，则可以在该面上的任意二不相邻的结点间添加一条边，则不会破坏平面图的平面性，但平面图的面数增加了）。 9.4 平面图二、平面图的判定图9.13为著名的彼得森(Peterson)图，容易看出它是非平面图，但如何证明？ 9.4 平面图 首先介绍图的细分的概念，即给定图G，在G的边上插入任意数量的2度结点，则得到图G的一个细分图。其实就是将G的边用路径替换。如图9.14所示，G1、G2均为G的细分，当然也可以认为G也是自身的细分。 9.4 平面图定理9.11 (Kuratowski定理

28、) 图G是平面图，当且仅当K5与K3,3的任何细分图都不是G的子图。 这里不对该定理作证明，但容易注意到，细分图并不改变原图的平面性，因此，若K5与K3,3的任何细分图是某图G的子图，则G显然是非平面图。9.5 最短路径与关键路径问题一、最短路径问题为了应用图论的方法解决实际问题，除了将实际问题化为图外，有时还需要将一些附加信息赋给图的边和顶点。这些信息通常与实际问题中数量指标有关。如果图的边和顶点都附加上一个实数，这个图就成了一个带权图。定义9.7 图G的每一条边ei都存在一个实数wi与之对应，称wi是边ei的权，称为边带权图；图G的每个顶点vi都存在一个实数wi与之对应，称wi是顶点vi的

29、权，G和顶点上的权称为点带权图；带权图通常表示成，其中W是边集或点集到实数上的函数。9.5 最短路径与关键路径问题带权图是研究许多实际问题所需要的，本章许多问题将涉及到。下面讨论本章通路应用的一个常见问题最短路径问题。最短路径问题直接应用于生产实际中，如各种管道的铺设、线路的安排、运输网络的最少时间问题、最少费用问题、互联网网络中路由问题等。这里的路径指的是图中的一条初级通路，一条路径的权是该初级通路收纳所有边权之和。最短路径问题就是在图中寻找从一个顶点到另一个顶点的权最小的路径。9.5 最短路径与关键路径问题较好的解决办法是由迪基克斯特（E.W.Dijkstra）在1959年提出的算法，即D

30、ijkstra算法，解决了由固定点到其他任意点的最短路径问题。该算法的主要思想是利用点到集合的最短路径替换两点间的最短路径。假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：9.5 最短路径与关键路径问题1) 初始化。起源点设置为： ds=0, ps为空; 所有其他点: di=, pi=?; 标记起源点s，记k=s,其他所有点设为未标记的。2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设

31、置：dj=mindj, dk+lkj式中，lkj是从点k到j的直接连接距离。3) 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i：di=mindj, 所有未标记的点j9.5 最短路径与关键路径问题点i就被选为最短路径中的一点，并设为已标记的。4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：i=j*5) 标记点i。如果所有点已标记，则算法完全退出，否则，记k=i，转到2) 再继续。下面具体应用Dijkstra算法寻找最短路径。9.5 最短路径与关键路径问题例9.10求图9.15中顶点v1到v7的最短路径。9.5 最短路径与关键路径问题解 通常以表

32、格的形式来简化整个过程。表中每行有且仅有一个顶点被置定，置定值放入方框内，形式为Wj(r) / vi，表示顶点vj被置定，即获得标号*，而vi在从v1到vj的最短路径上，并与vj 相邻。每行都是先计算具体值，第一行是直接写出固定点的值为0，其他为，其他行是利用上一行的置定值计算；然后选择本行的最小值并置定，从而为计算下一行做准备。 9.5 最短路径与关键路径问题9.5 最短路径与关键路径问题这里的例子是有向图，实际在算法描述上是针对的一般图，即不管是有向图，还是无向图，算法都相同。如前所述，Dijkstra算法是解决固定点到其他任意点最短路径的较好方法。解决图中任意顶点之间最短路径当然也可以利

33、用Dijkstra算法，但也可以利用其他的算法实现，例如Floyd算法。Floyd算法是运用矩阵形式表示，找出最短路径和路由矩阵，计算出带权图的最短路径，其具体算法思想在此就不再详细描述，读者可参考相应的数据结构书籍对Floyd算法的详细介绍。 9.5 最短路径与关键路径问题二、关键路径问题关键路径问题是求带权有向图中两个顶点之间的最长路径问题，主要应用于规划评审的时间问题。如一个项目的时间规划，由于项目中有许多工作，一些工作必须在某些工作完成后才能开始，有些工作可以同时进行，如果将这些工作和时间画成图论的有向图，则以顶点表示各个状态，有向边表示各个工作过程，而以有向边的权表示完成工作所需要的时间。这时，从项目开始和项目结束有一条很长的路径，这是完成项目所需要的时间，如果这条线上的工作提前或拖后多9.5 最短路径与关键路径问题长时间，这条线路仍然一直是最长路径，则整个项目就会相应提前或拖后多少时间，显然这条路径上的工作是整个项目的关键所在，所以该路径成为“关键路径”，其他路径就是非关键路径；规划要求尽量先保证关键路径上的人力、物力需求，这可从非关键路径上挖潜力、要支援关键路径。 9.5 最短路径与关键路径问题定义9.8 一个连通的边带权有向图