第11章 特殊图.ppt

1、离 散 数 学,电子科技大学,计算机科学与工程学院 示 范 性 软 件 学 院,2020年8月6日星期四,2020/8/6,第11章 特殊图,2020/8/6,11.0 内容提要,几个特殊图的概念：欧拉图、哈密顿图、偶图、平面图； 欧拉图、哈密顿图、偶图、平面图的判定； 偶图的匹配、图的着色； 欧拉图、哈密顿图、偶图、平面图的应用,2020/8/6,10.1 本章学习要求,2020/8/6,11.2 欧拉图,11.2.1 欧拉图的引入与定义,2020/8/6,定义11.2.1,设G是无孤立结点的图，若存在一条通路(回路)，经过图中每边一次且仅一次，则称此通路(回路)为该图的一条欧拉通路(回路)

2、(Eulerian Entry/Circuit)。 具有欧拉回路的图称为欧拉图(Eulerian Graph)。 规定：平凡图为欧拉图。 以上定义既适合无向图，又适合有向图。,2020/8/6,欧拉通路和欧拉回路的特征,欧拉通路是经过图中所有边的通路中长度最短的通路，即为通过图中所有边的简单通路； 欧拉回路是经过图中所有边的回路中长度最短的回路，即为通过图中所有边的简单回路。 如果仅用边来描述，欧拉通路和欧拉回路就是图中所有边的一种全排列。,2020/8/6,例11.2.1,判断下面的6个图中，是否是欧拉图？是否存在欧拉通路？,欧拉图,欧拉图,不是欧拉图，但存在欧拉通路,不存在欧拉通路,不存在

3、欧拉通路,不是欧拉图，但存在欧拉通路,2020/8/6,11.2.2 欧拉图的判定,定理11.2.1 无向图G = 具有一条欧拉通路，当且仅当G是连通的，且仅有零个或两个奇度数结点。 分析 只要找到了，就是存在的。我们具体找一条欧拉通路。对于结点的度数，我们在通路中去计算。 证明 若G为平凡图，则定理显然成立。故我们下面讨论的均为非平凡图。,2020/8/6,必要性：G有欧拉通路 = G连通，且仅有零个或两个奇度数结点,设G具有一条欧拉通路L = ，则L经过G中的每条边，由于G中无孤立结点，因而L经过G的所有结点，所以G是连通的。 对欧拉通路L的任意非端点的结点 ，在L中每出现 一次，都关联两

4、条边 和 ，而当 重复出现时，它又关联另外的两条边，由于在通路L中边不可能重复出现，因而每出现一次都将使某点获得2度。若在L中重复出现p次，则deg( )= 2p。,2020/8/6,必要性：G有欧拉通路 = G连通，且仅有零个或两个奇度数结点,若端点 ，设 、 在通路中作为非端点分别出现p1和p2次，则 deg( )= 2p1+1，deg( ) = 2p2+1 因而G有两个度数为奇数的结点。 若端点 = ，设在通路中作为非端点出现p3次，则 deg( )= 1+2p3+1 = 2(p3+1) 因而G无度数为奇数的结点。,2020/8/6,充分性：构造性证明。,从两个奇度数结点之一开始(若无奇

5、度数结点，可从任一结点开始)构造一条欧拉通路，以每条边最多经过一次的方式通过图中的边。 对于度数为偶数的结点，通过一条边进入这个结点，总可以通过一条未经过的边离开这个结点，因此，这样的构造过程一定以到达另一个奇度数结点而告终(若无奇度数结点，则以回到原出发点而告终)。 如果图中所有的边已用这种方式经过了，显然这就是所求的欧拉通路。如果图中不是所有的边都经过了，则去掉已经过的边，得到一个由剩余的边组成的子图，这个子图的所有结点的度数均为偶数。,2020/8/6,因为原来的图是连通的，因此，这个子图必与我们已经过的通路在一个或多个结点相接。 从这些结点中的一个开始，我们再通过边构造通路，因为结点的

6、度数全是偶数，因此，这条通路一定最终回到起点。我们将这条回路加到已构造好的通路中间组合成一条通路。如有必要，这一过程重复下去，直到我们得到一条通过图中所有边的通路，即欧拉通路。 由定理11.2.1的证明知：若连通的无向图有两个奇度数结点，则它们是G中每条欧拉通路的端点。,2020/8/6,结论,推论11.2.1 无向图G = 具有一条欧拉回路，当且仅当G是连通的，并且所有结点的度数均为偶数。 定理11.2.2 有向图G具有一条欧拉通路，当且仅当G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。 推论11.2.2

