“数学建模”讲座：图论方法及其建模.doc

《“数学建模”讲座：图论方法及其建模.doc》由会员分享，可在线阅读，更多相关《“数学建模”讲座：图论方法及其建模.doc（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学建模讲座：数学建模中的图论方法图论是离散数学的重要组成部分，它对于自然科学、工程技术、经济管理和社会现象等诸多问题，能够提供有力的数学模型加以解决，特别在国内外大学生数学建模竞赛当中，有不少问题可以应用图论模型解决。我们在此有针对性地把图论的骨干概念和结论以及相关的有效算法做一简要介绍，愿听者增强图论建模的意识和能力。MCM中与图论有关的题目： 190-B 扫雪问题（二邮递员中国邮路问题） 求欧拉回路的Fleury算法 291-B 通讯网络的最小生成树 寻找最优Steiner树 392-B 应急电力修复系统 最小生成树算法 494-B 计算机网络的最小接通时间中国大学生数学建模竞赛试题：

2、1. 94-A 逢山开路利用求最短路的Dijkstra算法 94-B 锁具装箱DFS算法 2. 98-B 灾情巡视路线 多邮递员中国邮路问题 3. 99-B 钻井布局 4. 00-B 钢管订购和运输1 图论的基础知识图论中的“图”并不是通常意义下的几何图形或物体的形状图，而是以一种抽象的形式来表达一些确定的事物及其关系的一个数学系统。在历史上，图论的创立开始于对著名的七桥问题的研究。是18世纪欧洲的一个城市，位于河畔，河中有两个岛屿和，人们架设了七座桥把河岸和两个小岛连接起来。当时城中的居民热衷于讨论这样一个问题：要从任何一块陆地出发，能否通过每座桥一次且不重复，最后返回出发地(图1)？瑞士数

3、学家欧拉于1736年解决了这个问题，他发表了图论的第一篇论文（！），证明了七桥问题是无解的。同时他提出并解决了更为一般的问题，从而奠定了图论的基础。图1一.图的基本概念图G是由非空结点集以及边集所组成，记作。它的结点数称为阶。根据边有无方向，图分为有向图和无向图。有向图的边去掉方向后所得的图称为原有向图的基础图(或底图)。没有自环或多重边的图称简单图。有些实际问题抽象出来的图，边上往往带有信息，在边上附加一些数字来刻划此边，称权，此时该图称加权图。无向图中与结点v相关联的边数称为v的度数，记，有向图中以v为起点或终点的边数分别称为v的出度和入度，记。握手定理：（1）无向图中所有结点的度数之和等

4、于边数的两倍。 （2）有向图中所有结点的出度(入度)之和等于边数。推论：任何图的奇结点必为偶数个。例如，一群人中，有奇数个朋友的人必为偶数个。如果简单无向图的任两个结点均邻接，称之为完全图，n阶完全图记为，它的每个结点的度数等于,边数等于。若为n阶简单图，则在相应的完全图中去掉的所有边所得的图称为的补图，记为。一个边的序列(或点的序列)称路径，封闭的路径称回路。边不重复的路径称简单路径，点不重复的路径称基本路径。路径所含边的条数称为路径的长度。如果存在从结点u到v的路径，则称从u到v可达。如果u到v可达，则从u到v的路径中长度最短的路径称为短程线（或测地线），它的长度称为从u到v的距离,记为；

5、如果u到v不可达，则记。如果无向图G的任两个结点都可达，则称G为连通图。有向图的连通性复杂一些：若G中任意两结点间都相互可达，则称G是强连通的；若G中任意两结点间至少有一个结点可达另一个结点，则称G是单向连通(简称单连通)的；若G的基础图是连通的，则称G是弱连通的；否则称G是非连通图。若两个图的结点之间存在一个保持连接关系的双射,则称之为同构.设图，若存在双射函数，使保持连接关系，即之间的连接关系与之间的连接关系完全相同，在有向图时还要保持边的方向，多重图时还要有相同的重数，则称与同构，记为。下面给出几组同构的图（结点的对应关系如图所示）。图2二图的矩阵表示为适合使用计算机对图进行存储和处理，

