离散数学第十章 几种图的介绍.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第,十,章,几种图的介绍,离散数学,陈志奎主编,人民邮电出版社,前言,自从,1736,年欧拉（,L.Euler,）利用图论的思想解决了哥尼斯堡（,Konigsberg,）七桥问题以来，图论经历了漫长的发展道路。在很长一段时期内，图论被当成是数学家的智力游戏，解决一些著名的难题，曾经吸引了众多的学者。图论中许多的概论和定理的建立都与解决这些问题有关。,1859,年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体，它的,20,个顶点标出世界著名的,20,个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即绕行世界。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个问题后来就叫做哈密顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的关注和研究。,前言,在图论的历史中，还有一个最著名的问题,四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。四色猜想有一段有趣的历史。每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接。所以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。,前言,在电子计算机问世后，图论的应用范围更加广泛，在解决运筹学、信息论、控制论、网络理论、博奕论、化学、社会科学、经济学、建筑学、心理学、语言学和计算机科学中的问题时，扮演着越来越重要的角色，受到工程界和数学界的特别重视，成为解决许多实际问题的基本工具之一。,本章将结合图论基础知识，进一步介绍一些常用的基本图类，如欧拉图、哈密尔顿图、二部图、平面图、网络等，除研究每种图类的本质特征之外，都力求结合一些实际问题来阐明图论的广泛可应用性，介绍一些最基本的图论算法，使读者对图的理论和应用这两个方面都有一定的了解。,PART,01,欧拉图,主要,内容,PART,0,2,哈密尔顿图,PART,0,3,二部图及匹配,PART,0,4,平面图,PART,0,5,网络,PART,0,6,图的示例分析,10.1,欧拉图,定义,10.1,图,G,中包含其所有边的简单开路径称为图,G,的欧拉路径，图,G,中包含其所有边的简单闭路径称为,G,的欧拉闭路,。,图,10.1,哥尼斯堡七桥,图,10.2,哥尼斯堡七桥问题的图,6,10.1,欧拉图,例,10.1,图,10.3,中（,a,）是欧拉闭路，（,c,）是欧拉路径，（,b,）既不是欧拉路径也不是欧拉闭路。,图,10.3,7,10.1,欧拉图,定义,10.2,每个结点都是偶结点的连通无向图称为,欧拉图,。每个结点的出度和入度相等的连通有向图称为,欧拉有向图,。,例,10.2,图,10.4,中（,b,）是欧拉有向图。,图,10.4,8,10.1,欧拉图,定理,10.1,设,G,是连通无向图，,G,是欧拉图，当且仅当,G,有欧拉闭路。,9,10.1,欧拉图,定理,10.2,设,G=,为连通无向图，且 ，,，则,G,有一条从 至 的欧拉路径当且仅当,G,恰有两个奇结点 和 。,10,10.1,欧拉图,定理,10.3,设,G,为弱连通的有向图。,G,是欧拉有向图，当且仅当,G,有欧拉闭路。,定理,10.4,设,G,为弱连通有向图。和 为,G,的两个不同结点。,G,有一条从 至 的欧拉路径，当且仅当,=+1,，,=-1,，且对,G,的其他结点,v,有,=,11,10.1,欧拉图,定理,10.5,如果 和 是可运算的欧拉图，则 是欧拉图。,由定理,10.5,可得图,10.5,图,10.5,12,PART,01,欧拉图,主要,内容,PART,0,2,哈密尔顿图,PART,0,3,二部图及匹配,PART,0,4,平面图,PART,0,5,网络,PART,0,6,图的示例分析,10.2,哈密尔顿图,爱尔兰数学家哈密尔顿（,William Hamilton,）爵士,1859,年提出了一个,“,周游世界,”,的游戏。这个游戏把一个正十二面体的二十个顶点看成地球上的二十个城市。棱线看成是连接城市的航路（航空、航海线或陆路交通线），要求游戏者沿棱线走，寻找一条经过所有结点（即城市）一次且仅一次的回路，如图,10.6,（,a,）所示。也就是在图,10.6,（,b,）中找一条包含所有结点的圈。图（,b,）中的粗线所构成的圈就是这个问题的回答。,与欧拉图不同，哈密尔顿图是遍历图中的每个结点，一条哈密尔顿回路不会在两个结点间走两次以上，因此没有必要在有向图中讨论。,14,图,10.6,10.2,哈密尔顿图,爱尔兰数学家哈密尔顿（,William Hamilton,）爵士,1859,年提出了一个,“,周游世界,”,的游戏。这个游戏把一个正十二面体的二十个顶点看成地球上的二十个城市。棱线看成是连接城市的航路（航空、航海线或陆路交通线），要求游戏者沿棱线走，寻找一条经过所有结点（即城市）一次且仅一次的回路，如图,10.6,（,a,）所示。也就是在图,10.6,（,b,）中找一条包含所有结点的圈。图（,b,）中的粗线所构成的圈就是这个问题的回答。,与欧拉图不同，哈密尔顿图是遍历图中的每个结点，一条哈密尔顿回路不会在两个结点间走两次以上，因此没有必要在有向图中讨论。,15,图,10.6,10.2,哈密尔顿图,定义,10.3,给定无向图,G,，图,G,中包含其所有顶点的简单开路径称为图,G,的,哈密尔顿路径,，图,G,中包含其所有顶点的简单闭路径称为,G,的,哈密尔顿回路,。具有哈密顿回路的图称为,哈密尔顿图,。,由定义可知哈密尔顿圈与哈密尔顿路通过图,G,中的每个结点一次且仅一次，例如图,10.6,（,b,）就是哈密尔顿图（哈密尔顿圈用实线标出）。,16,10.2,哈密尔顿图,例,10.3,图,10.7,中，图（,a,）、（,b,）中有哈密尔顿圈，图（,c,）中有哈密尔顿路，（,d,）中既没有哈密尔顿圈也没有哈密尔顿路。,图,10.7,哈密尔顿图和欧拉图相比，虽然考虑的都是遍历问题，但是侧重点不同。欧拉图遍历的是边，而哈密尔顿图遍历的是结点。另外两者的判定困难程度也不一样，前面我们已经给出了判定欧拉图的充分必要条件，但对于哈密尔顿图的判定，至今还没有找出判定的充要条件，只能给出若干必要条件或充分条件。,17,10.2,哈密尔顿图,定理,10.6,若,G,是哈密尔顿图，则对于结点集 的任一非空真子集,有 。其中 表示在,G,中删去,S,中的结点后所构成的图，表示 的连通分支数。,18,哈密尔顿图的必要条件可用来判定某些图不是哈密尔顿图，只要能够找到不满足定理条件的结点集,V,的非空子集,S,。,10.2,哈密尔顿图,例,10.4,图,10.8,（,a,）不是哈密尔顿图。,图,10.8,（,a,）中共有,9,个结点，如果取结点集,S=3,个白点,，即 。而这时 （如图（,b,）。这说明图,10.8,（,a,）不是哈密尔顿图。但要注意若一个图满足定理,10.6,的条件也不能保证这个图一定是哈密尔顿图，如图,10.8,（,c,）。,19,图,10.8,10.2,哈密尔顿图,定理,10.7,设图,G,是具有,n,（,3,）个结点的无向简单图，如果,G,中每一对结点度数之和大于等于,n-1,，则在,G,中存在一条哈密尔顿路。,定理,10.8,若,G,是具有,n,（,3,）个结点的无向简单图，对于,G,中每一对不相邻的结点 均有 ，则,G,是一个哈密尔顿图。,定理,10.7,和,10.8,都是充分条件，即满足这些条件的图一定是哈密尔顿图。但不是所有的哈密尔顿图都满足这些条件。例如图,10.9,是哈密尔顿图,但它不满足上述定理的条件。,20,图,10.9,10.2,哈密尔顿图,例,10.5,某地有,5,个风景点。若每个景点均有两条道路与其它景点相通，问是否可经过每个景点恰好一次而游完这,5,处？,解：将景点作为结点，道路作为边，则得到一个有,5,个结点的无向图。,由题意，对每个结点 ，有,则对任两点 ，均有,可知此图一定有一条哈密尔顿路，本题有解。,21,10.2,哈密尔顿图,例,10.6,今有 和,7,人，已知下列事实。,a,讲英语；,b,讲英语和汉语；,c,讲英语、意大利语和俄语；,d,讲日语和汉语；,e,讲德国和意大利语；,f,讲法语、日语和俄语；,g,讲法语和德语。,试问这,7,个人应如何排座位，才能使每个人都能和他身边的人交谈？,22,解：设无向图 ，其中,图,G,是连通图，如图,10.10,（,a,）所示。将这,7,个人排座围圆桌而坐，使得每个人能与两边的人交谈，即在图,10.10,（,a,）中找哈密尔顿回路。经观察该回路是。即按照图,10.10,（,b,）安排座位即可。,PART,01,欧拉图,主要,内容,PART,0,2,哈密尔顿图,PART,0,3,二部图及匹配,PART,0,4,平面图,PART,0,5,网络,PART,0,6,图的示例分析,10.3,二部图及匹配,定义,10.4,设无向图,G=,。如果存在,V,的划分,，使得 中的任何两个结点都不相邻（,i=1,2,），则称,G,为,二部图,，和 称为,G,的,互补结点子集,。,显然，二部图没有自圈。与二部图的一条边关联的两个结点一定分属于两个互补结点子集。一般来说，二部图的互补结点子集的划分不是唯一的。如图,10.11,的二部图，和 是它的互补结点子集，,和,也是它的互补结点子集。,图,10.11,二部图,24,10.3,二部图及匹配,一个无向图如果能画成上面的样式，很容易判定它是二部图。有些图虽然表面上不是上面的样式，但经过改画就能成为上面的样式，仍可判定它是一个二部图，如图,10.12,中（,a,）可改画成图（,b,），图（,c,）可改画成图（,d,）。可以看出，它们仍是二部图。,图,10.12,25,10.3,二部图及匹配,定理,10.9,设,G,是阶大于,1,的无向图。,G,是二部图，当且仅当,G,的所有回路长度均为偶数。,定义,10.5,设 和 是简单二部图,G,的互补结点子集，如果 中的每个结点与 中的每个结点相邻，则称,G,为,完全二部图,。,我们把互补结点子集分别包含,m,和,n,个结点的完全二部图记为 。图,10.14,画出了 的两个图示。很重要，我们在讨论图的平面性时还要用到它。,26,10.3,二部图及匹配,二部图的主要应用是匹配，,“,匹配,”,是图论中的一个重要内容，它在所谓,“,人员分配问题,”,和,“,最优分配问题,”,等运筹学中的问题上有重要的应用。,首先看实际中常碰见的问题：给,n,个工作人员安排,m,项任务，,n,个人用 表示。并不是每个工作人员均能胜任所有的任务，一个人只能胜任其中 个任务，那么如何安排才能做到最大限度地使每项任务都有人做，并使尽可能多的人有工作做？,例如，现有,5,个人，,5,项工作。已知 能胜任,和 ，能胜任 和 ，能胜任 和 ，能胜任 和 ，能胜任 、和 。如何安排才能使每个人都有工作做，且每项工作都有人做？,27,10.3,二部图及匹配,显然，我们只需构造这样的数学模型：以 和 （,i,，,j=1,，,2,，,3,，,4,，,5,）为顶点，在 与其胜任的工作 之间连边，得二部图,G,，如图,10.15,所示，然后在,G,中找一个边的子集，使得每个顶点只与一条边关联（图中粗线），问题便得以解决了。这就是所谓匹配问题，下面给出匹配的基本概念和术语。,图,10.15,匹配问题示意图,28,10.3,二部图及匹配,定义,10.6,设无向图,G=,，,（,1,）如果 不包含自圈，并且 中的任何两条边都不邻接，则称 为,G,中的,匹配,。,（,2,）如果 是,G,中的匹配，并且对于,G,中的一切匹配 ，只要 必有,，则称 为,G,中的,极大匹配,。,（,3,）,G,中的边数最多的匹配称为,G,中的,最大匹配,。,（,4,）,G,中的最大匹配包含的边数称为,G,的,匹配数,。,显然，最大匹配一定是极大匹配，而极大匹配不一定是最大匹配。在一个无向图中，可以有多个极大匹配和最大匹配。,29,10.3,二部图及匹配,例,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.16,30,10.3,二部图及匹配,定义,10.7,设 和 是二部图,G,的互补结点子集。如果,G,的匹配数等于 ，则称,G,中的最大匹配为 到 的完美匹配。,显然，只有,V,2,V,1,时可能存在从,V,1,到,V,2,的完美匹配。但这个条件并不是充分条件。如图,10.16,给出的二部图中，,V,1,a,1,a,2,a,3,a,4,V,2,p,1,p,2,p,3,p,4,p,5,p,6,V,2,V,1,，但并不存在,V,1,到,V,2,的完美匹配。下面的定理给出了存在完美匹配的充分必要条件。,图,10.16,无向图中的匹配,31,10.3,二部图及匹配,定理,10.10,设,和,是二部图,G,的互补结点子集。存在,到,的,完美匹配,，当且仅当对于任意,，其中,当二部图的结点数目比较大时，定理,10.10,用起来不太方便，下面给出存在完美匹配的一个充分条件，判断二部图是否存在完美匹配时，可以先用这个充分条件，如果得不出结论，再用定理,10.10,。,32,10.3,二部图及匹配,定理,10.11,设,V,1,和,V,2,是二部图,G,的互补结点子集，,t,是正整数。对于,V,1,中的每个结点，在,V,2,中至少有,t,个结点与其邻接。对于,V,2,中的每个结点，在,V,1,中至多有,t,个结点与其邻接。则存在,V,1,到,V,2,的完美匹配。,33,PART,01,欧拉图,主要,内容,PART,0,2,哈密尔顿图,PART,0,3,二部图及匹配,PART,0,4,平面图,PART,0,5,网络,PART,0,6,图的示例分析,10.4,平面图,例,10.8,一个工厂有,3,个车间和,3,个仓库。为了工作需要，车间与仓库之间将设专用的车道。为避免发生车祸，应尽量减少车道的交叉点，最好是没有交叉点，这是否可能？,如图,10.17,（,a,）所示，,A,，,B,，,C,是,3,个车间，,M,，,N,，,P,是,3,座仓库。经过努力表明，要想建造不相交的道路是不可能的，但可以使交叉点最少（如图,10.17,（,b,）所示）。此类实际问题涉及到平面图的研究。近年来，由于大规模集成电路的发展，也促进了平面图的研究。本节介绍平面图的一些基本概念和常用结论。,图,10.17,35,10.4,平面图,定义,10.8,在一个平面上，如果能够画出无向图,G,的图解，其中没有任何边的交叉，则称图,G,是个平面图；否则，称,G,是非平面图。,直观上说，所谓平面图就是可以画在平面上，使边除端点外彼此不相交的图。应当注意，有些图从表面上看，它的某些边是相交的，但是不能就此肯定它不是平面图。,36,10.4,平面图,例,10.9,对于图,10.18,（,a,）（,b,）中的无向图来说，试把该图解加以重画之后，它将不包含任何边的交叉，如图,10.17,（,e,）（,f,）所示。因此，由图,10.17,（,a,）（,b,）给出的图是平面图，而（,c,）（,d,）不是。,图,10.18,37,10.4,平面图,设,G,=,V,，,E,，,是能够画于平面上的图解中的无向图，并且设,C,=,v,1,v,2,v,3,v,4,v,1,是图,G,中的任何基本循环。此外，设,x,v,1,v,3,和,x,v,2,v,4,是图,G,中的任意两条不交叉的基本路径。在图,10.19,中给出了两种可能的结构。显然，,x,和,x,或都在基本循环,C,的内部，或者都在基本循环,C,的外部，当且仅当,G,是个非平面图。因为这时基本路径,x,和,x,是相互交叉的。用视察法证明给定图的非平面性时，上述的简单性质甚为有用。,图,10.19,38,10.4,平面图,例,10.10,设有一个电路，它含有两个结点子集,V,1,和,V,2,，且有,|,V,1,|=|,V,2,|=3,。用导线把一个集合中的每一个结点，都与另外一个集合中的每一个结点连通，如图,10.20,所示。试问，是否有可能这样来接线，使得导线相互不交叉。对于印刷电路，避免交叉具有实际意义。,解：,这个问题等价于判定图,10.20,中的图是否是个平面图。可以看出，给定图中有一个基本循环,C,=,v,1,v,6,v,3,v,5,v,2,v,4,v,1,，如图,10.21,所示。,39,图,10.20,图,10.21,10.4,平面图,试考察三条边,v,1,，,v,5,，,v,2,，,v,6,，,v,3,，,v,4,，上述每条边或是处于循环,C,的内部，或是处于,C,的外部。显然，三条边中至少有两条边同时处于,C,的同一侧，因此避免不了交叉，如图,10.22,所示。故给定的图是非平面图。,图,10.22,40,10.4,平面图,下面就来阐明库拉托夫斯基（,Kuratowski,，波兰数学家）定理。试考察图,10.23,中的两个图。在例,10.10,中已经证明了图,10.20,中的图是个非平面图。把图,10.20,加以改画以后，就能够得到图,10.23,（,a,）。由此可见，图,10.20,同构于图,10.23,（,a,），因此图,10.23,（,a,）也是个非平面图。另外，采用该例中所使用的方法，也能证明图,10.23,（,b,）也是个非平面图。这两个非平面图都称为库拉托夫斯基图。,图,10.23,41,10.4,平面图,在图,10.24,中，给出了两个图解。如图,10.24,（,a,）所示，试往图中的一条边上，插上一个新的次数为,2,的结点，把一条边分解成两条边，则不会改变给定图的平面性。另外，如图,10.24,（,b,）所示，把联系于一个次数为,2,的结点的两条边，合并成一条边，也不会改变给定图的平面性。,图,10.24,42,10.4,平面图,定义,10.9,设,G,1,和,G,2,是两个无向图。如果,G,1,和,G,2,是同构的，或者是通过反复插入和（或）删除次数为,2,的结点，能够把,G,1,和,G,2,转化成同构的图，则称,G,1,和,G,2,在次数为,2,的结点内是,同构的,。,例,10.11,图,10.25,中的,4,个图，在次数为,2,的结点内是同构的。,图,10.25,43,10.4,平面图,定理,10.12,设,G,是一个无向图。图,G,中不存在任何与图,10.23,中的两个图同构的子图，当且仅当图,G,是个平面图。称为,库拉托夫斯基定理,。,例,10.12,根据库拉托夫斯基定理证明图,10.26,中的（彼得森图）是非平面图。,图,10.25,44,10.4,平面图,定义,10.10,多边形的图的归纳法定义如下。,一个多边形是一个多边形的图。设,G=,是一个多边形的图，再设,P=v,i,u,1,u,2,u,l-1,v,j,是长度为,l,1,的任何基本路径，它不与图,G,中任一路径交叉，且有,v,i,，,v,j,V,，但是对于,n=1,2,，,l-1,来说，,u,n,V,。于是，由图,G,和,P,所构成的图,G,=,也是一个多边形的图，其中,V,=V,u,1,，,u,2,，,，,u,l-1,E,=E,v,i,，,u,1,，,u,1,，,u,2,，,，,u,l-1,，,v,j,多边形的图是个平面图（或多重边图，因为允许长度为,2,的循环存在），它能够把平面划分成数个区域，每一个区域都是由一个多边形定界。,45,10.4,平面图,例,10.13,图,10.27,中的图是一个多边形的图。,图,10.27,多边形的图,46,10.4,平面图,定义,10.11,由多边形的图定界的每一个区域，都称为图,G,的面。例如，图,10.27,中的区域,F,1,，,F,2,，,F,3,等等，都是该多边形图的面。,定义,10.12,包含有多边形的图,G,的所有面的边界的多边形，称为,G,的,极大基本循环,。,例如，图,10.27,中的循环,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,1,，就是该多边形的图的极大基本循环。,应该说明，给定图,G,的极大基本循环外侧的无限区域，是另外一个面，一般称为,G,的无限面。事实上，如果把图,G,的图解画在球面上，则,G,的无限面与其它的有限面并没有什么区别。,47,10.4,平面图,定义,10.13,如果图,G,的两个面共有一条边，则称这样的两个面是,邻接的面,。,定理,10.13,（,欧拉公式,）设,G,=,是个具有,k,个面（包括无限面在内）的,(,n,m,),多边形的图。则,n,m,+,k,=2,。,48,10.4,平面图,例,10.14,在图,10.28,中，给出了一个多边形的图,(,实线画出的,),和它的对偶,(,虚线画出的,),，就说明了上述方法。,由上述的构成方法不难看出，每一个多边形的图,G,，其对偶图也必定是一个多边形的图，而且,G,和,G*,是互为对偶的。,49,图,10.28,对偶图,10.4,平面图,定义,10.14,如果多边形的图,G,的对偶,G*,同构于,G,，则称,G,是,自对偶图,。,例,10.15,在图,10.29,中，给出了一个自对偶图。,50,图,10.29,自偶图,10.4,平面图,定理,10.14,若平面图 是自对偶图，且有,n,个结点，,m,条边，则,定义,10.15,平面图 的,正常着色,(,简称,着色,，是指对 的每个结点指派一种颜色，使得相邻结点都有不同的颜色,),。若可用,n,种颜色对图,G,着色，则称,G,是,n,可着色的,。对图,G,着色时，需要的最少颜色数称为,G,的着色数，记为,51,10.4,平面图,定理,10.15,（,四色定理,）任何简单平面图都是,4,可着色的。,定理,10.16,（,五色定理,）任何简单平面图 ，均有,52,PART,01,欧拉图,主要,内容,PART,0,2,哈密尔顿图,PART,0,3,二部图及匹配,PART,0,4,平面图,PART,0,5,网络,PART,0,6,图的示例分析,10.5,网络,定义,10.16,一个网络,N=(V,A),是指一个连通无环且满足下列条件的有向图。,（,1,）有一个顶点子集,X,，其每个顶点的入度都是,0,。,（,2,）有一个与,X,不相交的顶点子集,Y,，其每个顶点的出度都为,0,。,（,3,）每条弧都有一个非负的权值，称为弧的容量。,上述网络,N,可以记作,N=(V,X,Y,A,C),，其中，,X,称为网络的源点集，,Y,称为网络的汇点集，,V,和,A,分别为顶点集和弧集，网络中的除源点和汇点之外的顶点称为中转点。源点和汇点在实际网络中对应于网络的入口和出口，或者说计算机网络的源结点和目的结点。,54,10.5,网络,C,为网络的容量函数，容量函数是定义在弧集,A,上的非负函数。在实际网络中，它对应于相应路线上的通行能力，如公路的宽度、计算机网络的带宽等。,例如，在图,10.33,所示的网络中，,x,1,x,2,是源点集，,y,1,y,2,是汇点集。其他结点是中转结点，弧上的数字表示弧的容量。,图,10.33,网络示例,55,10.5,网络,如果一个网络中的源点集和汇点集都只包含一个顶点，我们称该网络为单源单汇网络。事实上，对于任意网络,N=,(,V,X,Y,A,C,),，在经过一定的处理后，都可以转变为一个单源单汇网络。处理的方法为：,（,1,）给网络,N,添加两个新的顶点,s,和,t,。,（,2,）对任意,x,X,，从,s,向,x,添加一条弧，其容量为,（或,）。,（,3,）对任意,y,Y,，从,y,向,t,添加一条弧，其容量为,（或,）。,其中，,N,+,(,x,),表示顶点,x,的出邻点集合,u,|(,x,u,),A,，,N,-,(,y,),表示顶点,y,的入邻点集合,u,|(,u,y,),A,。新添加的顶点,s,和,t,分别称为人工源和人工汇。,56,10.5,网络,简单地说，只需要在原有非单源单汇网络中添加一个新的源点和一个新的汇点，并且添加从新的源点指向原有源点的弧，再添加从原有汇点指向新的汇点的弧，就能得到一个单源单汇网络。,图,10.34,单源单汇网络,对图,10.33,所示的网络添加人工源和人工汇后，将变为图,10.34,所示的单源单汇网络。单源单汇网络是一种特殊的网络，它在各种网络问题的求解方面比非单源单汇网络更为简单。由于任意网络都可以转化为单源单汇网络，后续章节中对网络流的讨论都可以只考虑单源单汇网络。,57,10.5,网络,在一些实际应用中，需要考虑弧和顶点都有容量限制的网络。例如，在某些网络中，需要考虑结点的缓存大小，此时结点的转发能力会受到限制。结点能力的限制并不能直接在图上体现出来，对于这样的情况，可以做一个转换，其方法为：将中转能力受限的结点分裂为两个结点，并且在这两个结点之间加入一条弧，这样就可以利用这条新加入的弧来表示结点的转发能力受限。,经过转化为单源单汇网络并将结点能力的受限转化为弧的受限后，实际网络问题可以转化为图论中的网络问题。,58,10.5,网络,定义,10.17,可行流为：网络,N=,(,V,X,Y,A,C,),中的一个可行流是指定义在,A,上的一个整值函数,f,，使得：,（,1,）对任意,a,A,，,0,f,(,a,),c,(,a,),（容量约束）；,（,2,）对任意,v,V,-(,X,Y,),，,f,-,(,v,)=,f,+,(,v,),，（流量守恒）。,其中，,f,-,(,v,),表示点,v,处入弧上的流量之和，即流入,v,的流量之和，,f,+,(,v,),表示点,v,处出弧上的流量之和，即从,v,流出的流量之和。,59,网络流,10.5,网络,也就是说，可行流满足两个条件：一是容量约束，即可行流在某一弧上的流量小于该弧的容量；二是流量守恒，即流入某一中转点的流量等于流出该点的流量。,需要强调的是，,可行流总是存在的,，如果,f(a)=0,，这个流称为零值流。,对于网络,N,中任意可行流,f,和任意顶点子集,S,，从,S,中流出的流量记为,f,+,(S),，它表示从,S,中顶点指向,S,外顶点的弧上的流量之和；流入,S,的流量记为,f,-,(S),，表示从,S,外顶点指向,S,中顶点的弧上流量之和。,60,网络流,10.5,网络,定义,10.18,设,f,是网络,N=(V,X,Y,A,C),中的一个可行流，则必有,f+(X)=f-(Y),。,f+(X),（或,f-(Y),）称为流,f,的,流量,，记为,Val f,。,流是网络中的重要概念，在实际网络问题中，经常需要求解与流相关的问题，例如网络的最大流等。,所谓最大流，是指网络,N,中流量最大的可行流。网络的最大流对于实际应用具有重要意义，例如，公路网络中获得最大的运输量、计算机网络中获得最大的转发增益等等。为了得到网络的最大流，,L.R.Ford,和,D.R.Fulkerson,在,1956,年提出了著名的最大流最小割定理，巧妙地将流与割对应起来，将最大流问题转化为最小割问题。,61,流量,10.5,网络,定义,10.19,设,N=(V,x,y,A,C),是一个单源单汇网络。假设网络中的某些顶点组成集合,S,，,SV,，,=V-S,。我们用,(S,),表示尾在,S,中而头在 中的所有弧的集合（即从,S,中的顶点指向,S,之外顶点的所有弧的集合）。如果,，而,，则称弧集,(S,),为网络,N,的一个,割,。,一个割,(S,),的容量是指,(S,),中各条弧的容量之和，记为,Cap(S,),。,62,10.5,网络,定义,10.19,设,N=(V,x,y,A,C),是一个单源单汇网络。假设网络中的某些顶点组成集合,S,，,SV,，,=V-S,。我们用,(S,),表示尾在,S,中而头在 中的所有弧的集合（即从,S,中的顶点指向,S,之外顶点的所有弧的集合）。如果,，而,，则称弧集,(S,),为网络,N,的一个,割,。,一个割,(S,),的容量是指,(S,),中各条弧的容量之和，记为,Cap(S,),。,63,10.5,网络,例如，在图,10.24,中所示的单源单汇网络,N,中，令,S=s,x,1,x,2,v,2,，则割,(S,)=x,1,v,1,x,2,v,1,v,2,y,1,v,2,y,2,，割的容量,Cap(S,)=11,。,对网络,N,中的任意流,f,和任意割,(S,),，流,f,的流量等于流出,S,的流量与流入,S,的流量之差，即,Val,f,=,f,+,(,S,)-,f,-,(,S,),。,网络,N,可能存在多个割，各个割的容量并不一定相等，其中容量最小的一个割称为网络,N,的,最小割,。,即：如果网络,N,不存在割 使得,，则割,K,称为网络,N,的最小割。,64,10.5,网络,定理,10.17,最大流最小割定理的基本内容为：任一网络,N=(V,X,Y,A,C),中，最大流的流量等于最小割的,容量,。,实际上，割就是一个弧的集合，如果去掉这些弧，就可以把网络,“,分割,”,成分别包含了源点和汇点的两部分。由于从源点到汇点必须要经过这些弧，因此，如果能求出最小的割集，就能得到最大流。,最大流最小割定理对于求解最大流具有非常重要的指导意义，关于怎样求解网络的最大流，我们将在下一节介绍。,65,10.5,网络,定义,10.20,设,P=,uv,1,u,k,v,是网络,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,=,xv,1,v,3,v,4,y,上，所有弧都是正向弧；而在,x-y,路,Q,=,xv,2,v,4,v,3,y,上，弧,和,是正向弧，而,和,是反向弧。可以看出，对于同一条弧,，在路,P,中为正向弧，而在路,Q,中为反向弧。可见，一条弧是正向弧还是反向弧与路的选择有关。,10.5,网络,定义,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,上,流的增量,（可增量）。,67,10.5,网络,68,图,10.36,网络的课可增路,可增量在求解网络的最大流问题时非常重要，求解网络最大流问题的几种常用算法都是基于可增量方法的。,下面，我们介绍最大流问题求解的两种经典算法：标号算法和,Dinic,算法。,10.5,网络,标号算法就是由可增路的概念得到的。其基本原理为：,对于一个网络,N,中的一个可行流,f,，如果能找到,N,中的一条,f,可增,x-y,路,P,，则可沿着,P,修改流的值，得到一个流量更大的可行流,f,。修改后流的流量为,Val f,=Val f+f(P),。,如果反复找,N,中的可增路，沿着可增路将流量扩大，直到找不出可增路为止，就可以达到最大流。,那么，怎样判断可行流,f,的可增路是否存在呢？或者说怎样找,f,的可增路？,69,标号算法,10.5,网络,解决这一问题需要使用,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,网络,当检查完,u,的所有邻点之后，,u,称为已标已查顶点。,反复进行上述操作，最终结果有两种情况：,（,1,）汇点,y,获得标号，此时已经得到了,f,的可增流,（,2,）,y,点没有获得标号，并且已经没有已标未查顶点。此时当前的流,f,就是最大流。,图,10.38,（下页）演示了网络,N,从零值流开始，利用标号算法求最大流的过程。在每条弧上，括号外的数字表示当前流值，括号里的数字表示弧的容量。在每个顶点旁边有一组三元标号。在这个三元标号中，第一个元素表示该点的标号值是通过哪个点获得的，它用于反向追踪可增路；第二个元素的正或者负表示标号的前一个点是通过正向弧还是反向弧连接到当前点的，它用于标识在增流时应该在弧上增加流值还是减小流值；第三个元素为该顶点的标号数值，表示从源点,x,到该点通过当前找到的可增路可以增加的流值。,71,标号算法,10.5,网络,72,标号算法,图,10.38,标号算法示例,10.5,网络,在图,10.38,（,a,）中，网络中的流是零值流。标号结束后，汇点,y,获得的标号为,(,v,4,+,7),。标号的第一项为当前点的前一个点，根据这一点我们可以反向追踪得到可增路,xv,2,v,4,y,；标号的第三项表示可以增加的流值，也就是说可以增加,7,个单位的流量。据此，我们可以对网络进行增流，得到图,10.38,（,b,）。,在图,10.8,（,b,）中，标号结束后,y,获得的标号为,(,v,3,+,5),。根据标号的第一项可以反向追踪得到可增路,xv,1,v,3,y,，这条可增路能增加的流值为,5,。增流后可以得到图,10.38,（,c,）。同样，我们可以从图,10.38,（,c,）再次增流，得到图,10.38,（,d,），此时，已经没有已标未查点了，而汇点,y,还没有获得标号，因此，当前网络流已经是最大流了。,73,标号算法,10.5,网络,在标号算法中，有可能出现每次只能增加一个单位流量的情况，这时，如果弧的容量为,m,，需要,2,m,次增流才能达到最大流。可见，标号算法的计算量不完全依赖于问题的规模（顶点数和弧数），还依赖于弧的容量。,我们把计算量虽然是问题规模的多项式，但是还依赖于其它参量的算法称为伪多项式算法。,Ford-Fulkerson,标号算法就是一种伪多项式算法。标号算法不是一个多项式算法，其复杂度还依赖于弧的容量，因此，我们需要复杂度更低的算法。,Dinic,算法就是一种改进的算法。,74,标号算法,10.5,网络,定义,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)0,，则,A(f,),，并且,c,(u,v)=f(u,v),。,这样构造的网络,N(f,),称为网络,N,关于流,f,的增量网络,。,简单的说，对应于,N,中一条非饱和流，,N(f,),中有一条正向弧，其容量值为,N,中弧的容量与流量之差；对应于,N,中一条非零流弧，,N(f,),中有一条反向弧，其容量值为,N,中弧的流量。,75,Dinic,算法,10.5,网络,图,10.