7、有向图G具有一条欧拉回路，当且仅当G是连通的，且所有结点的入度等于出度。,2020/8/6,欧拉通路与欧拉回路判别准则,对任意给定的无向连通图，只需通过对图中各结点度数的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图；对任意给定的有向连通图，只需通过对图中各结点出度与入度的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图。 利用这项准则，很容易判断出哥尼斯堡七桥问题是无解的，因为它所对应的图中所有4个结点的度数均为奇数；也很容易得到例11.2.1的结论。,2020/8/6,定义11.2.2,设G = ，eE，如果 p(G-e)p(G) 称e为G的桥(Bridg

8、e)或割边(Cut edge)。 显然，所有的悬挂边都是桥。,2020/8/6,Fleury算法,算法11.2.1 求欧拉图G = 的欧拉回路的Fleury算法： （1）任取v0V，令P0 = v0，i = 0； （2）按下面的方法从E-e1, e2, , ei中选取ei+1： a. ei+1与vi相关联； b. 除非无别的边可选取，否则ei+1不应该为G = G-e1, e2, , ei中的桥； （3）将边ei+1加入通路P0中，令P0 = v0e1v1e2eiviei+1vi+1，i = i+1； （4）如果i = |E|，结束，否则转(2)。,2020/8/6,例11.2.2,用Fleu

9、ry算法求欧拉图的一条欧拉回路。,v1,v7,v5,v3,v2,v8,v4,e1,e2,e3,e4,e5,e6,e10,e7,e8,e9,e11,e12,v6,分析 求从v1出发，按照Fleury算法，每次走一条边，在可能的情况下，不走桥。例如，在得到 P7 = v1e1v2e2v3e3v4e4v5e5v6e6v7e7v8 时，G = G-e1, e2, , e7中的e8是桥，因此下一步选择走e9，而不要走e8。,解 从v1出发的一条欧拉回路为： P12 = v1e1v2e2v3e3v4e4v5e5v6e6v7e7v8e9v2e10v4e11v6e12v8e8v1,2020/8/6,11.2.

10、3 欧拉图的难点,仅有欧拉通路而无欧拉回路的图不是欧拉图； 图中是否存在欧拉通路、欧拉回路图的判定非常简单，只需要数一下图中结点的度数即可； 使用Fleury算法求欧拉通路(回路)时，每次走一条边，在可能的情况下，不走桥。,2020/8/6,11.2.4 欧拉图的应用,1、一笔画问题 所谓“一笔画问题”就是画一个图形，笔不离纸，每条边只画一次而不许重复，画完该图。 “一笔画问题”本质上就是一个无向图是否存在欧拉通路(回路)的问题。如果该图为欧拉图，则能够一笔画完该图，并且笔又回到出发点；如果该图只存在欧拉通路，则能够一笔画完该图，但笔回不到出发点；如果该图中不存在欧拉通路，则不能一笔画完该图。

11、,2020/8/6,例11.2.3,图中的三个图能否一笔画？为什么？,解 因为图(a)和(b)中分别有0个和2个奇度数结点，所以它们分别是欧拉图和存在欧拉通路，因此能够一笔画，并且在(a)中笔能回到出发点，而(b)中笔不能回到出发点。图c中有4个度数为3的结点，所以不存在欧拉通路，因此不能一笔画。,2020/8/6,2、蚂蚁比赛问题,例11.2.4 甲、乙两只蚂蚁分别位于图的结点A、B处，并设图中的边长度相等。甲、乙进行比赛：从它们所在的结点出发，走过图中所有边最后到达结点C处。如果它们的速度相同，问谁先到达目的地？,解 图中仅有两个度数为奇数的结点B、C，因而存在从B到C的欧拉通路，蚂蚁乙走

12、到C只要走一条欧拉通路，边数为9条，而蚂蚁甲要想走完所有的边到达C，至少要先走一条边到达B，再走一条欧拉通路，因而它至少要走10条边才能到达C，所以乙必胜。,2020/8/6,3、计算机鼓轮设计,假设一个旋转鼓的表面被等分为24个部分，如图所示，其中每一部分分别由导体或绝缘体构成，图中阴影部分表示导体，空白部分表示绝缘体，导体部分给出信号1，绝缘体部分给出信号0。根据鼓轮转动时所处的位置，,四个触头A、B、C、D将获得一定的信息。因此，鼓轮的位置可用二进制信号表示。试问如何选取鼓轮16个部分的材料才能使鼓轮每转过一个部分得到一个不同的二进制信号，即每转一周，能得到0000到1111的16个数。

13、,2020/8/6,问题的等价描述与解决方法,问题的等价描述：把16个二进制数排成一个圆圈，使得四个依次相连的数字所组成的16个四位二进制数互不相同。 问题的解决思想：设ai0,1(i= 1,2,3, 16)，鼓轮每转一个部分，信号就从a1a2a3a4变为a2a3a4a5，前者的右三位决定了后者的左三位。 我们可把所有三位二进制数作为结点，从每个结点a1a2a3到a2a3a4连一条有向边表示a1a2a3a4这个四位二进制数，作出的所有可能的码变换的有向图。,2020/8/6,所有可能的码变换的有向图,e00000e81000 e10001e91001 e20010e101010 e30011e