6、需要用矩阵表示图。常用的有：邻接矩阵、可达性矩阵、距离矩阵等。定义 设n阶图的结点集，则n阶方阵称为G的邻接矩阵，其中aij表示以vi为起点、vj为终点的边的数目。一个图的邻接矩阵完整地刻划了图中各结点间的邻接关系。如图3，它们的邻接矩阵分别为：， v1v2v3v4图3 由邻接矩阵的定义，很容易得到以下结论：（1）无向图的邻接矩阵是对称的；（2）图没有平行边当且仅当的元素全为0或1；（3）图没有自环当且仅当的主对角元全为0；（4）图是零图当且仅当的元素全为0；（5）若是无向图，则 （6）若是有向图，则 定理 设n阶图G的结点集，A是G的邻接矩阵，则Ak中的元素等于G中从vi到vj的长度为k的路

7、径条数(，)。 如图3中的，分别表示从到长度为1，2，3，4的路径条数，各为1条，1条，2条，3条，请读者自己在图上进行验证，并找出各条路径。定义 设n阶图G的结点集，则n阶方阵称为G的可达矩阵，其中显然，无向图的可达矩阵是对称的，而有向图则不然。计算公式为：，其中，和分别表示布尔和与布尔积。 如图3中的可达矩阵为： 利用图的邻接矩阵和可达矩阵可以判断图的连通性，下面结果是显然的：(1) 无向图G是连通图当且仅当它的可达矩阵P的元素全为1；(2) 有向图G是强连通图当且仅当它的可达矩阵P的元素全为1；(3) 有向图G是单向连通图当且仅当它的可达矩阵P及其转置PT的布尔和中除主对角元外全为1；(

8、4) 有向图G是(弱)连通图当且仅当以它的邻接矩阵A及其转置AT的布尔和作为邻接矩阵而得到的可达矩阵的元素全为1。 另外，也可以利用图的可达性矩阵判断有无回路：图G中存在回路当且仅当它的可达性矩阵的主对角元不全为零。也可以利用可达矩阵求出无向图的连通分支等，请读者考虑具体的方法。三几类重要的图1无向树连通无回路图称为树。每个连通分支都是树的无向图称为森林下面图中，(a),(b),(c),(d)都是树，(e)是森林定理：若树的结点数为n，边数为m，则m=n-1。在结点数确定的情况下，树是连通图中边数最少的图，也是无回路图中边数最多的图每个连通图G至少有一个生成子图是一棵树，称之为G的生成树。显然

9、每个连通图都有生成树，而一般来说生成树不唯一(而边数是确定的)。例 设有6个城市，它们之间有输油管道连通，其布置图如图4.3(a)所示战争期间，为了保卫油管不被破坏，需派部队看守，看守一段油管需一连士兵为保证各城市间输油畅通，最少需派几连士兵？他们应驻于那些油管处？解：此问题即为寻找图4.3(a)的生成树问题由图知，结点数为6，故其生成树的边数为5，即最少需派5连士兵看守其看守地段可见图4.3(b)、(c)、(d)所画之线段图4.3如果G是一个加权连通图，我们希望找一棵权之和最小的生成树，称为最小生成树。2根树定义 一棵非平凡的有向树，如果恰有一个结点的入度为0，其余结点的入度均为1，则称此有

10、向树为根树入度为0的结点称为根，出度为0的结点称为叶，出度不为0的结点称为分枝点。习惯上我们把根树的根画在最上方，叶画在下方，有向边的方向均指向下方，这样就可以省去全部箭头。3.欧拉图如果图G中具有一条经过所有边的简单回路,称欧拉回路,含欧拉回路的图称为欧拉图；如果图G中具有一条经过所有边的简单(非回路)路径,称欧拉路。定理:(1)连通无向图G是欧拉图的充要条件是G的每个结点均为偶结点;(2) 连通无向图G含有欧拉路的充要条件是G恰有两个奇结点,且欧拉路必始于一个奇结点而终止于另一个奇结点.图7的所有结点均为偶结点，故为欧拉图，一条欧拉回路为：。图8有2个奇结点，故不是欧拉图，但有欧拉路：。从

