离散数学几种特殊的图

离散数学几种特殊的图第1页/共35页2哥尼斯堡七桥问题哥尼斯堡城（现在俄罗斯）在18世纪属东普鲁士，它位于普雷格尔（Pregel）河畔，河中有两个岛，通过七座桥彼此相联，如下图：

。。。。ABCD第2页/共35页3内容提要

8.1二部图

8.2欧拉图与哈密尔顿图

8.3平面图

第3页/共35页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=<V,E>,如下图所示。第4页/共35页58.1二部图由图显而易见，分配a1去完成b1,a2去完成B2,a3去完成b4，a4去完成B3就能满足要求。在此图中，a1,a2,a3,a4彼此不相邻，b1,b2,b3,b4也彼此不相邻。像这样的图，称它为二部图。第5页/共35页68.1二部图定义8.1.1

若能将无向图的顶点集V分成两个子集V1和V2(V1V2=),使得G中任何一条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图（或称偶图、双图、二分图），V1,V2称为互补顶点子集.

若G是二部图，也可将G记为G=<V1,V2,E>。又若V1中任一顶点与V2中任一顶点均有且仅有一条边相关联，则称二部图G为完全二部图。若|V1|=r,|V2|=s,则记完全二部图为Kr,s第6页/共35页78.1二部图

注:在完全二部图Kr,s中，它的顶点数n=r+s，它的边数m=rs.定理8.1.1一个无向图G=<V,E>是二部图当且仅当G中无奇数长度的回路。第7页/共35页8

如图所示各图都是二部图，其中，(1)，(2)，(3)为K6的子图，(3)为完全二部图K3,3，常将K3,3画成与其同构的(5)的形式，K3,3是下文中经常遇到的图。(4)是K5的子图，它是完全二部图K2,3，K2,3常画成(6)的形式。

注意，n阶零图为二部图。

第8页/共35页98.2欧拉图与哈密尔顿图引例：哥尼斯堡七桥问题

如何不重复地走完七桥后回到起点？

。。。。ABCD第9页/共35页108.2欧拉图与哈密尔顿图一、欧拉图定义8.2.1

给定无孤立结点图G=<V,E>，若存在一条通路，经过图中每条边一次且仅一次，该通路称作欧拉通路；若G中欧拉通路又是回路，则称它为G中的欧拉回路；具有欧拉回路的图称为欧拉图。注意：只有欧拉通路无欧拉回路的图不是欧拉图。第10页/共35页118.2欧拉图与哈密尔顿图(a)无欧拉通路(b)无欧拉回路(c)是欧拉图第11页/共35页128.2欧拉图与哈密尔顿图定理8.2.1

无向图G具有一条欧拉通路，当且仅当G是连通的，且有零个或两个奇数度结点。证明必要性设G具有欧拉通路，即有点边序列v0e1v1e2v2…eiviei+1…ekvk,其中结点可能重复出现，但边不重复，因为欧拉通路经过所有图G的结点，故图G是连通的。对任意一个不是端点（始点和终点）的结点vi,在欧拉通路中每当vi出现一次，必关联两条边，故vi虽可重复出现，但deg(vi)必是偶数。对于端点，若v0=vk,则d(v0)为偶数，即G中无奇数度结点；若端点v0与vk不同，则d(v0)为奇数，d(vk)为奇数，G中就有两个奇数度结点。第12页/共35页138.2欧拉图与哈密尔顿图充分性若图G连通，有零个或两个奇数度结点，我们构造一条欧拉通路如下：

(1)若有两个奇数度结点，则从其中的一个结点考试构造一条迹，即从v0出发经关联边e1“进入”v1,若deg(v1)为偶数，则可由v1再经关联边e2进入v2,如此进行下去，每边仅取一次。由于G是连通的，故必可到达另一奇数度结点停下，得到一条迹L:v0e1v1e2v2…eiviei+1…ekvk.若G中没有奇数度结点则从任一结点v0出发，用上述方法必可回到结点v0,得到上述一条闭迹L1.第13页/共35页148.2欧拉图与哈密尔顿图(2)若L1通过了G的所有边，则L1就是欧拉通路。(3)若G中去掉L1后得到子图G’,则G’中每个结点度数为偶数，因为原来的图是连通的，故L1与G’至少有一个结点vi重合，在G’中由vi出发重复(1)的方法，得到闭迹L2.(4)当L1与L2组合在一起，如果恰是G,即得欧拉通路，否则重复(3)可得到闭迹L3,依此类推直到得到一条经过图G中所有边的欧拉通路。第14页/共35页158.2欧拉图与哈密尔顿图

由于有了欧拉回路和欧拉通路的判别准则，因此哥尼斯堡七桥问题立即有了确切的否定答案，因为从上图中可以看到deg(A)=5,deg(B)=deg(C)=deg(D)=3,故欧拉回路必不存在。

。。。。ABCD第15页/共35页168.2欧拉图与哈密尔顿图欧拉通路和欧拉回路的概念，可以推广到有向图中去。定义8.2.2

给定有向图G,通过图中每边一次且仅一次的一条单向通路(回路),称作单向欧拉通路(回路)。定理8.2.2

