离散数学几种特殊的图.pptx

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