14、111011 e40100e121100 e50101e131101 e60110e141110 e70111e151111,2020/8/6,问题的求解,问题转化为在这个有向图中找一条欧拉回路。 这个有向图中8个结点的出度和入度都是2，因此存在欧拉回路。 例如e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8就是一条欧拉回路。根据邻接边的标号记法，这16个二进制数的可写成对应的二进制序列0000100110101111，把这个序列排成一个圆圈，与所求的鼓轮相对应，就得到鼓轮的设计。,2020/8/6,推广,存在一个2n个二进制数的循环序列，其中2n个由n位二进制数组

15、成的子序列全不相同。 将上述2n个二进制数的循环序列称为布鲁因(De Brujin)序列。,2020/8/6,11.3 哈密顿图,11.2.1 哈密顿的引入与定义,2020/8/6,哈密顿图,定义11.3.1 经过图中每个结点一次且仅一次的通路(回路)称为哈密顿通路(回路)(Hamiltonian Entry/circuit)。存在哈密顿回路的图称为哈密顿图(Hamiltonian Graph)。 规定：平凡图为哈密顿图。 以上定义既适合无向图，又适合有向图。,2020/8/6,哈密顿通路和哈密顿回路的特征,哈密顿通路是经过图中所有结点的通路中长度最短的通路，即为通过图中所有结点的基本通路；

16、哈密顿回路是经过图中所有结点的回路中长度最短的回路，即为通过图中所有结点的基本回路。 如果仅用结点来描述： 哈密顿通路就是图中所有结点的一种全排列 哈密顿回路就是图中所有结点的一种全排列再加上该排列中第一个结点的一种排列。,2020/8/6,例11.3.1,判断下面的6个图中，是否是哈密顿图？是否存在哈密顿通路？,哈密 顿图,不存在哈密顿通路,不是哈密顿图，但存在哈密顿通路,哈密 顿图,不是哈密顿图，但存在哈密顿通路,不存在哈密顿通路,2020/8/6,11.3.2 哈密顿图的判定,定理11.3.1 设无向图G = 是哈密顿图，V1是V的任意非空子集，则 p(G-V1) |V1| 其中p(G-

17、V1)是从G中删除V1后，所得到的图的连通分支数。 分析 考察G的一条哈密顿回路C，显然C是G的生成子图，从而C-V1也是G-V1的生成子图，且有p(G-V1) p(C-V1)，故只需要证明p(C-V1) |V1|即可。,2020/8/6,定理11.3.1 证明,设C是G中的一条哈密顿回路，V1是V的任意非空子集。下面分两种情况讨论： （1）V1中结点在C中均相邻，删除C上V1中各结点及关联的边后，C-V1仍是连通的，但已非回路，因此p(C-V1) = 1 |V1|。 （2）V1中结点在C上存在r(2 r |V1|)个互不相邻，删除C上V1中各结点及关联的边后，将C分为互不相连的r段，即 p(

18、C-V1) = r |V1|。 一般情况下，V1中的结点在C中即有相邻的，又有不相邻的，因此总有p(C-V1) |V1|。 又因C是G的生成子图，从而C-V1也是G-V1的生成子图，故有 p(G-V1) p(C-V1) |V1|,2020/8/6,推论11.3.1,设无向图G = 中存在哈密顿通路，则对V的任意非空子集V1，都有 p(G-V1) |V1| + 1,注意： 若存在V的某个非空子集V1使得p(G-V1)|V1|，则G不是哈密顿图。,2020/8/6,例11.3.2,证明图中不存在哈密顿回路。,证明：删除结点子集d, e, f，得新图，它的连通分支为4个，因而不会存在哈密顿回路。,2

19、020/8/6,定理11.3.2,设G = 是具有n个结点的简单无向图。如果对任意两个不相邻的结点u, vV，均有 deg(u) + deg(v) n-1 则G中存在哈密顿通路。 证明 首先证明满足上述条件的G是连通图。 用反证法：假设G有两个或更多连通分支。 设一个连通分支有n1个结点，另一个连通分支有n2个结点。这二个连通分支中分别有两个结点v1、v2。 显然，deg(v1)n1-1，deg(v2)n2-1。 从而deg(v1)+deg(v2)n1+n2-2 n-2与已知矛盾，故G是连通的。,2020/8/6,定理11.3.2 证明(续),其次，证明G中存在哈密顿通路。 设P = v1v2

20、vk为G中用“延长通路法”得到的“极大基本通路”，即P的始点v1与终点vk不与P外的结点相邻，显然k n。 （1）若k = n，则P为G中经过所有结点的通路，即为哈密顿通路。 （2）若k n，说明G中还有在P外的结点，但此时可以证明存在仅经过P上所有结点的基本回路，证明如下： （a）若在P上v1与vk相邻，则v1v2vkv1为仅经过P上所有结点的基本回路。,2020/8/6,定理11.3.2 证明(续),（b）若在P上v1与vk不相邻，假设v1在P上与vi1= v2,vi2,vi3,vij相邻(j必定大于等于2，否则deg(v1)+deg(vk) 1+k-2n-1)， 此时vk必与vi2,vi