有向图G具有一条单向欧拉回路，当且仅当是连通的，且每个结点入度等于出度。一个有向图G具有单向欧拉通路，当且仅当它是连通的，而且除两个结点之外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度大1，另一个结点的入度比出度小1。第16页/共35页178.2欧拉图与哈密尔顿图二、哈密尔顿图1859年爱尔兰数学家威廉.哈密顿首先提出在正十二面体上的一个数学游戏，即能否在如下所示的图中找到一条基本(初级)回路(或路径)，使它经过每个顶点恰好一次。第17页/共35页188.2欧拉图与哈密尔顿图

由于他将每个顶点看作一个城市，将两个顶点之间的边看作交通线，于是他提出的问题称为“周游世界问题”。对于任何一个连通图，都可以提出这样的问题，即在图中是否存在经过所有顶点一次且仅一次的回路或通路。将这样的初级通路、回路分别称为哈密尔顿通路、回路。第18页/共35页198.2欧拉图与哈密尔顿图定义8.2.3

给定图G,若存在一条通路经过图中的每个结点恰好一次，这条通路称作哈密尔顿路。若存在一条回路，经过图中的每个结点恰好一次，这条回路称作哈密尔顿回路。具有哈密尔顿回路的图称作哈密尔顿图。与欧拉图的情况不同，直到目前，人们还没有找到哈密尔顿图的简单的充要条件，寻找充要条件是图论中的一个难题。目前人们只找到一些判断存在性的充分条件和一些必要条件，下面以无向图为例加以说明。第19页/共35页208.2欧拉图与哈密尔顿图定理8.2.3

设无向图G=<V,E>为哈密尔顿图，V1是V的任意真子集，则其中，p(G-V1)为从G中删除V1后所得图的连通分支数。定理中给出的条件是必要的。因而对一个图来说，如果不满足这个必要条件，它一定不是哈密尔顿图。但是，满足这个条件的图不一定是哈密尔顿图。推论：有割点的图一定不是哈密尔顿图。第20页/共35页218.2欧拉图与哈密尔顿图下面给出一些充分条件。定理8.2.4

设G是n(n3)阶无向简单图，若对于G中每一对不相邻的顶点u,v,均有

deg(u)+deg(v)n-1则G中存在哈密尔顿通路。又若

deg(u)+deg(v)n则G中存在哈密尔顿回路，即G为哈密尔顿图。推论：设G是n(n3)阶无向简单图，若G是哈密尔顿图。第21页/共35页228.2欧拉图与哈密尔顿图第22页/共35页238.2欧拉图与哈密尔顿图关于有向图中的哈密尔顿通路与回路有下面的结论。定理8.2.5

在n(n2)阶有向图D=<V,E>中，如果略去所有有向边的方向，所得无向图中含生成子图kn,则D中存在哈密尔顿通路。推论

n(n3)阶有向完全图都是哈密尔顿图。第23页/共35页248.2欧拉图与哈密尔顿图例：今有a,b,c,d,e,f,g7个任，已知下列事实：

a会讲英语；

b会讲英语和汉语；

c会讲英语、意大利语和俄语；

d会讲日语和汉语；

e会讲德语和意大利语；

f会讲法语、日语和俄语；

g会讲法语和德语。问能否将这7个人安排就坐圆桌旁，使得每个人都能与两边的人交谈？第24页/共35页258.2欧拉图与哈密尔顿图解：做无向图G=<V,E>,V={a,b,c,d,e,f,g},E={(u,v)|u,vV且uv且u与v有共同语言}，根据已知条件得G如下图所示：第25页/共35页268.2欧拉图与哈密尔顿图在图中，u与v相邻当且仅当它们有共同语言。问题就变成了图中是否存在哈密尔顿回路(也即G为哈密尔顿图)。不难看出C=acegfdba为G中的一条哈密尔顿回路，因而可以按C中顶点顺序安排座次，这样，每个人都与两边的人有共同语言，因而能交谈。第26页/共35页278.3平面图在图的理论探讨和实际应用中，平面图都具有重要的意义。比如在现实生活中，常常要画一些图形，希望边与边之间尽量减少相交的情况，例如印刷线路板上的布线，交通道的设计等。定义8.3.1

设G=<V,E>是一个无向图，如果能够把G的所有结点和边画在平面上，且使得任何两边除了端点外没有其它的交点，就称G是一个平面图。画出的没有边交叉出现的图称为G的一个平面嵌入或平面表示。无平面嵌入的图为非平面图。第27页/共35页288.3平面图(a)(b)第28页/共35页298.3平面图(c)(d)第29页/共35页308.3平面图定义8.3.2

设G是一个平面图，G的边将所在的平面划分成若干个区域，每个区域称为G的一个面。其中面积无限的区域称为无限面或外部面，面积有限的区域称为内部面或有限面。包围每个面的所有边构成的回路称为该面的边界，边界的长度称为该面的次数。面Ri的次数记作deg(Ri),人们常把外部面记成R0.第30页/共35页318.3平面图第31页/共35页328.3平面图定理8.3.1

在一个平面图G中，所有面的次数之和为边数的2倍，即其中，r为G的面数，m为边数。关于平面图的平面嵌入，还应指出两点：(1)同一个平面图G，可以有不同形状的平面嵌入，但它们都是与G同构的；(2)平面图G的外部面，可以通过变换由G的任何面充当。第32页/共35页338.3平面图在上图中，(b)(c)都是(a)的平面嵌入，它们的形状不同，但都与(a)同构。(b)中的有限面R22在(c)中变成了无限面R0,