离散数学课件第十章-几种图的介绍

第第十十章章 几种图的介几种图的介绍绍离散数学离散数学 陈志奎主编陈志奎主编人民邮电出版社人民邮电出版社前言n自从1736年欧拉（L.Euler）利用图论的思想解决了哥尼斯堡（Konigsberg）七桥问题以来，图论经历了漫长的发展道路。在很长一段时期内，图论被当成是数学家的智力游戏，解决一些著名的难题，曾经吸引了众多的学者。图论中许多的概论和定理的建立都与解决这些问题有关。n1859年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即绕行世界。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个问题后来就叫做哈密顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的关注和研究。前言n在图论的历史中，还有一个最著名的问题四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。四色猜想有一段有趣的历史。每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接。所以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。前言n在电子计算机问世后，图论的应用范围更加广泛，在解决运筹学、信息论、控制论、网络理论、博奕论、化学、社会科学、经济学、建筑学、心理学、语言学和计算机科学中的问题时，扮演着越来越重要的角色，受到工程界和数学界的特别重视，成为解决许多实际问题的基本工具之一。n本章将结合图论基础知识，进一步介绍一些常用的基本图类，如欧拉图、哈密尔顿图、二部图、平面图、网络等，除研究每种图类的本质特征之外，都力求结合一些实际问题来阐明图论的广泛可应用性，介绍一些最基本的图论算法，使读者对图的理论和应用这两个方面都有一定的了解。PART PART 0101欧拉图主要内容PART PART 0 02 2哈密尔顿图PART PART 0 03 3二部图及匹配PART PART 0 04 4平面图PART PART 0 05 5网络PART PART 0 06 6图的示例分析10.1欧拉图n定义10.1图G中包含其所有边的简单开路径称为图G的欧拉路径，图G中包含其所有边的简单闭路径称为G的欧拉闭路。图10.1哥尼斯堡七桥图10.2哥尼斯堡七桥问题的图610.1欧拉图n例10.1图10.3中（a）是欧拉闭路，（c）是欧拉路径，（b）既不是欧拉路径也不是欧拉闭路。图10.3710.1欧拉图n定义10.2每个结点都是偶结点的连通无向图称为欧拉图。每个结点的出度和入度相等的连通有向图称为欧拉有向图。n例10.2图10.4中（b）是欧拉有向图。图10.4810.1欧拉图n定理10.1设G是连通无向图，G是欧拉图，当且仅当G有欧拉闭路。910.1欧拉图n定理10.2设G=为连通无向图，且，则G有一条从至的欧拉路径当且仅当G恰有两个奇结点和。1010.1欧拉图n定理10.3设G为弱连通的有向图。G是欧拉有向图，当且仅当G有欧拉闭路。n定理10.4设G为弱连通有向图。和为G的两个不同结点。G有一条从至的欧拉路径，当且仅当=+1，=-1，且对G的其他结点v有=1110.1欧拉图n定理10.5如果和是可运算的欧拉图，则是欧拉图。由定理10.5可得图10.5图10.512PART PART 0101欧拉图主要内容PART PART 0 02 2哈密尔顿图PART PART 0 03 3二部图及匹配PART PART 0 04 4平面图PART PART 0 05 5网络PART PART 0 06 6图的示例分析10.2哈密尔顿图n爱尔兰数学家哈密尔顿（WilliamHamilton）爵士1859年提出了一个“周游世界”的游戏。这个游戏把一个正十二面体的二十个顶点看成地球上的二十个城市。棱线看成是连接城市的航路（航空、航海线或陆路交通线），要求游戏者沿棱线走，寻找一条经过所有结点（即城市）一次且仅一次的回路，如图10.6（a）所示。也就是在图10.6（b）中找一条包含所有结点的圈。图（b）中的粗线所构成的圈就是这个问题的回答。n与欧拉图不同，哈密尔顿图是遍历图中的每个结点，一条哈密尔顿回路不会在两个结点间走两次以上，因此没有必要在有向图中讨论。14图10.610.2哈密尔顿图n爱尔兰数学家哈密尔顿（WilliamHamilton）爵士1859年提出了一个“周游世界”的游戏。这个游戏把一个正十二面体的二十个顶点看成地球上的二十个城市。棱线看成是连接城市的航路（航空、航海线或陆路交通线），要求游戏者沿棱线走，寻找一条经过所有结点（即城市）一次且仅一次的回路，如图10.6（a）所示。也就是在图10.6（b）中找一条包含所有结点的圈。图（b）中的粗线所构成的圈就是这个问题的回答。n与欧拉图不同，哈密尔顿图是遍历图中的每个结点，一条哈密尔顿回路不会在两个结点间走两次以上，因此没有必要在有向图中讨论。15图10.610.2哈密尔顿图n定义10.3给定无向图G，图G中包含其所有顶点的简单开路径称为图G的哈密尔顿路径，图G中包含其所有顶点的简单闭路径称为G的哈密尔顿回路。具有哈密顿回路的图称为哈密尔顿图。由定义可知哈密尔顿圈与哈密尔顿路通过图G中的每个结点一次且仅一次，例如图10.6（b）就是哈密尔顿图（哈密尔顿圈用实线标出）。1610.2哈密尔顿图n例10.3图10.7中，图（a）、（b）中有哈密尔顿圈，图（c）中有哈密尔顿路，（d）中既没有哈密尔顿圈也没有哈密尔顿路。图10.7哈密尔顿图和欧拉图相比，虽然考虑的都是遍历问题，但是侧重点不同。欧拉图遍历的是边，而哈密尔顿图遍历的是结点。另外两者的判定困难程度也不一样，前面我们已经给出了判定欧拉图的充分必要条件，但对于哈密尔顿图的判定，至今还没有找出判定的充要条件，只能给出若干必要条件或充分条件。1710.2哈密尔顿图n定理10.6若G是哈密尔顿图，则对于结点集的任一非空真子集有。其中表示在G中删去S中的结点后所构成的图，表示的连通分支数。18哈密尔顿图的必要条件可用来判定某些图不是哈密尔顿图，只要能够找到不满足定理条件的结点集V的非空子集S。10.2哈密尔顿图n例10.4图10.8（a）不是哈密尔顿图。图10.8（a）中共有9个结点，如果取结点集S=3个白点，即。而这时（如图（b）。这说明图10.8（a）不是哈密尔顿图。但要注意若一个图满足定理10.6的条件也不能保证这个图一定是哈密尔顿图，如图10.8（c）。19图10.810.2哈密尔顿图n定理10.7设图G是具有n（3）个结点的无向简单图，如果G中每一对结点度数之和大于等于n-1，则在G中存在一条哈密尔顿路。n定理10.8若G是具有n（3）个结点的无向简单图，对于G中每一对不相邻的结点均有，则G是一个哈密尔顿图。定理10.7和10.8都是充分条件，即满足这些条件的图一定是哈密尔顿图。但不是所有的哈密尔顿图都满足这些条件。例如图10.9是哈密尔顿图,但它不满足上述定理的条件。20图10.910.2哈密尔顿图n例10.5某地有5个风景点。若每个景点均有两条道路与其它景点相通，问是否可经过每个景点恰好一次而游完这5处？解：将景点作为结点，道路作为边，则得到一个有5个结点的无向图。由题意，对每个结点，有则对任两点，均有可知此图一定有一条哈密尔顿路，本题有解。2110.2哈密尔顿图n例10.6今有和7人，已知下列事实。a讲英语；b讲英语和汉语；c讲英语、意大利语和俄语；d讲日语和汉语；e讲德国和意大利语；f讲法语、日语和俄语；g讲法语和德语。试问这7个人应如何排座位，才能使每个人都能和他身边的人交谈？22解：设无向图，其中图G是连通图，如图10.10（a）所示。将这7个人排座围圆桌而坐，使得每个人能与两边的人交谈，即在图10.10（a）中找哈密尔顿回路。经观察该回路是。即按照图10.10（b）安排座位即可。PART PART 0101欧拉图主要内容PART PART 0 02 2哈密尔顿图PART PART 0 03 3二部图及匹配PART PART 0 04 4平面图PART PART 0 05 5网络PART PART 0 06 6图的示例分析10.3二部图及匹配n定义10.4设无向图G=。如果存在V的划分,，使得中的任何两个结点都不相邻（i=1,2），则称G为二部图，和称为G的互补结点子集。显然，二部图没有自圈。与二部图的一条边关联的两个结点一定分属于两个互补结点子集。一般来说，二部图的互补结点子集的划分不是唯一的。如图10.11的二部图，和是它的互补结点子集，和也是它的互补结点子集。图10.11二部图2410.3二部图及匹配n一个无向图如果能画成上面的样式，很容易判定它是二部图。有些图虽然表面上不是上面的样式，但经过改画就能成为上面的样式，仍可判定它是一个二部图，如图10.12中（a）可改画成图（b），图（c）可改画成图（d）。可以看出，它们仍是二部图。图10.122510.3二部图及匹配n定理10.9设G是阶大于1的无向图。G是二部图，当且仅当G的所有回路长度均为偶数。n定义10.5设和是简单二部图G的互补结点子集，如果中的每个结点与中的每个结点相邻，则称G为完全二部图。我们把互补结点子集分别包含m和n个结点的完全二部图记为。图10.14画出了的两个图示。很重要，我们在讨论图的平面性时还要用到它。2610.3二部图及匹配n二部图的主要应用是匹配，“匹配”是图论中的一个重要内容，它在所谓“人员分配问题”和“最优分配问题”等运筹学中的问题上有重要的应用。n首先看实际中常碰见的问题：给n个工作人员安排m项任务，n个人用表示。并不是每个工作人员均能胜任所有的任务，一个人只能胜任其中个任务，那么如何安排才能做到最大限度地使每项任务都有人做，并使尽可能多的人有工作做？n例如，现有5个人，5项工作。已知能胜任和，能胜任和，能胜任和，能胜任和，能胜任、和。如何安排才能使每个人都有工作做，且每项工作都有人做？2710.3二部图及匹配n显然，我们只需构造这样的数学模型：以和（i，j=1，2，3，4，5）为顶点，在与其胜任的工作之间连边，得二部图G，如图10.15所示，然后在G中找一个边的子集，使得每个顶点只与一条边关联（图中粗线），问题便得以解决了。这就是所谓匹配问题，下面给出匹配的基本概念和术语。图10.15匹配问题示意图2810.3二部图及匹配n定义10.6设无向图G=，（1）如果不包含自圈，并且中的任何两条边都不邻接，则称为G中的匹配。（2）如果是G中的匹配，并且对于G中的一切匹配，只要必有，则称为G中的极大匹配。（3）G中的边数最多的匹配称为G中的最大匹配。（4）G中的最大匹配包含的边数称为G的匹配数。显然，最大匹配一定是极大匹配，而极大匹配不一定是最大匹配。在一个无向图中，可以有多个极大匹配和最大匹配。2910.3二部图及匹配n例10.7在图10.16中，a,c，a,c,g，a,f，b,e，b,g，b,f,h，c,h，c,p，d,g，d,h，f,p是极大匹配，其中a,c,g和b,f,h是最大匹配。匹配数是3。图10.163010.3二部图及匹配n定义10.7设和是二部图G的互补结点子集。如果G的匹配数等于，则称G中的最大匹配为到的完美匹配。显然，只有V2V1时可能存在从V1到V2的完美匹配。但这个条件并不是充分条件。如图10.16给出的二部图中，V1a1,a2,a3,a4,V2p1,p2,p3,p4,p5,p6,V2V1，但并不存在V1到V2的完美匹配。下面的定理给出了存在完美匹配的充分必要条件。图10.16无向图中的匹配3110.3二部图及匹配n定理10.10设和是二部图G的互补结点子集。存在到的完美匹配，当且仅当对于任意,，其中当二部图的结点数目比较大时，定理10.10用起来不太方便，下面给出存在完美匹配的一个充分条件，判断二部图是否存在完美匹配时，可以先用这个充分条件，如果得不出结论，再用定理10.10。3210.3二部图及匹配n定理10.11设V1和V2是二部图G的互补结点子集，t是正整数。对于V1中的每个结点，在V2中至少有t个结点与其邻接。对于V2中的每个结点，在V1中至多有t个结点与其邻接。则存在V1到V2的完美匹配。33PART PART 0101欧拉图主要内容PART PART 0 02 2哈密尔顿图PART PART 0 03 3二部图及匹配PART PART 0 04 4平面图PART PART 0 05 5网络PART PART 0 06 6图的示例分析10.4平面图n例10.8一个工厂有3个车间和3个仓库。为了工作需要，车间与仓库之间将设专用的车道。为避免发生车祸，应尽量减少车道的交叉点，最好是没有交叉点，这是否可能？如图10.17（a）所示，A，B，C是3个车间，M，N，P是3座仓库。经过努力表明，要想建造不相交的道路是不可能的，但可以使交叉点最少（如图10.17（b）所示）。此类实际问题涉及到平面图的研究。近年来，由于大规模集成电路的发展，也促进了平面图的研究。本节介绍平面图的一些基本概念和常用结论。图10.173510.4平面图n定义10.8在一个平面上，如果能够画出无向图G的图解，其中没有任何边的交叉，则称图G是个平面图；否则，称G是非平面图。直观上说，所谓平面图就是可以画在平面上，使边除端点外彼此不相交的图。应当注意，有些图从表面上看，它的某些边是相交的，但是不能就此肯定它不是平面图。3610.4平面图n例10.9对于图10.18（a）（b）中的无向图来说，试把该图解加以重画之后，它将不包含任何边的交叉，如图10.17（e）（f）所示。因此，由图10.17（a）（b）给出的图是平面图，而（c）（d）不是。图10.183710.4平面图n设G=V，E，是能够画于平面上的图解中的无向图，并且设C=v1v2v3v4v1是图G中的任何基本循环。此外，设xv1v3和xv2v4是图G中的任意两条不交叉的基本路径。在图10.19中给出了两种可能的结构。显然，x和x或都在基本循环C的内部，或者都在基本循环C的外部，当且仅当G是个非平面图。因为这时基本路径x和x是相互交叉的。用视察法证明给定图的非平面性时，上述的简单性质甚为有用。图10.193810.4平面图n例10.10设有一个电路，它含有两个结点子集V1和V2，且有|V1|=|V2|=3。用导线把一个集合中的每一个结点，都与另外一个集合中的每一个结点连通，如图10.20所示。试问，是否有可能这样来接线，使得导线相互不交叉。对于印刷电路，避免交叉具有实际意义。解：这个问题等价于判定图10.20中的图是否是个平面图。可以看出，给定图中有一个基本循环C=v1v6v3v5v2v4v1，如图10.21所示。39图10.20图10.2110.4平面图n试考察三条边v1，v5，v2，v6，v3，v4，上述每条边或是处于循环C的内部，或是处于C的外部。显然，三条边中至少有两条边同时处于C的同一侧，因此避免不了交叉，如图10.22所示。故给定的图是非平面图。图10.224010.4平面图n下面就来阐明库拉托夫斯基（Kuratowski，波兰数学家）定理。试考察图10.23中的两个图。在例10.10中已经证明了图10.20中的图是个非平面图。把图10.20加以改画以后，就能够得到图10.23（a）。由此可见，图10.20同构于图10.23（a），因此图10.23（a）也是个非平面图。另外，采用该例中所使用的方法，也能证明图10.23（b）也是个非平面图。这两个非平面图都称为库拉托夫斯基图。图10.234110.4平面图n在图10.24中，给出了两个图解。如图10.24（a）所示，试往图中的一条边上，插上一个新的次数为2的结点，把一条边分解成两条边，则不会改变给定图的平面性。另外，如图10.24（b）所示，把联系于一个次数为2的结点的两条边，合并成一条边，也不会改变给定图的平面性。图10.244210.4平面图n定义10.9设G1和G2是两个无向图。如果G1和G2是同构的，或者是通过反复插入和（或）删除次数为2的结点，能够把G1和G2转化成同构的图，则称G1和G2在次数为2的结点内是同构的。n例10.11图10.25中的4个图，在次数为2的结点内是同构的。图10.254310.4平面图n定理10.12设G是一个无向图。图G中不存在任何与图10.23中的两个图同构的子图，当且仅当图G是个平面图。称为库拉托夫斯基定理。n例10.12根据库拉托夫斯基定理证明图10.26中的（彼得森图）是非平面图。图10.254410.4平面图n定义10.10多边形的图的归纳法定义如下。一个多边形是一个多边形的图。设G=是一个多边形的图，再设P=viu1u2ul-1vj是长度为l1的任何基本路径，它不与图G中任一路径交叉，且有vi，vjV，但是对于n=1,2,，l-1来说，unV。于是，由图G和P所构成的图G=也是一个多边形的图，其中V=Vu1，u2，ul-1E=Evi，u1，u1，u2，ul-1，vj多边形的图是个平面图（或多重边图，因为允许长度为2的循环存在），它能够把平面划分成数个区域，每一个区域都是由一个多边形定界。4510.4平面图n例10.13图10.27中的图是一个多边形的图。图10.27多边形的图4610.4平面图n定义10.11由多边形的图定界的每一个区域，都称为图G的面。例如，图10.27中的区域F1，F2，F3等等，都是该多边形图的面。n定义10.12包含有多边形的图G的所有面的边界的多边形，称为G的极大基本循环。例如，图10.27中的循环v1v2v3v4v5v6v7v1，就是该多边形的图的极大基本循环。应该说明，给定图G的极大基本循环外侧的无限区域，是另外一个面，一般称为G的无限面。事实上，如果把图G的图解画在球面上，则G的无限面与其它的有限面并没有什么区别。4710.4平面图n定义10.13如果图G的两个面共有一条边，则称这样的两个面是邻接的面。n定理10.13（欧拉公式）设G=是个具有k个面（包括无限面在内）的(n,m)多边形的图。则nm+k=2。4810.4平面图n例10.14在图10.28中，给出了一个多边形的图(实线画出的)和它的对偶(虚线画出的)，就说明了上述方法。由上述的构成方法不难看出，每一个多边形的图G，其对偶图也必定是一个多边形的图，而且G和G*是互为对偶的。49图10.28对偶图10.4平面图n定义10.14如果多边形的图G的对偶G*同构于G，则称G是自对偶图。n例10.15在图10.29中，给出了一个自对偶图。50图10.29自偶图10.4平面图n定理10.14若平面图是自对偶图，且有n个结点，m条边，则n定义10.15平面图的正常着色(简称着色，是指对的每个结点指派一种颜色，使得相邻结点都有不同的颜色)。若可用n种颜色对图G着色，则称G是n可着色的。对图G着色时，需要的最少颜色数称为G的着色数，记为5110.4平面图n定理10.15（四色定理）任何简单平面图都是4可着色的。n定理10.16（五色定理）任何简单平面图，均有52PART PART 0101欧拉图主要内容PART PART 0 02 2哈密尔顿图PART PART 0 03 3二部图及匹配PART PART 0 04 4平面图PART PART 0 05 5网络PART PART 0 06 6图的示例分析10.5网络n定义10.16一个网络N=(V,A)是指一个连通无环且满足下列条件的有向图。（1）有一个顶点子集X，其每个顶点的入度都是0。（2）有一个与X不相交的顶点子集Y，其每个顶点的出度都为0。（3）每条弧都有一个非负的权值，称为弧的容量。上述网络N可以记作N=(V,X,Y,A,C)，其中，X称为网络的源点集，Y称为网络的汇点集，V和A分别为顶点集和弧集，网络中的除源点和汇点之外的顶点称为中转点。源点和汇点在实际网络中对应于网络的入口和出口，或者说计算机网络的源结点和目的结点。5410.5网络nC为网络的容量函数，容量函数是定义在弧集A上的非负函数。在实际网络中，它对应于相应路线上的通行能力，如公路的宽度、计算机网络的带宽等。n例如，在图10.33所示的网络中，x1,x2是源点集，y1,y2是汇点集。其他结点是中转结点，弧上的数字表示弧的容量。图10.33网络示例5510.5网络n如果一个网络中的源点集和汇点集都只包含一个顶点，我们称该网络为单源单汇网络。事实上，对于任意网络N=(V,X,Y,A,C)，在经过一定的处理后，都可以转变为一个单源单汇网络。处理的方法为：（1）给网络N添加两个新的顶点s和t。（2）对任意xX，从s向x添加一条弧，其容量为（或）。（3）对任意yY，从y向t添加一条弧，其容量为（或）。其中，N+(x)表示顶点x的出邻点集合u|(x,u)A，N-(y)表示顶点y的入邻点集合u|(u,y)A。新添加的顶点s和t分别称为人工源和人工汇。5610.5网络n简单地说，只需要在原有非单源单汇网络中添加一个新的源点和一个新的汇点，并且添加从新的源点指向原有源点的弧，再添加从原有汇点指向新的汇点的弧，就能得到一个单源单汇网络。图10.34单源单汇网络n对图10.33所示的网络添加人工源和人工汇后，将变为图10.34所示的单源单汇网络。单源单汇网络是一种特殊的网络，它在各种网络问题的求解方面比非单源单汇网络更为简单。由于任意网络都可以转化为单源单汇网络，后续章节中对网络流的讨论都可以只考虑单源单汇网络。5710.5网络n在一些实际应用中，需要考虑弧和顶点都有容量限制的网络。例如，在某些网络中，需要考虑结点的缓存大小，此时结点的转发能力会受到限制。结点能力的限制并不能直接在图上体现出来，对于这样的情况，可以做一个转换，其方法为：将中转能力受限的结点分裂为两个结点，并且在这两个结点之间加入一条弧，这样就可以利用这条新加入的弧来表示结点的转发能力受限。n经过转化为单源单汇网络并将结点能力的受限转化为弧的受限后，实际网络问题可以转化为图论中的网络问题。5810.5网络n定义10.17可行流为：网络N=(V,X,Y,A,C)中的一个可行流是指定义在A上的一个整值函数f，使得：（1）对任意aA，0f(a)c(a),（容量约束）；（2）对任意vV-(XY)，f-(v)=f+(v)，（流量守恒）。其中，f-(v)表示点v处入弧上的流量之和，即流入v的流量之和，f+(v)表示点v处出弧上的流量之和，即从v流出的流量之和。59网络流10.5网络n也就是说，可行流满足两个条件：一是容量约束，即可行流在某一弧上的流量小于该弧的容量；二是流量守恒，即流入某一中转点的流量等于流出该点的流量。n需要强调的是，可行流总是存在的，如果f(a)=0，这个流称为零值流。对于网络N中任意可行流f和任意顶点子集S，从S中流出的流量记为f+(S)，它表示从S中顶点指向S外顶点的弧上的流量之和；流入S的流量记为f-(S)，表示从S外顶点指向S中顶点的弧上流量之和。60网络流10.5网络n定义10.18设f是网络N=(V,X,Y,A,C)中的一个可行流，则必有f+(X)=f-(Y)。f+(X)（或f-(Y)）称为流f的流量，记为Valf。流是网络中的重要概念，在实际网络问题中，经常需要求解与流相关的问题，例如网络的最大流等。所谓最大流，是指网络N中流量最大的可行流。网络的最大流对于实际应用具有重要意义，例如，公路网络中获得最大的运输量、计算机网络中获得最大的转发增益等等。为了得到网络的最大流，L.R.Ford和D.R.Fulkerson在1956年提出了著名的最大流最小割定理，巧妙地将流与割对应起来，将最大流问题转化为最小割问题。61流量10.5网络n定义10.19设N=(V,x,y,A,C)是一个单源单汇网络。假设网络中的某些顶点组成集合S，SV，=V-S。我们用(S,)表示尾在S中而头在中的所有弧的集合（即从S中的顶点指向S之外顶点的所有弧的集合）。如果，而，则称弧集(S,)为网络N的一个割。n一个割(S,)的容量是指(S,)中各条弧的容量之和，记为Cap(S,)。6210.5网络n定义10.19设N=(V,x,y,A,C)是一个单源单汇网络。假设网络中的某些顶点组成集合S，SV，=V-S。我们用(S,)表示尾在S中而头在中的所有弧的集合（即从S中的顶点指向S之外顶点的所有弧的集合）。如果，而，则称弧集(S,)为网络N的一个割。n一个割(S,)的容量是指(S,)中各条弧的容量之和，记为Cap(S,)。6310.5网络n例如，在图10.24中所示的单源单汇网络N中，令S=s,x1,x2,v2，则割(S,)=x1v1,x2v1,v2y1,v2y2，割的容量Cap(S,)=11。对网络N中的任意流f和任意割(S,)，流f的流量等于流出S的流量与流入S的流量之差，即Val f=f+(S)-f-(S)。网络N可能存在多个割，各个割的容量并不一定相等，其中容量最小的一个割称为网络N的最小割。即：如果网络N不存在割使得，则割K称为网络N的最小割。6410.5网络n定理10.17最大流最小割定理的基本内容为：任一网络N=(V,X,Y,A,C)中，最大流的流量等于最小割的容量。实际上，割就是一个弧的集合，如果去掉这些弧，就可以把网络“分割”成分别包含了源点和汇点的两部分。由于从源点到汇点必须要经过这些弧，因此，如果能求出最小的割集，就能得到最大流。最大流最小割定理对于求解最大流具有非常重要的指导意义，关于怎样求解网络的最大流，我们将在下一节介绍。6510.5网络n定义10.20设P=uv1ukv是网络N=(V,x,y,A,C)中一条u-v路，若弧A，则称此弧为u-v路P的一条正向弧（或称前向弧、顺向弧），若弧A，则称此弧为u-v路P的一条反向弧（或称后向弧、逆向弧）。将u-v路P所经过的弧（无论正向弧还是反向弧）称为路P上的弧。66在图10.35中的网络N中，x-y路P=xv1v3v4y上，所有弧都是正向弧；而在x-y路Q=xv2v4v3y上，弧和是正向弧，而和是反向弧。可以看出，对于同一条弧，在路P中为正向弧，而在路Q中为反向弧。可见，一条弧是正向弧还是反向弧与路的选择有关。10.5网络n定义10.21假设f是网络N=(V,X,Y,A,C)中的一个可行流，u是N中任意一点，P是网络N中的一条x-u路，如果对路P上的任一条弧a，都有：（1）若弧a是P的正向弧，则c(a)-f(a)0；（2）若弧a是P的反向弧，则f(a)0。则称P是N的一条f可增x-u路。特别的，N中的一条f可增x-y路可简称为N的一条f可增路。对于N中任意一条f可增路P和P上任意一条弧a，假设沿路P可增加的流量为，这一值称为f可增路P上流的增量（可增量）。6710.5网络68图10.36网络的课可增路可增量在求解网络的最大流问题时非常重要，求解网络最大流问题的几种常用算法都是基于可增量方法的。下面，我们介绍最大流问题求解的两种经典算法：标号算法和Dinic算法。10.5网络n标号算法就是由可增路的概念得到的。其基本原理为：对于一个网络N中的一个可行流f，如果能找到N中的一条f可增x-y路P，则可沿着P修改流的值，得到一个流量更大的可行流f。修改后流的流量为Valf=Valf+f(P)。如果反复找N中的可增路，沿着可增路将流量扩大，直到找不出可增路为止，就可以达到最大流。那么，怎样判断可行流f的可增路是否存在呢？或者说怎样找f的可增路？69标号算法10.5网络n解决这一问题需要使用Ford-Fulkerson标号法，标号过程如下。设网络N=(V,x,y,A,C)中当前可行流为f。从源点x开始，首先给x标上，即l(x)=（x称为已标未查顶点，其它顶点称为未标未查顶点）。任选一已标未查顶点u，检查其所有尚未标号的邻点：（1）对u的尚未标号的出邻点v（即A），若c(u,v)f(u,v)，则给v标号：，（v称为已标未查顶点）否则，不给v标号。（2）对u的尚未标号的入邻点v（即A），若f(u,v)0，则给v标号：，（v称为已标未查顶点）否则，不给v标号。70标号算法10.5网络n当检查完u的所有邻点之后，u称为已标已查顶点。n反复进行上述操作，最终结果有两种情况：（1）汇点y获得标号，此时已经得到了f的可增流（2）y点没有获得标号，并且已经没有已标未查顶点。此时当前的流f就是最大流。n图10.38（下页）演示了网络N从零值流开始，利用标号算法求最大流的过程。在每条弧上，括号外的数字表示当前流值，括号里的数字表示弧的容量。在每个顶点旁边有一组三元标号。在这个三元标号中，第一个元素表示该点的标号值是通过哪个点获得的，它用于反向追踪可增路；第二个元素的正或者负表示标号的前一个点是通过正向弧还是反向弧连接到当前点的，它用于标识在增流时应该在弧上增加流值还是减小流值；第三个元素为该顶点的标号数值，表示从源点x到该点通过当前找到的可增路可以增加的流值。71标号算法10.5网络72标号算法图10.38标号算法示例10.5网络n在图10.38（a）中，网络中的流是零值流。标号结束后，汇点y获得的标号为(v4,+,7)。标号的第一项为当前点的前一个点，根据这一点我们可以反向追踪得到可增路xv2v4y；标号的第三项表示可以增加的流值，也就是说可以增加7个单位的流量。据此，我们可以对网络进行增流，得到图10.38（b）。n在图10.8（b）中，标号结束后y获得的标号为(v3,+,5)。根据标号的第一项可以反向追踪得到可增路xv1v3y，这条可增路能增加的流值为5。增流后可以得到图10.38（c）。同样，我们可以从图10.38（c）再次增流，得到图10.38（d），此时，已经没有已标未查点了，而汇点y还没有获得标号，因此，当前网络流已经是最大流了。73标号算法10.5网络n在标号算法中，有可能出现每次只能增加一个单位流量的情况，这时，如果弧的容量为m，需要2m次增流才能达到最大流。可见，标号算法的计算量不完全依赖于问题的规模（顶点数和弧数），还依赖于弧的容量。n我们把计算量虽然是问题规模的多项式，但是还依赖于其它参量的算法称为伪多项式算法。Ford-Fulkerson标号算法就是一种伪多项式算法。标号算法不是一个多项式算法，其复杂度还依赖于弧的容量，因此，我们需要复杂度更低的算法。Dinic算法就是一种改进的算法。74标号算法10.5网络n定义10.22对于网络N=(V,x,y,A,C)和N上的一个可行流f，构造一个新的网络N(f)=(V,x,y,A(f),C)，其中A(f)及容量函数C定义如下：（1）若A并且f(u,v)c(u,v)，则A(f)，并且c(u,v)=c(u,v)-f(u,v)。（2）若A并且f(u,v)0，则A(f)，并且c(u,v)=f(u,v)。这样构造的网络N(f)称为网络N关于流f的增量网络。简单的说，对应于N中一条非饱和流，N(f)中有一条正向弧，其容量值为N中弧的容量与流量之差；对应于N中一条非零流弧，N(f)中有一条反向弧，其容量值为N中弧的流量。75Dinic算法10.5网络图10.39显示了一个网络和它的增量网络。在图10.39（a）中的网络N中，有一条饱和弧，因此，在对应的增量网络图10.39（b）中，只有一条与之方向相反的弧与之对应；在网络N中，有2条零流弧和，因此在增量网络中也有与它们对应的弧和；而对于网络N中的非零流非饱和弧，增量网络中将有正反两条弧与之对应。增量网络N(f)中每条弧的容量恰好是N中对应弧的流可增量。图10.3976Dinic算法10.5网络在增量网络N(f)中，我们把从x到y的有向路称为增量网络N(f)的x-y有向路。N(f)的x-y有向路是与网络N中的x-y路对应的，它是N的f可增路。因此，我们可以用在增量网络N(f)中找x-y有向路的方法来寻找网络N的f可增路。这一转换关系正是Dinic算法的依据。为了更快地得到最大流，我们需要对增量网络进行分层并且得到辅助网络。77Dinic算法10.5网络n定义10.23在网络N=(V,x,y,A,C)中，令：Vi=vV|N中x到v的最短有向路的长度为i。假设x到y的最短有向路的长度为n，则：（1）xV，yVn。（2）ViVj=，(ji)。Vi中的顶点称为网络N的第i层顶点。上述有向路的长度是指路上有向边的数目，而两点间最短有向路指两点间有向边最少的有向路。按照上述分层原则，我们可以对图10.40中的网络N进行分层。V0=x,V1=v1,v2,V2=y,v3,v478Dinic算法10.5网络n分层后的网络如图10.41所示。很容易看出，网络顶点分层后，弧有三种可能性：从第i层顶点指向第i+1层顶点；从第i层顶点指向第i层顶点；从第i层顶点指向第j层顶点(ji)。根据层的定义，不可能出现第i层顶点指向第i+k(k2)的情况。79Dinic算法图10.40待分层的网络N图10.41网络N的分层10.5网络对分层后的网络进行进一步的操作就可以得到辅助网络。辅助网络是在增量网络和网络分层的基础上得到的。其定义为：对于网络N=(V,x,y,A,C)，假设N(f)是N的关于流f的增量网络。对N(f)的顶点按照最短有向路进行分层后，删除层数不低于y的顶点（即比y层数高的顶点和与y同层的顶点），再删除从高层指向低层的弧和同层顶点之间的弧，得到的N(f)的子网络称为N的关于流f的辅助网络，记为AN(f)。此时所剩下的各条弧上的容量与N(f)相同。80辅助网络10.5网络n图10.42演示了从网络N到增量网络N(f)，再对增量网络N(f)进行分层并得到辅助网络的过程。81辅助网络图10.42网络N的增量网络、分层和辅助网络示例10.5网络有了前面介绍的增量网络、网络分层和辅助网络的概念之后，可以利用分层后的辅助网络求最大流，这一算法是Dinic提出的，我们称之为Dinic算法。Dinic算法可以从网络N=(V,x,y,A,C)的任意可行流f开始，执行如下过程：（1）构造增量网络N(f)（2）对N(f)分层并构造辅助网络AN(f)（3）求AN(f)中的一条x-y有向路P，它就是N中的一条f可增路；（4）在N中沿着P增流得到更大的流，并去掉因增流在AN(f)中所导致的饱和弧。如果此时AN(f)中仍然有x-y有向路，则再沿着新的x-y有向路在N中增流，直到N(f)剩余网络中没有x-y有向路为止；（5）反复执行（1）（4），直到新流f的增量网络N(f)不能分层到达y位置。完成上述步骤后，网络N不再有f可增路，因此得到的是最大流。82Dinic网络10.5网络我们同样以图10.38中的网络为例来演示Dinic算法，从而比较标号算法和Dinic算法的联系和区别。Dinic算法的演示过程如图10.43所示。83Dinic网络10.5网络可以看出，执行的过程与标号算法类似，但是在求可增流的过程中，Dinic算法借助增量网络和辅助网络更直观的得到可增流，为了演示标号算法和Dinic算法的联系，每次增流都只进行了一次，实际上，前两次增流可以一次完成。在简单的网络中，两者差别不大，但是在复杂的网络中，Dinic算法在复杂度上有一定的优势。下面我们来看Dinic算法的复杂度。在Dinic算法中，找路循环最多能进行e次，而在分层辅助网络中找一条x-y有向路的计算量为O(v)，因此，算法的总计算复杂度为O(v-1)(e+ev)=O(v2e)。其中，e为弧的数量、v为顶点的数量。在每次可增加的量较小时，Dinic算法的复杂度要明显低于标号算法。84Dinic网络10.5网络n定义10.24设a,b是开关网络GN上两个结点，而是a，b两点间的道路，其中若道路上各边的权的连乘积为，并令则称fab为开关网络GN关于结点a，b的开关函数。85开关网络10.5网络n定义10.25对于开关网络有矩阵其中则称矩阵为开关网络的传输矩阵。86开关网络10.5网络而对矩阵，其中则称矩阵为开关网络的连接矩阵。如果说连接矩阵A类似于邻接矩阵，而传输矩阵颇与路径矩阵相当，不难得到如下关系式这里是矩阵A的n-1次幂，不过乘是逻辑乘，和是逻辑和，并服从逻辑运算法则。87开关网络10.5网络n例10.17简单接触网络如图10.46所示。这里就是结点间“不超过两步”走到的道路的开关函数88图10.4610.5网络n例10.178910.5网络n定理10.18若是开关网络的两个结点，则对于中不含边的回路，必有间的道路，使，即回路为道路与的对称差。9010.5网络n例10.18设第一步：引进边，并从回路矩阵出发，通过一系列初等变换，目的要得出基本回路矩阵，步骤如下：从基本回路矩阵可知，图有m=9，余数变数=4，树的边数=5，n=6。第二步：从基本回路矩阵9110.5网络与基本割集矩阵的关系可得矩阵如下：对矩阵进行下列一系列初等变换，便能得到一个每列至多有两个元素1的矩阵。9210.5网络第三步：对上面所的矩阵增加最后一行，使得每列有两个元素1，于是得关联矩阵。根据基本道路矩阵与关联矩阵，可得开关网络图（去掉边）如图10.50所示。93图10.50PART PART 0101欧拉图主要内容PART PART 0 02 2哈密尔顿图PART PART 0 03 3二部图及匹配PART PART 0 04 4平面图PART PART 0 05 5网络PART PART 0 06 6图的示例分析10.6图的实例分析n1962年我国的管梅谷首先提出并研究了如下的问题：邮递员从邮局出发经过他投递的每一条街道，然后返回邮局，邮递员希望找出一条行走距离最短的路线。这个问题被外国人称为中国邮递员问题（ChinesePostmanProblem）。n我们把邮递员的投递区域看作一个连通的带权无向图G，其中G的顶点看作街道的交叉口和端点，街道看作边，权看作街道的长度，解决中国邮递员问题，就是在连通带权无向图中，寻找经过每边至少一次且权和最小的回路。n如果对应的图G是欧拉图，那么从对应于邮局的顶点出发的任何一条欧拉回路都是符合上述要求的邮递员的最优投递路线。95中国邮递员问题10.6图的实例分析n如果图G只有两个奇点x和y，则存在一条以x和y为端点的欧拉链，因此，由这条欧拉Euler链加x到y最短路即是所求的最优投递路线。n如果连通图G不是欧拉图也不是半欧拉Euler图，由于图G有偶数个奇点，对于任两个奇点x和y，在G中必有一条路连接它们。将这条路上的每条边改为二重边得到新图H1，则x和y就变为H1的偶点，在这条路上的其他顶点的度数均增加2，即奇偶数不变，于是H1的奇点个数比G的奇点个数少2。对H1重复上述过程得H2，再对H2重复上述过程得H3，经若干次后，可将G中所有顶点变成偶点，从而得到多重欧拉图（在中，若某两点u和v之间连接的边数多于2，则可去掉其中的偶数条多重边，最后剩下连接u与v的边仅有1或2条边，这样得到的图仍是欧拉图）。这个欧拉欧拉图的一条欧拉回路就相应于中国邮递员问题的一个可行解，且欧拉回路的长度等于G的所有边的长度加上由G到所添加的边的长度之和。但怎样才能使这样的欧拉回路的长度最短呢？如此得到的图中最短的欧拉Euler回路称为图G的最优环游。96中国邮递员问题10.6图的实例分析n定理10.19设P是加权连通图G中一条包含G的所有边至少一次的闭链，则P最优（即具有最小长度）的充要条件是：（1）P中没有二重以上的边。（2）在G的每个圈C中，重复边集E的长度之和不超过这个圈的长度的一半，即97中国邮递员问题10.6图的实例分析n根据上面的讨论及定理10.19，我们可以设计出求非欧拉带权非欧拉连通图G的最优环游的算法。此算法称为最优环游的奇偶点图上作业法。（1）把G中所有奇点配成对，将每对奇点之间的一条路上的每边改为二重边，得到一个新图G1，新图G1中没有奇点，即G1为多重欧拉图。（2）若G1中每一对顶点之间有多于2条边连接，则去掉其中的偶数条边，留下1条或2条边连接这两个顶点。直到每一对相邻顶点至多由2条边连接，得到图G2。（3）检查G2的每一个圈C，若某一个圈C上重复边的权和超过此圈权和的一半，则将C中的重复边改为不重复，而将单边改为重复边。重复这一过程，直到对G2的所有圈，其重复边的权和不超此圈权和的一半，得到图G3。（4）G3的Euler回路。98中国邮递员问题10.6图的实例分析n例10.19求图10.51所示图G的最优环游。解：图G中有6个奇点v2，v4，v5，v7，v9，v10，把它们配成三对：v2与v5，v4与v7，v9与v10。在图G中，取一条连接v2与v5的路v2v3v4v5，把边(v2，v3)，(v3，v4)，(v4，v5)作为重复边加入图中；再取v4与v7之间一条路v4v5v6v7，把边(v4，v5)，(v5，v6)，(v6，v7)作为重复边加入图中，在v9和v10之间加一条重复边(v9，v10)，如图10.52所示，这个图没有奇点，是一个欧拉图。图10.51-10.5399中国邮递员问题10.6图的实例分析n在图10.52中，顶点v4与v5之间有3条重边，去掉其中2条，得图10.53所示的图，该图仍是一个欧拉图。n如图10.53中，圈v2v3v4v11v2的总权为24，而圈上重复边的权和为14，大于该圈总权的一半，于是去掉边(v2,v3)和(v3,v4)上的重复边，而在边(v2,v11)和(v4,v11)上加入重复边，此时重复边的权和为10，小于该圈总权的一半。同理，圈v5v6v7v12v5的总权为25，而重复边权和为15，于是去掉边(v5,v6)和(v6,v7)上的重复边，在边(v5,v12)和(v7,v12)上加重复边，如图10.54所示。图10.54-10.56100中国邮递员问题10.6图的实例分析n图10.54中，圈v4v5v12v11v4的总权为15，而重复边的权和为8，从而调整为图10.55所示。n图10.55中，圈v1v2v11v12v7v8v9v10v1的总权为36，而重复边的总权为20，继续调整为图10.56所示。n检查图10.56，可知定理的和均满足，故为最优方案，接着给出出图10.56所示图的Euler回路，即为图G的最优环游由上例可知，对于比较大的图，要考察每个圈上重复边权和不大于该圈总权和的一半，确定每个圈的时间复杂性太大。1973年Edmonds和Johnson给出了一个更有效算法。101中国邮递员问题10.6图的实例分析n旅行售货员问题（TravelingSalesmanProblem）是在加权完全无向图中，求经过每个顶点恰好一次的（边）权和最小的哈密尔顿圈，又称之为最优哈密尔顿圈（OptimumHamiltoncycle）。如果我们将加权图中的结点看作城市，加权边看作距离，旅行售货员问题就成为找出一条最短路线，使得旅行售货员从某个城市出发，遍历每个城市一次，最后再回到出发的城市。102旅行售货员问题10.6图的实例分析n若选定出发点，对n个城市进行排列，因第二个顶点有n-1种选择，第三个顶点有n-2种选择，依次类推，共有(n-1)!条哈密尔顿圈。考虑到一个哈密尔顿圈可以用相反两个方向来遍历，因而只需检查个哈密尔顿圈，从中找出权和最小的一个。我们知道随着n的增加而增长得极快，比如有20个顶点，需考虑（约为）条不同的哈密尔顿圈。要检查每条哈密尔顿圈用最快的计算机也需大约1年的时间才能求出该图中长度最短的一条哈密尔顿圈。n因为旅行售货员问题同时具有理论和实践的重要性，所以已经投入了巨大的努力来设计解决它的有效算法。目前还没有找到一个有效算法！n当有许多需要访问的顶点时，解决旅行售货员问题的实际方法是使用近似算法（Approximationalgorithm）。103旅行售货员问题10.6图的实例分析n最邻近方法的步骤如下：（1）由任意选择的结点开始，指出与该结点最靠近（即权最小）的点，形成有一条边的初始路。（2）设x表示最新加到这条路上的结点，从不在路上的所有结点中选一个与x最靠近的结点，把连接x与这个结点的边加到这条路上。重复这一步，直到图中所有结点包含在路上。（3）将连接起点与最后加入的结点之间的边加到这条路上，就得到一个哈密尔顿圈，即得问题的近似解。104旅行售货员问题10.6图的实例分析n例10.20用“最邻近方法”找出图10.57所示加权完全图中具有充分小权的哈密尔顿圈。解：ADCBEFA的权和为55，BCADEFB的权和为53，CBADEFC的权和为42，DABCFED的权和为42，EADCBFE的权和为51，FCBADEF的权和为42。由上例可知，所选取的哈密尔顿圈不同，其近似解也不同，而“最邻近插入法”对上述方法可以进行改进，从而产生一个较好的结果。该方法在每次迭代中都构成一个闭的旅行路线。它是由多个阶段而形成的一个个旅程，逐步建立起来的，每一次比上一次多一个顶点，即是说，下一个旅程比上一个旅程多一个顶点，求解时，在已建立旅程以外的顶点中，寻找最邻近于旅程中某个顶点的顶点，然后将其插入该旅程中，并使增加的距离尽可能小，当全部顶点收入这个旅程后，就找到了我们所求的最短哈密尔顿圈的近似解。105旅行售货员问题10.6图的实例分析n最邻近插入法的步骤如下（图中有n个结点）：（1）取图中一点，作闭回路，置。（2），则输出闭回路，结束；否则转。（3）在已有闭回路之外的结点中，选取与闭回路最邻近的点u。（4）将u插入闭回路的不同位置可得k条不同的闭回路，从这k条闭回路选取一条长度最小的作为新的闭回路。，转（2）。106旅行售货员问题10.6图的实例分析n例10.21用“最邻近插入法”找出图10.57所示加权完全图中具有充分小权的哈密尔顿圈。解：开始于顶点A，组成闭旅程AA。最邻近A的顶点为D，建立闭旅程ADA。顶点B最邻近顶点A，建立闭旅程ADBA。由于C最邻近B，将C插入，分别得到三个闭旅程ACDBA、ADCBA、ADBCA，其长度依次为33、20、23，选取长度最短的旅程ADCBA。距旅程ADCBA中顶点最邻近顶点为F，将F插入，分别得到四个闭旅程AFDCBA、ADFCBA、ADCFBA、ADCBFA，其长度依次为52、34、37、45，选取长度最短的旅程ADFCBA。把顶点E插入旅程ADFCBA中，得到5个闭旅程AEDFCBA、ADEFCBA、ADFECBA、ADFCEBA、ADFCBEA、，其长度依次为54、42、60、61、49。显然，长度最短的旅程ADEFCBA即为我们要求的最短哈密尔顿圈的近似解。107旅行售货员问题10.6图的实例分析n排课是高校教学管理中一项重要而且复杂的基本工作，其实质就是为学校所设置的课程安排一组适当的教学时间与空间，从而使整个教学活动能够有计划有秩序地进行。n在排课问题中，其主要任务是将具有多种属性的各种资源，如教室、班级、教师、学生、课程、时间等，以一个周期的方式进行合理的匹配，使其不发生冲突。事实上，在排课问题中，每节课可抽象为教师和学生在时间和空间上的统一。因此，课表是协调教师和上课班级在上课时间、上课教室两个要素的总调度。课表算法本质要求主体即教师和上课班级合理使用时间和教室两种资源。n课表的编排包括教师和上课班级在上课时间（节次）和上课地点（教室）上的编排，这其中的组合可能性太多，为此可将模型简化为两个子模型：教师和上课班级在时间（节次）上的编排；教师和上课班级在地点（教室）上的编排，而这两个优化过程都可以转化为图论问题来解决。108排课问题10.6图的实例分析109排课问题n排课问题在时间上的安排实际上就是安排每一个教师在具体的时间段到某个具体的班级去上课。这个安排要求满足下面的条件：同一时间每位教师只能到一个班级去上课；一个班级在同一个时间也只能由一位教师来上课。用图论的知识可以来表示这个问题。例如：有n位教师，用x1,x2,xn来表示，有m个班，用y1,y2,ym来表示，教师xi要给班级yj上课就将xi与yj相连，如果一周内教师xi要给班级yj上2次课，则连2条线，以此类推。可以先作一个二部图G，使G=(X,Y,E)，其中X=x1,x2,xn代表n个教师，Y=y1,y2,ym代表m