21、3,vij相邻的结点vi2-1,vi3-1,vij-1至少之一相邻(否则deg(v1) + deg(vk) j+k-2-(j-1) = k-1n-1)。设vk与vir-1(2rj)相邻，如图所示。,2020/8/6,定理11.3.2 证明(续),在P中添加边(v1,vir)、(vk,vir-1)，删除边(vir-1,vir)得基本回路C = v1v2vir-1vkvk-1virv1。,2020/8/6,定理11.3.2 证明(续),（3）证明存在比P更长的通路。 因为kn，所以V中还有一些结点不在C中，由G的连通性知，存在C外的结点与C上的结点相邻，不妨设vk+1V-V(C)且与C上结点vt相

22、邻，在C中删除边(vt-1,vt)而添加边(vt,vk+1)得到通路P= vt-1v1virvkvir-1vtvk+1。 显然，P比P长1，且P上有k+1个不同的结点。 对P重复(1)(3)，得到G中的哈密顿通路或比P更长的基本通路。 由于G中结点数目有限，故在有限步内一定得到G中的一条哈密顿通路。,2020/8/6,推论,推论11.3.2 设G = 是具有n个结点的简单无向图。如果对任意两个不相邻的结点u, vV，均有 deg(u) + deg(v) n 则G中存在哈密顿回路。 推论11.3.3 设G = 是具有n个结点的简单无向图，n3。如果对任意vV，均有deg(v) n/2，则G是哈密

23、顿图。,哈密顿图的充分条件，而非必要条件。,2020/8/6,例11.3.3,某地有5个风景点，若每个风景点均有2条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这5处？ 解 将5个风景点看成是有5个结点的无向图，两风景点间的道路看成是无向图的边，因为每处均有两条道路与其他结点相通，故每个结点的度数均为2，从而任意两个不相邻的结点的度数之和等于4，正好为总结点数减1。故此图中存在一条哈密顿通路，因此游人可以经过每个风景点恰好一次而游完这5处。,2020/8/6,例11.3.4,判断下图是否存在哈密顿回路。,解 方法一：在图中，删除结点子集a, b, c, d, e，得到的图有7个连通

24、分支，由定理11.2.1知，该图不是哈密顿图，因而不会存在哈密顿回路。,方法二：若图中存在哈密顿回路，则该回路组成的图中任何结点的度数均为2。因而结点1、2、3、4、5所关联的边均在回路中，于是在结点a、b、c、d、e处均应将不与1、2、3、4、5关联的边删除，而要删除与结点a、b、c、d、e关联的其它边，得到右上图，它不是连通图，因而图中不存在哈密顿回路。,2020/8/6,例11.3.5,证明下图没有哈密顿通路。,证明 任取一结点如1用A标记，所有与它邻接的结点用B标记。继续不断地用A标记所有邻接于B的结点，用B标记所有邻接于A的结点，直到所有结点都标记完毕。 如果图中有一条哈密顿通路，那

25、么它必交替通过结点A和B，故而标记A的结点与标记B的结点数目或者相同，或者相差1个。然而图中有3个结点标记为A，5个结点标记为B，它们相差两个，所以该图不存在哈密顿通路。,2020/8/6,定理11.3.3,设G = 是有n(n2)个结点的一些简单有向图。如果忽略G中边的方向所得的无向图中含生成子图Kn，则有向图G中存在哈密顿通路。,在右图中，它所对应的无向图中含完全图K5，由定理11.3.3知，图中含有哈密顿通路。事实上，通路v3v5v4v2v1为一条哈密顿通路。,2020/8/6,11.3.3 哈密顿图的难点,仅有哈密顿通路而无哈密顿回路的图不是哈密顿图； 还没有判断图中是否存在欧拉通路、

26、欧拉回路图的简单判定定理，我们只能对结点较少的图凭经验去判定； 在哈密顿图中有定理仅是必要条件，此必要条件正方面的叙述无法用来判断一个图是否是哈密顿图，此时该定理是毫无用处的，但必要条件的等价逆叙述却非常的重要，用此逆叙述可以判断一个图不是哈密顿图。,2020/8/6,11.3.4 哈密顿图的应用,1、巡回售货员问题 G = 是n个结点的赋权完全图，这里V = v1, v2, , vn是城市的集合，E是连接城市的道路的集合，W是从E到正实数集合的一个函数(即W(vi, vj)是城市vi与vj之间的距离)，显然对V中任意三个城市vi, vj, vk，显然它们之间的距离应满足三角不等式： W(vi

27、, vj) + W(vj, vk)W(vi, vk)， 试求出该赋权图上的最短哈密顿回路。,2020/8/6,算法11.3.1 最邻近算法：,以vi为始点，在其余n-1个结点中，找出与始点最邻近的结点vj(如果与vi最邻近的结点不唯一，则任选其中的一个作为vj)，形成具有一条边的通路vivj； 假设x是最新加入到这条通路中的结点，从不在通路上的结点中选取一个与x最邻近的结点，把连接x与此结点的边加到这条通路中。重复这一步，直到G中所有结点都包含在通路中； 把始点和最后加入的结点之间的边放入，就得到一条回路。,2020/8/6,8,16,7,12,4,例11.3.6,用最邻近算法计算下图的以a为

