《离散数学-第八章：几种特殊的图.ppt》由会员分享，可在线阅读，更多相关《离散数学-第八章：几种特殊的图.ppt（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、几种特殊的图几种特殊的图哥尼斯堡七桥问题哥尼斯堡城（现在俄罗斯）在哥尼斯堡城（现在俄罗斯）在18世纪属东普鲁士，世纪属东普鲁士，它位于普雷格尔（它位于普雷格尔（Pregel）河畔，河中有两个岛，）河畔，河中有两个岛，通过七座桥彼此相联，如下图：通过七座桥彼此相联，如下图：。A AB BC CD D2内容提要内容提要 8.1 二部图 8.2 欧拉图与哈密尔顿图 8.3 平面图 38.1 二部图二部图 引例：今有引例：今有4个工人个工人a1,a2,a3,a4,4项任务项任务b1,b2,b3,b4。已知工人。已知工人a1熟悉任务熟悉任务b1,b2,b3,a2熟熟悉悉b2,b3,a3只熟悉只熟悉b4,
2、a4熟悉熟悉b3和和b4。问如何分配。问如何分配工人，才能使每人都有任务，且每项任务都有人工人，才能使每人都有任务，且每项任务都有人来完成？其实，只要以来完成？其实，只要以 V=a1,a2,a3,a4,b1,b2,b3,b4为顶点集，为顶点集，若若ai熟悉熟悉bj,就在就在ai和和bj之间连边，得边集之间连边，得边集E,构成无构成无向图向图G=,如下图所示。如下图所示。48.1 二部图二部图由图显而易见，由图显而易见，分配分配a1去完成去完成b1,a2去完成去完成B2,a3去完成去完成b4，a4去完成去完成B3就能满足要求。就能满足要求。在此图中，在此图中，a1,a2,a3,a4彼此彼此不相邻
3、，不相邻，b1,b2,b3,b4也彼此也彼此不相邻。像这样的图，称它为二部图。不相邻。像这样的图，称它为二部图。58.1 二部图二部图定义定义8.1.1 若能将无向图的顶点集若能将无向图的顶点集V分成两个子集分成两个子集V1和和V2(V1 V2=),使得使得G中任何一条边的两个端中任何一条边的两个端点都一个属于点都一个属于V1,另一个属于另一个属于V2,则称则称G为为二部图二部图（或称偶图、双图、二分图），（或称偶图、双图、二分图），V1,V2称为互补顶称为互补顶点子集点子集.若若G是二部图，也可将是二部图，也可将G记为记为G=。又若又若V1中任一顶点与中任一顶点与V2中任一顶点均有且仅有中任
4、一顶点均有且仅有一条边相关联，则称二部图一条边相关联，则称二部图G为为完全二部图完全二部图。若。若|V1|=r,|V2|=s,则记完全二部图为则记完全二部图为Kr,s68.1 二部图二部图 注注:在完全二部图在完全二部图Kr,s中，它的顶点数中，它的顶点数n=r+s，它的边数它的边数m=rs.定理定理8.1.1 一个无向图一个无向图G=是二部图当且仅是二部图当且仅当当G中无奇数长度的回路。中无奇数长度的回路。7如如图所示各所示各图都是二部都是二部图，其中，其中，(1)，(2)，(3)为K6的子的子图，(3)为完全二部完全二部图K3,3，常将，常将K3,3画成与其同构的画成与其同构的(5)的形的
5、形式，式，K3,3是下文中是下文中经常遇到的常遇到的图。(4)是是K5的子的子图，它是完全，它是完全二部二部图K2,3，K2,3常画成常画成(6)的形式。的形式。注意，注意，n n阶零图为二部图。阶零图为二部图。88 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图引例：引例：哥尼斯堡七桥问题哥尼斯堡七桥问题 如何不重复地走完七桥后回到起点？如何不重复地走完七桥后回到起点？。A AB BC CD D98 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图一、欧拉图一、欧拉图定义定义8.2.1 给定无孤立结点图给定无孤立结点图G=，若存在，若存在一条通路，经过图中每条边一次且仅一次，该通一条通路，
6、经过图中每条边一次且仅一次，该通路称作路称作欧拉通路欧拉通路；若；若G中欧拉通路又是回路，则称中欧拉通路又是回路，则称它为它为G中的中的欧拉回路欧拉回路；具有欧拉回路的图称为；具有欧拉回路的图称为欧拉欧拉图图。注意：只有欧拉通路无欧拉回路的图不是欧拉图。注意：只有欧拉通路无欧拉回路的图不是欧拉图。108 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图(a)无欧拉通路无欧拉通路(b)无欧拉回路无欧拉回路(c)是欧拉图是欧拉图118 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图定理定理8.2.1 无向图无向图G具有一条欧拉通路，当且仅当具有一条欧拉通路，当且仅当G是连通是连通的，且有零个或两
7、个奇数度结点。的，且有零个或两个奇数度结点。证明证明 必要性必要性设设G具有欧拉通路，即有点边序列具有欧拉通路，即有点边序列 v0e1v1e2v2eiviei+1ekvk,其中结点可能重复出现，但边其中结点可能重复出现，但边不重复，因为欧拉通路经过所有图不重复，因为欧拉通路经过所有图G的结点，故图的结点，故图G是连通是连通的。的。对任意一个不是端点（始点和终点）的结点对任意一个不是端点（始点和终点）的结点vi,在欧拉在欧拉通路中每当通路中每当vi出现一次，必关联两条边，故出现一次，必关联两条边，故vi虽可重复出现，虽可重复出现，但但deg(vi)必是偶数。对于端点，若必是偶数。对于端点，若v0
8、=vk,则则d(v0)为偶数，为偶数，即即G中无奇数度结点；若端点中无奇数度结点；若端点v0与与vk不同，则不同，则d(v0)为奇数，为奇数，d(vk)为奇数，为奇数，G中就有两个奇数度结点。中就有两个奇数度结点。128 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图充分性充分性 若图若图G连通，有零个或两个奇数度结点，连通，有零个或两个奇数度结点，我们构造一条欧拉通路如下：我们构造一条欧拉通路如下：(1)若有两个奇数度结点，则从其中的一个结点若有两个奇数度结点，则从其中的一个结点考试构造一条迹，即从考试构造一条迹，即从v0出发经关联边出发经关联边e1“进入进入”v1,若若deg(v1)为偶
9、数，则可由为偶数，则可由v1再经关联边再经关联边e2进进入入v2,如此进行下去，每边仅取一次。由于如此进行下去，每边仅取一次。由于G是连是连通的，故必可到达另一奇数度结点停下，得到一通的，故必可到达另一奇数度结点停下，得到一条迹条迹L:v0e1v1e2v2eiviei+1ekvk.若若G中没有奇数中没有奇数度结点则从任一结点度结点则从任一结点v0出发，用上述方法必可回到出发，用上述方法必可回到结点结点v0,得到上述一条闭迹得到上述一条闭迹L1.138 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图(2)若若L1通过了通过了G的所有边，则的所有边，则L1就是欧拉通路。就是欧拉通路。(3)若若G
10、中去掉中去掉L1后得到子图后得到子图G,则则G中每个结点度中每个结点度数为偶数，因为原来的图是连通的，故数为偶数，因为原来的图是连通的，故L1与与G至少有一个结点至少有一个结点vi重合，在重合，在G中由中由vi出发重复出发重复(1)的方法，得到闭迹的方法，得到闭迹L2.(4)当当L1与与L2组合在一起，如果恰是组合在一起，如果恰是G,即得欧拉通即得欧拉通路，否则重复路，否则重复(3)可得到闭迹可得到闭迹L3,依此类推直到依此类推直到得到一条经过图得到一条经过图G中所有边的欧拉通路。中所有边的欧拉通路。148 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图 由于有了欧拉回路和欧拉通路的判别准则
11、，因由于有了欧拉回路和欧拉通路的判别准则，因此哥尼斯堡七桥问题立即有了确切的否定答案，此哥尼斯堡七桥问题立即有了确切的否定答案，因为从上图中可以看到因为从上图中可以看到deg(A)=5,deg(B)=deg(C)=deg(D)=3,故欧拉回路故欧拉回路必不存在。必不存在。A AB BC CD D158 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图欧拉通路和欧拉回路的概念，可以推广到有向图欧拉通路和欧拉回路的概念，可以推广到有向图中去。中去。定义定义8.2.2 给定有向图给定有向图G,通过图中每边一次且仅通过图中每边一次且仅一次的一条单向通路一次的一条单向通路(回路回路),称作单向欧拉通路称
12、作单向欧拉通路(回路回路)。定理定理 8.2.2 有向图有向图G具有一条单向欧拉回路，当具有一条单向欧拉回路，当且仅当是连通的，且每个结点入度等于出度。一且仅当是连通的，且每个结点入度等于出度。一个有向图个有向图G具有单向欧拉通路，当且仅当它是连通具有单向欧拉通路，当且仅当它是连通的，而且除两个结点之外，每个结点的入度等于的，而且除两个结点之外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度出度，但这两个结点中，一个结点的入度比出度大大1，另一个结点的入度比出度小，另一个结点的入度比出度小1。168 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图二、哈密尔顿图二、哈密尔顿图18
13、59年爱尔兰数学家威廉年爱尔兰数学家威廉.哈密顿首先提出在正十哈密顿首先提出在正十二面体上的一个数学游戏，即能否在如下所示的二面体上的一个数学游戏，即能否在如下所示的图中找到一条基本图中找到一条基本(初级初级)回路回路(或路径或路径)，使它经，使它经过每个顶点恰好一次。过每个顶点恰好一次。178 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图 由于他将每个顶点看作一个城市，将两个顶点由于他将每个顶点看作一个城市，将两个顶点之间的边看作交通线，于是他提出的问题称为之间的边看作交通线，于是他提出的问题称为“周周游世界问题游世界问题”。对于任何一个连通图，都可以提出。对于任何一个连通图，都可以提出
14、这样的问题，即在图中是否存在经过所有顶点一次这样的问题，即在图中是否存在经过所有顶点一次且仅一次的回路或通路。将这样的初级通路、回路且仅一次的回路或通路。将这样的初级通路、回路分别称为哈密尔顿通路、回路。分别称为哈密尔顿通路、回路。188 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图定义定义8.2.3 给定图给定图G,若存在一条通路经过图中的若存在一条通路经过图中的每个结点恰好一次，这条通路称作哈密尔顿路。每个结点恰好一次，这条通路称作哈密尔顿路。若存在一条回路，经过图中的每个结点恰好一次，若存在一条回路，经过图中的每个结点恰好一次，这条回路称作哈密尔顿回路。这条回路称作哈密尔顿回路。具有
15、哈密尔顿回路的图称作具有哈密尔顿回路的图称作哈密尔顿图哈密尔顿图。与欧拉图的情况不同，直到目前，人们还没有找与欧拉图的情况不同，直到目前，人们还没有找到哈密尔顿图的简单的充要条件，寻找充要条件到哈密尔顿图的简单的充要条件，寻找充要条件是图论中的一个难题。目前人们只找到一些判断是图论中的一个难题。目前人们只找到一些判断存在性的充分条件和一些必要条件，下面以无向存在性的充分条件和一些必要条件，下面以无向图为例加以说明。图为例加以说明。198 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图定理定理8.2.3 设无向图设无向图G=为哈密尔顿图，为哈密尔顿图，V1是是V的任意真子集，则的任意真子集，则
16、其中，其中，p(G-V1)为从为从G中删除中删除V1后所得图的连通分后所得图的连通分支数。支数。定理中给出的条件是必要的。因而对一个图来说，定理中给出的条件是必要的。因而对一个图来说，如果不满足这个必要条件，它一定不是哈密尔顿如果不满足这个必要条件，它一定不是哈密尔顿图。但是，满足这个条件的图不一定是哈密尔顿图。但是，满足这个条件的图不一定是哈密尔顿图。图。推论推论：有割点的图一定不是哈密尔顿图。：有割点的图一定不是哈密尔顿图。208 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图下面给出一些充分条件。下面给出一些充分条件。定理定理8.2.4 设设G是是n(n 3)阶无向简单图，若对于阶无向
17、简单图，若对于G中每一对不相邻的顶点中每一对不相邻的顶点u,v,均有均有 deg(u)+deg(v)n-1则则G中存在哈密尔顿通路。又若中存在哈密尔顿通路。又若 deg(u)+deg(v)n则则G中存在哈密尔顿回路，即中存在哈密尔顿回路，即G为哈密尔顿图。为哈密尔顿图。推论：设推论：设G是是n(n 3)阶无向简单图，若阶无向简单图，若G是哈密尔顿图。是哈密尔顿图。218 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图228 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图关于有向图中的哈密尔顿通路与回路有下面的结关于有向图中的哈密尔顿通路与回路有下面的结论。论。定理定理8.2.5 在在n(n
18、 2)阶有向图阶有向图D=中，如果中，如果略去所有有向边的方向，所得无向图中含生成子略去所有有向边的方向，所得无向图中含生成子图图kn,则则D中存在哈密尔顿通路。中存在哈密尔顿通路。推论推论 n(n 3)阶有向完全图都是哈密尔顿图。阶有向完全图都是哈密尔顿图。238 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图例：今有例：今有a,b,c,d,e,f,g 7个任，已知下列事实：个任，已知下列事实：a会讲英语；会讲英语；b会讲英语和汉语；会讲英语和汉语；c会讲英语、意大利语和俄语；会讲英语、意大利语和俄语；d会讲日语和汉语；会讲日语和汉语；e会讲德语和意大利语；会讲德语和意大利语；f会讲法语、
19、日语和俄语；会讲法语、日语和俄语；g会讲法语和德语。会讲法语和德语。问能否将这问能否将这7个人安排就坐圆桌旁，使得每个人都个人安排就坐圆桌旁，使得每个人都能与两边的人交谈？能与两边的人交谈？248 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图解：做无向图解：做无向图G=,V=a,b,c,d,e,f,g,E=(u,v)|u,v V且且u v且且u与与v有共同语言有共同语言，根据已知条，根据已知条件得件得G如下图所示：如下图所示：258 8.2.2 欧拉图与哈密尔顿图欧拉图与哈密尔顿图在图中，在图中，u与与v相邻当且仅当它们有共同语言。问题就变成相邻当且仅当它们有共同语言。问题就变成了图中是否
20、存在哈密尔顿回路了图中是否存在哈密尔顿回路(也即也即G为哈密尔顿图为哈密尔顿图)。不。不难看出难看出C=acegfdba为为G中的一条哈密尔顿回路，因而可以中的一条哈密尔顿回路，因而可以按按C中顶点顺序安排座次，这样，每个人都与两边的人有共中顶点顺序安排座次，这样，每个人都与两边的人有共同语言，因而能交谈。同语言，因而能交谈。268.3 平面图平面图在图的理论探讨和实际应用中，平面图都具有重在图的理论探讨和实际应用中，平面图都具有重要的意义。比如在现实生活中，常常要画一些图要的意义。比如在现实生活中，常常要画一些图形，希望边与边之间尽量减少相交的情况，例如形，希望边与边之间尽量减少相交的情况，
21、例如印刷线路板上的布线，交通道的设计等。印刷线路板上的布线，交通道的设计等。定义定义8.3.1 设设G=是一个无向图，如果能够是一个无向图，如果能够把把G的所有结点和边画在平面上，且使得任何两边的所有结点和边画在平面上，且使得任何两边除了端点外没有其它的交点，就称除了端点外没有其它的交点，就称G是一个是一个平面图平面图。画出的没有边交叉出现的图称为画出的没有边交叉出现的图称为G的一个的一个平面嵌入平面嵌入或或平面表示平面表示。无平面嵌入的图为。无平面嵌入的图为非平面图非平面图。278.3 平面图平面图(a)(b)288.3 平面图平面图(c)(d)298.3 平面图平面图定义定义8.3.2 设
22、设G是一个平面图，是一个平面图，G的边将所在的平的边将所在的平面划分成若干个区域，每个区域称为面划分成若干个区域，每个区域称为G的一个的一个面面。其中面积无限的区域称为其中面积无限的区域称为无限面无限面或外部面，面积或外部面，面积有限的区域称为内部面或有限的区域称为内部面或有限面有限面。包围每个面的。包围每个面的所有边构成的回路称为该面的所有边构成的回路称为该面的边界边界，边界的长度，边界的长度称为该面的称为该面的次数次数。面。面Ri的次数记作的次数记作deg(Ri),人们常人们常把外部面记成把外部面记成R0.308.3 平面图平面图318.3 平面图平面图定理定理8.3.1 在一个平面图在一
23、个平面图G中，所有面的次数之和中，所有面的次数之和为边数的为边数的2倍，即倍，即其中，其中，r为为G的面数，的面数，m为边数。为边数。关于平面图的平面嵌入，还应指出两点：关于平面图的平面嵌入，还应指出两点：(1)同一个平面图同一个平面图G，可以有不同形状的平面嵌入，可以有不同形状的平面嵌入，但它们都是与但它们都是与G同构的；同构的；(2)平面图平面图G的外部面，可以通过变换由的外部面，可以通过变换由G的任何面的任何面充当。充当。328.3 平面图平面图在上图中，在上图中，(b)(c)都是都是(a)的平面嵌入，它们的形状不的平面嵌入，它们的形状不同，但都与同，但都与(a)同构。同构。(b)中的有
24、限面中的有限面R22在在(c)中变成中变成了无限面了无限面R0,R00变成了变成了(c)中的中的R2。338.3 平面图平面图下面讨论连通平面图中顶点数，边数，面数之间下面讨论连通平面图中顶点数，边数，面数之间的关系。的关系。定理定理8.3.1 设设G为任意的连通的平面图，则为任意的连通的平面图，则 n-m+r=2其中，其中，n为为G的顶点数，的顶点数，m为边数，为边数，r为面数。为面数。注意，欧拉公式只对连通的平面图成立。注意，欧拉公式只对连通的平面图成立。推论推论 G是具有是具有k(k 2)个连通分支的平面图，则个连通分支的平面图，则 n-m+r=k+1其中，其中，n,m,r 分别是分别是G的阶数、边数和面数。的阶数、边数和面数。34