11、欧拉回路和欧拉路的定义可知，图中的欧拉回路(欧拉路)是经过图中所有边的最短回路(路径)。图7 图8 图9 图10如图9是某街道图形。洒水车从A点出发执行洒水任务。试问是否存在一条洒水路线，使洒水车通过所有街道且不重复而最后回到车库B？此问题即为求证图中是否存在A到B的欧拉路。由于图中每个结点除A，B为奇结点外其余均为偶结点，由定理可知，这样的洒水线路是存在的，例如，ACDEFBGCFGAB或AGFEDCFBGCAB，等等。（蚂蚁比赛问题）如图10所示，甲、乙两只蚂蚁分别位于结点处，并设图中的边长度相等。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点处。如果他们的速度相同，问

12、谁先到达目的地？在图中，仅有两个奇结点，因而存在从到的欧拉路，蚂蚁乙走到只要走一条欧拉路，边数为9条；而蚂蚁甲要想走完所有的边到达，至少要先走一条边到达，再走一条欧拉路，因而它至少要走10条边才能到达，所以乙必胜。如图11(a)是一幢房子的平面图，前门进入一个客厅，由客厅通向四个房间。如果要求每扇门只能通过一次，现在由前门进入，能否通过所有的门走遍所有的房间（包括客厅），然后从后门走出？图11 将四个房间和一个客厅及室外作为接点，门作为边画出图(b)。由于b和e是仅有的两个奇结点，故从前门进、后门出的欧拉路是不存在的，即本题无解。如果把“前门进、后门出”这一条件去掉，则存在“每扇门通过一次且仅

13、一次”的走法。请读者找出具体的走法。4哈密尔顿图所谓哈密尔顿回路，起源于一个名叫“周游世界”的游戏，它是由英国数学家哈密尔顿（Hamilton）于1859年提出的。他用一个正十二面体的20个顶点代表20个大城市（图12(a)），这个正十二面体同构于一个平面图（图12(b)）。要求沿着正十二面体的棱，从一个城市出发，经过每个城市恰好一次，然后回到出发点。这个游戏曾风靡一时，它有若干个解。图12(b)给出了一个解。定义：如果图G中具有一条经过所有结点的基本回路（称哈密尔顿回路），则称为哈密尔顿图。虽然哈密尔顿图判定问题与欧拉图判定问题同样有意义，但遗憾的是至今为止还没有找到一个判别它的充分必要条件

14、，这是图论中尚未解决的主要问题之一。(a)图12 (b)5二部图定义 设无向图，如果存在的一个分划，使得G的每一条边的两个端点分属V1和V2，则称G为二部图(或偶图)。V1和V2称为互补结点子集，此时可将G记为。显然，二分图没有自环，在互补结点子集V1和V2内各结点互不邻接图13(a)给出了一个二分图的例子，它的互补结点子集为，图13如果V1的每个结点与V2的每个结点有且仅有一条边相关联，则称G为完全二部图，记为，其中。图13(b)给出了一个完全二部图。定理 无向图G=(V, E)是二部图的充分必要条件是G中无长度为奇数的回路。推论 非平凡树是二部图。与二部图的概念紧密相关的问题是匹配问题。设

15、是二部图，若，且M中任何两条边均不相邻，则称M是G的一个匹配；具有最大边数的匹配称为最大匹配；若最大匹配M满足，则称M是G的一个完备匹配，此时若，则称M为V1到V2的一个完备匹配；若，则称M是G的一个完美匹配在图14中，为G1中的最大匹配，G1中不存在完备匹配，更无完美匹配；G2中，为完备匹配，但G2中无完美匹配；在G3中，为完备匹配，同时也是完美匹配e3e1e2e1e2e3e2e1 图14下面给出存在完备匹配的充分必要条件Hall定理 设二分图，则G中存在从V1到V2的完备匹配当且仅当V1中任意k个结点至少邻接V2中的k个结点，定理中的条件称为相异性条件判断一个二分图是否满足相异性条件通常比

16、较复杂，下面给出一个判断二分图是否存在完备匹配的充分条件，对于任何二分图来说，都很容易确定这些条件因此，在考察相异性之前，应首先试用这个充分条件定理 设二分图，如果（1）V1中每个结点至少关联t条边；（2）V2中每个结点至多关联t条边，则G中存在从V1到V2的完备匹配，其中t为正整数（充分，不必要）定理中的条件通常称为t条件6.平面图如果无向图G有一种画法，使其没有非结点的交叉，则称G为平面图。波兰数学家Kuratowsky给出下面的重要结论： （1）K5与K3,3不是平面图。 （2）G是平面图的充分必要条件是G中不含与K5与K3,3同胚的子图。定理(欧拉公式) 设G是连通平面图，则有其中n为