28、始点的一条近似最短哈密顿回路。,回路的总距离为47,2020/8/6,其它结点为始点的哈密顿回路,以b为始点的哈密顿回路为：badecb，总距离为：42。 以c为始点的哈密顿回路为：cbadec，总距离为：42；或cdaebc，总距离为：35；或cdabec，总距离为：42。 以d为始点的哈密顿回路为：dabecd，总距离为：42；或daebcd，总距离为：35。 以e为始点的哈密顿回路为：eadbce，总距离为：41。,2020/8/6,分析及结论,图中最短哈密顿回路的长度为35 最长哈密顿回路的长度为48。 若以a为始点，用最邻近算法求得的哈密顿回路的长度为47，几乎达到了最长哈密顿回路的

29、长度。 最邻近算法不是好的算法。可以证明这个算法的误差可以很大。,2020/8/6,算法11.3.2 抄近路算法：,求G中的一棵最小生成树T； 将T中各边均加一条与原边权值相同的平行边，设所得图为G，显然G是欧拉图； 求G中的一条欧拉回路E； 在E中按如下方法求从结点v出发的一个哈密顿回路H：从v出发，沿E访问G中各个结点，在没有访问完所有结点之前，一旦出现重复出现的结点，就跳过它走到下一个结点，称这种走法为抄近路走法。W(H)作为最短哈密顿回路的长度(设为d0)的近似值。,2020/8/6,例11.3.7,用抄近路算法计算下图的以a为始点的一条近似最短哈密顿回路。 求一棵最小生成树T； 将T

30、中各边均加平行边； 求从结点a出发的欧拉回路Ea = aeadabcba； 求从结点a出发按抄近路走法的哈密顿回路Ha = aedbca； W(Ha) = 41。,2020/8/6,其它结点为始点的哈密顿回路,求图的一棵最小生成树T； 将T中各边均加平行边； 从结点c出发的欧拉回路为Ec = cbaeadabc； 从结点c出发按抄近路走法的哈密顿回路为Hc = cbaedc； W(Hc) = 36。,2020/8/6,定理11.3.4,设赋权完全图Kn(n3)满足三角不等式，d0是Kn中最短哈密顿回路的长度，H是用抄近路算法求出的Kn中的哈密顿回路，则 W(H) 2d0。,2020/8/6,定

31、理11.3.4 证明,设T是Kn中的最小生成树，E是将T中每边加平行边后的图中的欧拉回路，则W(E) = 2W(T)。由欧拉回路E产生哈密顿回路H时，因为Kn满足三角不等式，所以H的长度不会比E的权大，即 W(H) W(E) = 2W(T)。 Kn中的最短哈密顿回路H0去掉任意一条边就产生的一棵生成树T，从而有 W(T) W(T)d0 因此2W(T)2d0 故W(H)2d0,2020/8/6,2、中国邮路问题,一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应按怎样的路线走，他所走的路程才会最短呢？ 如果将这个问题抽象成图论的语言，就是给定一个连通图，连通图的每条边的权值为对应

32、的街道的长度(距离)，要在图中求一回路，使得回路的总权值最小。,2020/8/6,中国邮路问题,若图为欧拉图，只要求出图中的一条欧拉回路即可。否则，邮递员要完成任务就得在某些街道上重复走若干次。 如果重复走一次，就加一条平行边，于是原来对应的图就变成了多重图。只是要求加进的平行边的总权值最小就行了。 问题就转化为：在一个有奇度数结点的赋权连通图中，增加一些平行边，使得新图不含奇度数结点，并且增加的边的总权值最小。,2020/8/6,解决问题的步骤,要解决上述问题，应分下面两个大步骤。 首先，增加一些边，使得新图无奇度数结点，我们称这一步为可行方案(Feasible Scheme)； 其次，调整

33、可行方案，使其达到增加的边的总权值最小，称这个最后的方案为最佳方案(Optimal Scheme)。,2020/8/6,例11.3.8,在下图中，确定一条v1从v1到的回路，使它的权值最小。事实上，所确定的回路从任何一个结点出发都可以。,2020/8/6,第一个可行方案的确定,由于图中奇度数结点为偶数个，所以图中奇度数结点可以配对。又由于图的连通性，每对奇度数结点之间均存在基本通路，在配好对的奇度数结点之间各确定一条基本通路，然后将通路中的所有边均加一条平行边，这样产生的新图中无奇度数结点，因而存在欧拉回路。 图中奇度数结点有4个：v1, v3, v4, v6。任意将它们配2对：v1与v4配对

34、，v3与v6配对。选v1与v4之间的基本通路为v1v6v5v4，v3与v6之间的基本通路为v3v7v1v6。 每条通路中所含的边均加一条平行边。,2020/8/6,增加平行边的图如下图所示，它无奇度数结点，因而是欧拉图。 增加的边的总权值为 W(v3,v7)+W(v7,v1)+2W(v1,v6)+W(v6,v5)+W(v5,v4) = 13。,2020/8/6,调整可行方案，使增加的边的总数减少,图中边(v1,v6)的重数为3，若去掉两条边，既不影响v1,v6度数的奇偶性，也不影响图的连通性，因而可去掉两条边。一般情况下，若边的重数大于等于3，就去掉偶数条边。于是，有下面结论： I）在最优方案

35、中，图中每条边的重数小于等于2 如果将某条基本回路中的平行边均去掉，而给原来没有平行边的边加上平行边，也不影响图中结点度数的奇偶性。因而，如果在某条基本回路中，平行边的总权值大于该回路的权值的一半，就作上述调整。,2020/8/6,在图中，回路v1v2v3v7v1的权值为6，而平行边的总权值为4，大于3，因而应给予调整，调整后的图如右图所示。,我们又有下面的结论： II）在最优方案中，图中每个基本回路上平行边的总权值不大于该回路的权值的一半 经过以上调整的图，平行边的总权值为： W(v1,v2)+W(v2,v3)+W(v4,v5)+W(v5,v6)=5,2020/8/6,判断最佳方案的标准,一

36、个最佳方案是满足(1)、(2)的可行方案，反之，一个可行方案若满足(1)、(2)两条，它也一定是最佳方案。 因而I)、II)是最佳方案的充分必要条件。,右图满足I)、II)两条，从而是最佳方案，即图中的任意一条欧拉回路均为邮递员的最佳送信路线。,2020/8/6,11.4 偶图,11.4.1 偶图的定义 定义11.4.1 若无向图G = 的结点集V能够划分为两个子集V1, V2，满足V1V2 = ，且V1V2 = V，使得G中任意一条边的两个端点，一个属于V1，另一个属于V2，则称G为偶图(Bipartite Graph)或二分图(Bigraph)。 V1和V2称为互补结点子集，偶图通常记为G

37、 = 。 偶图没有自回路。 平凡图和零图可看成特殊的偶图。,2020/8/6,定义11.4.2,在偶图G = 中，若V1中的每个结点与V2中的每个结点都有且仅有一条边相关联，则称偶图G为完全偶图(Complete Bipartite Graph)或完全二分图(Complete Bigraph)。 记为Ki,j，其中，i = |V1|，j = |V2|。,2020/8/6,例11.4.1,判断图中的几个图，那些是偶图？那些是完全偶图？,偶图,偶图,偶图,偶图,不是偶图,完全偶图K2,3,完全偶图K3,3,完全偶图K3,3,2020/8/6,11.4.2 偶图的判定,定理11.4.1 无向图G =

38、 为偶图的充分必要条件是G中所有回路的长度均为偶数。 证明 必要性：设图G是偶图G = ，令C = v0v1v2vkv0是G的一条回路，其长度为k+1。 不失一般性，假设v0V1，由偶图的定义知，v1V2，v2V1。由此可知，v2iV1且v2i+1V2。 又因为v0V1，所以vkV2，因而k为奇数，故C的长度为偶数。,2020/8/6,充分性：证明G = 为偶图,设G中每条回路的长度均为偶数，若G是连通图，任选v0V，定义V的两个子集如下： V1 = vi | d(v0, vi)为偶数， V2 = V-V1 现证明V1中任两结点间无边存在。 假若存在一条边(vi, vj)E，其中vi, vjV

39、1，则由v0到vi间的短程线(长度为偶数)以及边(vi, vj)，再加上vj到v0间的短程线(长度为偶数)所组成的回路的长度为奇数，与假设矛盾。,2020/8/6,充分性（续）：,同理可证V2中任两结点间无边存在。 故G中每条边(vi, vj)，必有viV1，vjV2或viV2，vjV1，因此G是具有互补结点子集V1和V2的偶图。 若G中每条回路的长度均为偶数，但G不是连通图，则可对G的每个连通分支重复上述论证，并可得到同样的结论。,2020/8/6,定理11.4.1的用途,在实际应用中，定理11.4.1本身使用不多，我们常使用它的逆否命题来判断一个图不是偶图： 无向图G不是偶图的充分必要条件