17、结点数，m为边数，k为面数。推广：若平面图G有n个结点，m条边，k个面和(G)个连通分支，则有.2 综合例题例1 “死锁”问题下面举一个例子说明图的连通性在计算机科学中的应用在操作系统中允许多个进程同时工作，在进程工作时需要动态申请一些资源(如CPU，内存，外存，输入输出设备，编译程序等)，有时可能会出现一些冲突，如进程A占有资源R1且需要申请资源R2，而进程B占有资源R2且需要申请资源R1，此时两个进程均无法执行，这被称为计算机系统处于“死锁”状态可用有向图来模拟对资源的分配以及产生死锁的特征，从而便于检出和纠正死锁设是t时刻运行的程序集合，是t时刻所需的资源集合资源的分配状况如下：p1占有

18、资源r4且申请资源r1；p2占有资源r1且申请资源r2及r3；p3占有资源r2且申请资源r3；p4占有资源r3且申请资源r1及r4它们的资源分配情况可用图15表示图15显然，当且仅当分配图中含有多于一个结点的强连通分支时，或者含有回路时，计算机系统才在t时刻产生死锁。用矩阵方法可以计算出图中是否含有多于一个结点的强连通分支或是否含有回路，从而检测出是否存在死锁。例2 证明任意六个人的集会上，总会有三人互相认识或者不认识证明 这是1947年匈牙利数学竞赛出的一道试题，因为它很有趣且很重要，后来曾收录到美国数学月刊及其它数学刊物上。这类问题可以转化为图论中的完全图染色问题把参加集会的人看作结点，作

19、一个完全图，如果两个人认识，则两结点间的连线涂上红色，否则涂上蓝色问题转化为：无论怎样涂色，总可以找到红或蓝设六个结点为。从引出的边有五条，而颜色只有红蓝两种，由抽屉原理，至少有三条边同色，不失一般性，假定有三条边为红色。（1）如果结点之间至少有一条红边，比如是红边，则得到红色的三角形；（2）如果结点之间的边全是蓝色的，则得到蓝色的三角形。关于问题中的结点数，对任何，命题都成立但当时，命题便不成立了。这说明：不同的六个点是保证用两色涂染其边，存在同色三角形的最少点数。例3 出席某次国际学术会议的有六个成员a, b, c, d, e, f，其中：a会讲汉语、法语和日语；b会讲德语、日语和俄语；c

20、会讲英语和法语；d会讲汉语和西班牙语；e会讲英语和德语；f会讲俄语和西班牙语如将此六人分成两组，是否会发生同一组内的任意两人不能互相直接交谈的情况？ abdfec图18解 用结点表示成员，两成员间如有共同语言，则用边相连，可得图18由于图中的回路长度均为偶数，故此图为二部图设，当六位代表如此分组时，则同一组内的任意两个人都不能直接交谈例4 作为二叉树的一个应用，下面介绍一下有关前缀码的问题问题的提出：在通讯中，常用0和1的字符串作为英文字母来传递信息由于各个字母被使用的频率相差很大，人们希望将一些常用字的编码缩短，从而大大缩短信息串的总长但这就产生了一个问题：当我们用不同长度的序列去表示字母时

21、，在接收端的人如何将一长串的0和1准确无误地分割成字母对应的序列呢？例如，用00表示A，01表示B，0001表示T，那么当接收端收到信息串0001时，我们将不能分辨传递的内容是AB还是T为了避免发生这种混乱，我们在编码常常采用一种叫做前缀码的序列来表示英文字母定义 一个序列的集合，若这个集合的任何序列都不是另外序列的前缀，则这个序列集合称为前缀码例如，000，001，01，10，11是前缀码，而1，0001，000则不是前缀码前缀码与二叉树有一一对应的关系首先，任何一棵二叉树的树叶可对应一个前缀码若给定一棵二叉树，将每个分枝点的左侧的边标0，右侧的边标1，这样每片树叶将标定一个0和1的序列，它

22、是由树根到这片树叶的路径上各边的标号所组成的，显然没有一片树叶标号的序列是另一片树叶标号序列的前缀，因此这棵二叉树的树叶可对应一个前缀码另一方面，如给定一个前缀码，表示前缀码中最长序列的长度画一棵高度为的完全二叉树，并给每一分枝点射出的两条边标以0和1，这样对于长度不超过的每一个二进制序列必对应这棵二叉树的一个结点将对应于所给前缀码中没一个序列的结点给予一个标记，删除其余的结点，就得到一棵二叉树，它的树叶对应于给定的前缀码例如，给定前缀码000，001，01，10，11，则此前缀码对应的二叉树如图19所示根据上述二叉树，可对任意二进制序列进行译码，如可译为001，01，01，11，01，11，

23、01，10，10，10图19 又如，求图20所示两棵二叉树所产生的前缀码解: 图20（a）产生的前缀码为11，01，000，0010，0011；图20（b）产生的前缀码为01，10，11，000，0010，0011 图20 由以上产生的任一个前缀码都可以传输5个符号，比如A，B，C，D，E，都不会传错但由于字母出现的频率是不同的，用哪个序列代表哪个字母最省时间呢？这就是最优树问题，D.A.Haffman在1952年给出了一个极好的算法，有兴趣的读者可参阅有关资料例5 某中学有3个课外小组：英语组(A)、物理组(B)和生物组(C)，有5名学生a, b, c, d, e，(1)已知a, b为A组成

24、员，a, c, d为B组成员，c, d, e为C组成员；(2)已知a为A组成员，b, c, d为B组成员，b, c, d, e为C组成员；(3)已知a为A组成员，a又为B组成员，b, c, d, e为C组成员 问在以上三种情况下，能否各选出3名不兼职的组长？解： 根据三种已知情况，分别画出二部图，如图21所示记 ，(1) 在G1中，V1中的每个结点至少关联2条边，而V2中每个结点至多关联2条边，即满足t=2的t条件，故存在从V1到V2的完备匹配，图中粗边所示的匹配就是其中的一个(2) G2不满足t条件，但满足相异性条件，因而也存在从V1到V2的完备匹配，如图中粗边所示(3) G3既不满足t条件

25、，又不满足相异性条件，因而不存在完备匹配，故选不出3名不兼职的组长来图213 图论中的几个实用算法1加权图中的最短路径的Dijkstra算法最短路径问题：给定连接若干城市的铁路网，寻找从指定城市到各城市去的最短路线。数学模型：设是一个加权图，边的权记为，路径P的长度定义为路径中边的权之和，记为。两结点u和v之间的距离定义为 问题：在加权的简单连通无向图G(V,E,W)中，求一结点a(源点)到其它结点x的距离称单源问题。下面介绍1959年Dijkstra提出的单源问题的算法(至今仍公认是最好的算法)。它的基本思想是：若是从v1到vn的最短路径，则也必然是从v1到的最短路径。Dijkstra算法

26、把V分成两个子集S和T。初始时，； 对T中每一元素t计算，设，则即为a到x的距离； 。若，则stop，否则重复。说明： 表示从a到t的不含T中其他结点的最短路径的长度，但不一定是a到t的距离，但若，则即为a到x的距离； 计算的方法： 初始时，,设，记，则对，有。Dijkstra算法的时间复杂度为。例 在下面交通图中，权表示铁路的长度。求v1到v5的最短路径。属于S的点用方框表示，属于T的点用圆圈表示。解2求最小生成树的Kruskal算法和Prim算法筑路选线问题：欲修筑连接n个城市的铁路，已知i城与j城之间的铁路造价为Cij，设计一个线路图，使总造价最低。数学模型：在一个连通加权图上求权最小的

27、连通生成子图，显然，即求权最小的生成树，称最小生成树。（1） Kruskal算法（避圈法）1956年 设G为由n个顶点、m条边构成的加权连通图。先将G中所有的边按权的大小次序进行排列，不妨设， ； 若导出的子图不含回路，则； 若A中已有n-1条边，则；否则，转例：求图18(a)中加权图的最小生成树解： 用Kruscal算法可以求得最小生成树如图22(b)图22（2） Prime算法基本思想: (1) 先在中任取一个结点,并取入中；(2) 令 ,其中分别为的结点集；(3) 在所有连接的结点与的结点的边中,选出权最小的边,即(4) 将边取入中。重复(2)至(4)步骤,直至中的结点全部取入中为止。3