40、是G中存在长度为奇数的回路。 例如下图中存在长度为3的回路v1v2v4v1，所以它不是偶图。,2020/8/6,11.4.3 匹配,定义11.4.2 在偶图G = 中，V1 = v1, v2, , vq，若存在E的子集E = (v1, v1)，(v2, v2)，(vq, vq)，其中v1, v2, , vq 是V2中的q个不同的结点，则称G的子图G = 为从V1到V2的一个完全匹配(Complete Matching)，简称匹配。,2020/8/6,必要条件,在偶图G = 中，若存在V1到V2的单射f，使得对任意vV1，都有(v, f(v)E，则存在V1到V2的匹配。 由单射的性质知，不是所有

41、的偶图都有匹配，存在匹配的必要条件是|V1| |V2|。 然而，这个条件并不是充分条件。,2020/8/6,例11.4.2,下面的3个偶图哪些存在V1到V2匹配？对存在匹配的偶图给出一个匹配。,不存在匹配,不存在匹配,存在匹配,2020/8/6,霍尔定理,定理11.4.2 (霍尔定理) 偶图G = 中存在从V1到V2的匹配的充分必要条件是V1中任意k个结点至少与V2中的k个结点相邻，k = 1, 2, , |V1|。 定理11.4.2中的条件通常称为相异性条件(Diversity Condition)。,2020/8/6,例,不满足相异性条件，故没有匹配。,满足相异性条件，故存在匹配,2020

42、/8/6,定理11.4.3,设G = 是一个偶图。如果满足条件 （1）V1中每个结点至少关联t条边； （2）V2中每个结点至多关联t条边； 则G中存在从V1到V2的匹配。其中t为正整数。 该定理是偶图G存在匹配的充分性条件。 优点：计算量少。只需要判断V1中结点的最小度数与V2中结点的最大度数即可。,2020/8/6,定理11.4.3证明,设G = 是一个偶图。如果满足条件 （1）V1中每个结点至少关联t条边； （2）V2中每个结点至多关联t条边； 则G中存在从V1到V2的匹配。其中t为正整数。 证明 由条件(1)知，V1中k个结点至少关联tk条边(1k|V1|)，由条件(2)知，这tk条边至

43、少与V2中k个结点相关联，于是V1中的k个结点至少与V2中的k个结点相邻接，因而满足相异性条件，所以G中存在从V1到V2的匹配。,2020/8/6,11.4.4 偶图的难点,判断一个图是否是偶图已有充分必要条件，更重要的是，我们经常使用其逆叙述来判断一个图不是偶图； 匹配本质上是一个单射； 判断一个偶图是否存在匹配的相异性条件通常比较复杂，通常在考察相异性条件之前，先判断是否满足t条件。,2020/8/6,11.4.5 偶图的应用,例11.4.3 有n台计算机和n个磁盘驱动器。每台计算机与m0个磁盘驱动器兼容，每个磁盘驱动器与m台计算机兼容。能否为每台计算机配置一台与它兼容的磁盘驱动器？ 解

44、用V1表示n台计算机的集合，V2表示n台磁盘驱动器的集合。以V1，V2为互补结点子集，以E = (vi, vj) | viV1, vjV2且vi与vj兼容为边集，构造偶图。它显然满足t条件(t = m)，所以存在匹配，故能够为每台计算机配置一台与它兼容的磁盘驱动器。,2020/8/6,例11.4.4,现有三个课外小组：物理组，化学组和生物组，有五个学生s1,s2,s3,s4,s5。 （1）已知s1,s2为物理组成员；s1,s3,s4为化学组成员；s3,s4,s5为生物组成员。 （2）已知s1为物理组成员；s2,s3,s4为化学组成员；s2,s3,s4,s5为生物组成员。 （3）已知s1即为物理

45、组成员，又为化学组成员；s2,s3,s4,s5为生物组成员。 在以上三种情况的每一种情况下，在s1,s2,s3,s4, s5中选三位组长，不兼职，问能否办到？,2020/8/6,例11.4.4 解,用c1,c2,c3分别表示物理组、化学组和生物组。 V1=c1,c2,c3，V2=s1,s2,s3,s4,s5 以V1，V2为互补结点子集，以E=(ci,sj)|ciV1, sjV2且ci中有成员sj为边集，构造偶图。,不存在匹配,2020/8/6,11.5 平面图,11.5.1 平面图的定义 在一张纸上画几何模型时常常会发现，不仅需要允许各边在结点处相交，而且还应该允许各边在某些非结点处相交，这样

46、的点称为交叉点(Cross Point)；而相交的边，称为交叉边(Cross Edge)。,2020/8/6,定义11.5.1,如果能把一个无向图G的所有结点和边画在平面上，使得任何两边除公共结点外没有其他交叉点，则称G为平面图(Plane Graph)，否则称G为非平面图(Nonplanar Graph)。 当且仅当一个图的每个连通分支都是平面图时，这个图是平面图。,2020/8/6,非平面图,有些图形不论如何改画，除去结点外，总有边相交叉。 即不管怎样改画，至少有一条边与其他边相交叉，故它是非平面图。,2020/8/6,11.5.2 观察法,设G是画于平面上的图，并设 C = v1v2v3

47、v4v1 是G中的任何基本回路。此外，设P1 = v1v3和P2 = v2v4是G中的任意两条无公共结点的基本通路。,观察法,2020/8/6,例11.5.1,用观察法来判定图K3,3为非平面图。,2020/8/6,11.5.3 欧拉公式,定义11.5.2 在平面图G的一个平面表示中， 由边所包围的其内部不包含图的结点和边的区域，称为G的一个面(Surface)， 包围该面的诸边所构成的回路称为这个面的边界(Bound)， 面r的边界的长度称为该面的次数(Degree)，记为D(r)。 区域面积有限的面称为有限面(Finite Surface)，区域面积无限的面称为无限面(Infinite S

48、urface)。 平面图有且仅有一个无限面。,2020/8/6,面的形象描述：,假设我们把一个平面图的平面表示画在平面上，然后用一把小刀，沿着图的边切开，那么平面就被切成许多块，每一块就是图的一个面。 更确切地说，平面图的一个面就是平面的一块，它用边作边界线，且不能再分成子块。,2020/8/6,例11.5.2,考察下图所示平面图的面、边界和次数。,解 平面图把平面分成4个面： r0，边界为abdeheca，D(r0)=7 r1，边界为abca，D(r1)=3 r2，边界为becikijicb，D(r2)=9 r3，边界为bdeb，D(r3)=3 r1、r2和r3是有限面，r0是无限面。,20

49、20/8/6,例11.5.2,注意：对于平面图的不同平面表示，虽然面的数目相同，但各面的边界和次数会不同。,2020/8/6,定理11.5.1,平面图中所有面的次数之和等于边数的二倍。 证明 因任何一条边，或者是两个面边界的公共边，或者是在一个面中作为边界被重复计算两次，故平面图所有面的次数之和等于其边数的二倍。 1750年，欧拉发现，任何一个凸多面体，若有n个顶点、m条棱和r个面，则有n-m+r = 2。这个公式可以推广到平面图上来，称之为欧拉公式。,2020/8/6,欧拉公式,定理11.5.2 设G = 是连通平面图，若它有n个结点、m条边和r个面，则有 n-m+r = 2 证明 我们对G

50、的边数m进行归纳。 若m = 0，由于G是连通图，故必有n = 1，这时只有一个无限面，即r = 1。所以 n-m+r = 1-0+1 = 2 定理成立。,2020/8/6,定理11.5.2 证明（续）, 若m = 1，这时有两种情况： （1）该边是自回路，则有n=1，r=2，这时 n - m + r = 1 1 + 2 = 2 （2）该边不是自回路，则有n=2，r=1，这时 n m + r = 2 1 + 1 = 2 所以m=1时，定理也成立。 假设对少于m条边的所有连通平面图，欧拉公式成立。 现考虑m条边的连通平面图，设它有n个结点。分以下两种情况：,2020/8/6,定理11.5.2 证

51、明（续）,（1）若G是树，那么m=n-1，这时r=1。所以 n-m+r = n-(n-1)+1 = 2 （2）若G不是树，则G中必有回路，因此有基本回路，设e是某基本回路的一条边，则G= 仍是连通平面图，它有n个结点，m-1条边和r-1个面，按归纳假设知 n-(m-1)+(r-1) = 2 整理得 n-m+r=2 所以对m条边时，欧拉公式也成立。,2020/8/6,代入欧拉公式有2n-m+kn-m+2m/3 即2n-m/3 整理得m3n-6,推论11.5.1,设G是一个(n,m)简单连通平面图，若m1，则有 m3n-6 证明 设G有k个面，因为G是简单图，所以G的每个面至少由3条边围成。所以G

52、所有面的次数之和,由定理11.5.1知，2m3k，即k2m/3，,平面图中所有面的次数之和等于边数的二倍,2020/8/6,说明,推论11.5.1本身可能用处不大，但它的逆否命题却非常有用，可以用它来判定某些图是非平面图。即 一个简单连通图，若不满足m3n-6，则一定是非平面图。 但需要注意，满足不等式m3n-6的简单连通图未必是平面图。,2020/8/6,例11.5.3,证明5个结点的完全图K5是非平面图。 分析 因为K5是简单连通图，我们可以验证m 3n-6不成立，因此它不是平面图。 证明 因为K5是简单连通图，n=5，m=10，因此m3n-6=35-6=9，故不满足m3n-6，因此它不是

53、平面图。 再看图K3,3，n=6，m=9，满足不等式m3n-6，但是我们已用观察法证明了它是一个非平面图。,2020/8/6,推论11.5.2,设G是一个(n, m)简单连通平面图，若每个面的次数至少为k(k3)，则有,证明 设G共有r个面，各面的次数之和为T， 由条件可知Tkr 又由定理11.5.1知T = 2m 利用欧拉公式解出面数 r = 2-n+m 由此得出下式成立2mk(2-n+m) 从而有(k-2)m k(n-2) 由于k3，因而结论成立,2020/8/6,说明,推论11.5.2本身可能用处不大，但它的逆否命题却非常有用，可以用它来判定某些图是非平面图。即 一个简单连通图，若每个面的次数至少为k(k3)，若不满足 ，则一定是非平面图。,2020/8/6,例11.5.4,不使用观察法证明图K3,3是一个非平面图。 证明 利用推论11.5.2可以判断。事实上，假设K3,3是一个平面图，那么它的每个面的次数均不能小于