28、.中国邮路问题中国邮路问题(CPP Chinese Postman Problem)是在1960年由山东师范大学管梅谷教授首先提出并解决的中国邮路问题：邮递员传送报纸和信件，都要从邮局出发，经过他所管辖的每一条街道，最后回到邮局，要求最短的传送路线数学模型：在加权图上找一条经过所有边至少一次的回路，使它的权数最小。如果是欧拉图,则所求回路必为欧拉回路。下面给出在欧拉图上求取欧拉回路的Fleury算法。(1)Fleury算法(1) 任取起始结点,令；(2) 设路径 已选定,则从中选一边,使得:() 与相连(共端)；() 除非已无选择余地,不要选的桥(断边),即仍连通；(3) 重复步骤(2),直至

29、不能进行下去为止。(2)Edmonds-Johnson算法如果G不是欧拉图，即存在奇结点，这时某些边必被重复走过，我们称这样的边为重复边。考虑到奇结点必为偶数个，我们可以把奇结点划分成若干对，每对之间在G中有相应的最短路，将这些最短路的边以原来的权作为重复边叠加在原图上形成一个多重图G*，则G*是一个欧拉图，可用Fleury算法求出欧拉回路。问题是当G的奇结点较多时，可能有很多的配对方法，应怎样选择配对，使相应的欧拉回路的权最小呢？1973年，Edmonds和Johnson给出下面的算法：Edmonds-Johnson算法：设G是连通加权图,(1) 求出G的奇结点集 ；(2) 用Dijkstr

30、a算法求得V0中每对结点的距离；(3) 构作加权完全图:以为结点集,以为边的权；(4) 求中权之和最小的完备匹配M；(5) 用Dijkstra算法求M中边的端点之间在G中的最短路径；(6) 在(5)中求得的每条最短路径上每条边添加一条同权的新边,即得所求之欧拉图G*；(7) 在G*上用Fleury算法求一条欧拉回路,即为问题的解。也可由下面定理得到一个寻找中国邮路问题最优解的方法定理：L是图G中最短邮路的充分必要条件是：(1) G的每条边最多重复一次；(2)在G的任意一个回路上，重复边的长度之和不超过该回路长度的一半。根据该定理，首先选出奇结点，然后由条件(1)构造邮路，保证计算重复边之后每个

31、结点的度数为偶数，最后由条件(2)对所有回路进行判断，如果发现某个回路不满足条件(2)，则令该回路中重复的边变为不重复，而原来不重复的边改为重复，这种修改并不影响邮路的性质，待最后全部回路都满足条件(2)，该图的中国邮路问题就得解图16（a） (b) (c)图17在加权图16中，是奇结点，令边重复，如图17(a)，图中存在欧拉回路再由条件(2)，发现回路中重复边总长(9)大于非重复边的总长(4),故令代替，得到图17(b)在该图中又发现回路的重复边总长大于非重复边的总长，再令取代得到图17(c)至此条件(2)得到满足，故图17(c)中的任一条欧拉回路即为所求的中国邮路4.迷宫和DFS算法迷宫问

32、题：一座迷宫，游人事先未知其结构，如何搜索前进，保证万无一失地通过每一通道再从入口退出？我们玩迷宫游戏时，是这样玩的：从迷宫入口处出发，每个走廊都要搜索到，最后再从入口处出来。为了不兜圈子，我们可以记个暗号，标志哪些走廊已经走过，沿着未走过的通道尽可能远地走下去，走到死胡同底或那里已无未走过的走廊时，沿原路返回，到达一个路口，发现可通往一条未走过的走廊时，再沿这条未走过的走廊尽可能远地走下去，最后便可搜索遍全部走廊与厅室，再由入口处出迷宫了。上述过程启发人们设计出探索一个未知图结构的纵深搜索原则：任选一条未曾走过的通道就尽可能远地走下去，直至无未曾走过的路可走时，沿未逆行过的最晚来路返回，发现

33、有未走过的路，则沿它尽可能远地走下去，依次运行至重返入口止。1973年，Hopcroft和Tarjan把上述纵深搜索原则编写成下面的DFS(Depth First Search)算法.DFS算法(1) 标志所有边“未用过”,对每个结点,令, ；(2) ,；(3) 若v无未用过的关联边,转(5)；(4) 选一条与v关联的未用过的边,标志e“用过了”；若,转(3)；否则(即),转(2)；(5) 若,stop；(6) ,转(3)。其中k(v)是结点v的编码，称为v之父，v是f(v)之子，以父为尾、以子为头的有向边称为“父子边”。上述算法的时间复杂度为。上图所示的是DFS过程。容易证明，在DFS中每边

34、恰好通过两次，又返回出发点，且父子边们导出一棵生成树。例如，在地图是未知的情形下，双车道单车扫雪车，按右侧通行交通规则，依DFS算法的过程安排扫雪工作程序即可。5.TSP(货郎担问题)及“最邻近算法”一个与哈密尔顿图有密切关系的问题是所谓“货郎担”问题或“旅行商”问题(Travelling Salesman Problem)：货郎为了销售物品，要去访问若干个村、镇，然后回到自己所住的地方。假设每个村镇间都有路，那么他应该怎样设计所走的路线，使得能对每个村镇恰好访问一次且走的路程最短？用图论的话来讲就是：在一个加权的完全无向图中，如何寻找一条最短的哈密尔顿回路？解决上述问题的一个办法是“穷举法”

35、，即找出图中所有的哈密尔顿回路，求出其长度，然后找出最短的一条哈密尔顿回路。但当图中结点较多时，这种方法的计算量是相当惊人的(次加法,每秒百亿次,需1000多万年)，即使用高速计算机也很难完成，因而是无效算法。但迄今为止还没有找到一个解决“货郎担”问题的有效算法（多项式算法）。一般来讲，这个问题比哈密尔顿问题更加困难些。下面介绍一个近似解法“最邻近方法”（或称“贪婪算法”），这是实际工作中经常采用的方法： 选任意点作为始点，找出一个与始点最近的点，形成一条边的初始路径。然后用逐点扩充这条路径。 设x表示最新加到这条路径上的点，从不在路径上的所有点中，选一个与x最邻近的点，把连接x与此点的边加到

36、这条路径中。重复这一步，直到G中所有顶点包含在路径中。 把始点和最后加入的顶点之间的边放入，这样就得到一个回路。例 对加权完全无向图K5如图23(a)，如果从v1出发，使用“最邻近方法”得到的哈密尔顿回路如图23(b)，总距离为40；最小哈密尔顿回路的总距离为37（如图23(c)）。 (a)(b) (c)图23“抄近路算法”1. 求图中的一棵最小生成树T；2. 将T中各边均加一条与原边权值相同的平行边，设所得图为G*。显然G*是欧拉图；3. 求G*中的一条欧拉回路E；4. 在E中按如下方法求结点v出发的一条哈密尔顿回路：从v出发，沿E访问G*中各个结点，在没有访问完所有结点之前，一旦出现重复出

37、现的结点，就跳过它走到下一个结点。6.求可达矩阵的Warshall算法 给定n个结点的邻接矩阵，求G的可达性矩阵P。Warshall算法： 将图G的邻接矩阵送入中； ； ； 对，作： ，若,则转； ，若，则转，否则stop。7.判别连通性的算法给定n个结点的有向图的邻接矩阵，可判断该图是否为强连通的，单向连通的，或弱连通的。对于给定的邻接矩阵A，先用Warshall算法求出可达矩阵P。如果P的所有元素均为1，则所给有向图是强连通的；如果P的所有元素(除对角元外)满足：，则所给有向图是单向连通的。当所给有向图既不是强连通的，又不是单向连通的时候，我们改造邻接矩阵为：对于中所有的元素(除对角元外)

38、aij，若或，则且，所得矩阵记为A* (A*相当于原有向图的基础图的邻接矩阵)，再求出可达矩阵P*。如果P*的所有元素均为1，则原有向图是弱连通的；否则，原有向图不连通。进一步还可以求出各类连通分支。算法： 输入邻接矩阵； ； 调用求可达性矩阵子程序求出可达矩阵P； 调用判断强连通或单向连通子程序；若为强连通或单向连通的，则输出其标志，转；否则转； 改造A为A*，且； 调用求可达矩阵子程序求出可达矩阵P； 调用判断强连通或单向连通子程序；若为强连通的，则输出原有向图是弱连通的；否则，输出原有向图是不连通的； 。8.匈牙利算法分工问题：工作人员去做n件工作，每人适合做其中的一项或几项，问能否每人

39、都有一份适合的工作？如果不能，最多几人可以有适合的工作？数学模型：G是二分图,结点集划分为, ,当且仅当适合做工作时,求G中的最大匹配.解决这个问题可以用1965年Edmonds提出的匈牙利算法.匈牙利算法:(0) 从G中任取定一个初始匹配M；(1) 若M把X中的结点皆许配,stop, M即为完备匹配；否则,取X中未被M许配的一结点u,记,；(2) 若,stop,无完备匹配；否则,取；(3) 若y是被M许配的,设,令,转(2)；否则,取可增广路径,令,转(1)。这里,表示S中结点的邻集,表示对称差。算法的要点是把已有的匹配通过可增广路径逐次增广以至得到最大匹配。最佳分工问题：在分工问题中，工作

40、人员适合做的各项工作当中，效益未必一致，我们需要制定一个方案，使公司总效益最大。数学模型：在分工问题的模型中，图G的每边加了权，表示做工作的效益，求加权图G上的权最大的完备匹配。解决这个问题可以用Kuhn-Munkras算法，这里略去。4 其它问题1. 地图着色问题把无环图G的结点皆染上颜色，且使相邻的结点颜色不同，又所用的颜色最少，称这个颜色数为G的色数，记为。定理 设G为无环图，则，其中是G中结点的最大度数。1976年，Appel和Haken用计算机证明了下面的四色定理 若G是平面图，则。以图的着色为模型的实际问题非常之多，一般都是难解的问题。下面举几个例子。(1) 考试日程问题: 选修课

41、考试安排时,要避免任何一位学生所选不同课程在同一天考,问最少几天才能完成?数学模型: 以每门课程为结点,仅当两门课程被同一位学生选修时,在这两个结点之间连上一条边,构作一个图G,求取即为所求。(2) 存储安全问题: 某公司生产若干种化学制品,其中有些制品如果放在一起可能发生化学反应,引起危险.因此公司必须把仓库分成相互隔离的若干区.问至少要划分多少小区,才可安全存放?数学模型: 以每种货物为结点,仅当两种货物放在一起不够安全时,在这两个结点之间连上一条边,如此得到的图G的色数即为所求。(3) 频率分配问题: 地面上有若干无线电发射台,对每台分配一个频率供其使用,频率用自然数从1起编号,称为信道

42、号码,为排除同信道的干扰,要求使用同信道的发射台相距必须大于指定的正数d,问至少要几个信道?数学模型: 以为半径,以发射台为圆心作圆,仅当两圆有公共点时,在两个圆心之间加一边,以圆心为结点,得到图G (圆盘图),即为所求。2. 网络流的最大流问题把商品由产地运往市场，交通网上每个路段运输能力给定的条件下，设计一个运输方案，使得运输最快。1956年，Ford和Fulkson给出求最大流的2F算法。3. 规划审核技术与关键轨道方法规划审核技术PERT(Program evaluation and review technique)与关键轨道方法CPM(Critical path method)是典

43、型的统筹方法.总工期问题；赶工优化问题；工程设备量问题。4. 最小Steiner生成树问题Melzak算法5. 图的连通度破坏交通问题：游击队破坏敌人的铁路或公路，用炸毁车站、炸断桥梁或拆毁铁轨的游击战术。今欲使指定的两个车站间交通瘫痪，问至少要破坏两个指定车站以外的几个车站或几段铁路？数学模型：图的分离集与分离数。可靠通讯网的构作问题：我们要构作一个有线通讯网，使得敌人炸坏我几个通讯站之后，其余通讯站仍然能彼此通话，有两个要求应该得以满足，一个是不怕敌人炸毁的站数要多，一个是整体造价要低。数学模型：G是加权连通图，k是给定的自然数，求G的有最小权的k连通生成子图。1962年，Harary给出了一种解法。6. 覆盖集与控制集消防设施的安置：在一些交叉路口安置一些消防设施，只有与路口直接相连的街道才能使用它们。为使所有街道必要时都有消防设施可用，在哪些路口安置设施才最节省呢？数学模型：求最小覆盖集(Minimum Covering Set)。监狱看守问题：一座监狱的几间牢室有道路相连，看守要设在通过道路能直接监视所有牢室的地方。如果看守不得走动，那么他们应呆在某些牢室(即路口)所在地，问至少需要几名看守才能完成监视任务呢？数学模型：求最小控制集(Minimum Dominating Set)。