CH8 一些特殊的图.ppt

离散数学第8章 一些特殊的图 *2• 二部图 • 欧拉图 • 哈密尔顿图 • 平面图第8章 一些特殊的图*38.1二部图 ¯ 定义：若能将无向图G=(V,E)的顶点集V划分成两 个子集V1和V2（V1∩V2＝  ）,使得G中任何一条边 的两个端点一个属于V1,另一个属于V2，则称G为二 部图¯ 若V1中任一顶点与V2中任一顶点均有且仅有一条边 相关联，则称此二 部图为完全二部图4定理： 一个无向图是二部图当且仅当G中无奇 数长度的回路 *5匹配 二部图G=(V,E)中, 若ME, 且 M中任意两条边都没有公共顶点，则 称M为G中的匹配极大匹配 若在M中再加入任何1条 边就不是匹配了，则称为极大匹配最大匹配 边数最多的极大匹配称为 最大匹配 最大匹配中边的个数称 为匹配数 基本术语*6饱和点与非饱和点 属于匹配M的 边的所有顶点称为关于M饱和点， 否则称为M非饱和点完美匹配 若G中的每个顶点都是 M的饱和点，称M是G的完美匹配 完备匹配 设V1和V2是二部图G的 互补顶点集，若G中的匹配M使得 |M|=min{|V1|,|V2|}，称该匹配是完 备匹配。

7Hall定理 相异性定理 二部图G = (V1,V2 ,E )， |V1|≤|V2| ，存在从V1 到V2的完备匹配 当且仅当V1中任意k（=1，2 ，…|V1|）个顶点至少连接V2中的k个顶点t 条件定理*8例：某中学有3个课外小组：物理组、化学组、生物 组今有张、王、李、赵、陈5名同学，若已知： (1)张、王为物理组成员，张、李、赵为化学组成员 ，李、赵、陈为生物组成员； (2)张为物理组成员，王、李、赵为化学组成员，王 、李、赵、陈为生物组成员； (3)张为物理组和化学组成员，王、李、赵、陈为生 物组成员问在以上3种情况下能否各选出3名不兼职的组长？ *9解：设v1,v2,v3,v4,v5分别表示张、王、李、赵、陈 u1,u2,u3分别表示物理组、化学组、生物组在3种情 况下作二部图分别记为G1,G2,G3，如图所示10：在下图所示的各图中，是二部图的为 A 在二部图 中存在完美匹配的是 B ，它们的匹配数是 C *11分析 无奇数长度回路的只有图(3)，(4)，(5) ，因而它们都是二部图；也可根据定义，直接 将两个顶点集找出，进而判断是否是二部图。

一个图存在完美匹配的一个必要条件是具有偶 数个顶点，只有图(4)具有偶数个顶点，并且它 存在完美匹配，匹配数是3128.2 欧拉图Konigsberg(哥尼斯堡)七桥问题问题：能否从河岸或小岛出发，通过每一座桥， 而且仅仅通过一次就回到原地13Euler(欧拉)1736年对这个问题，给出了否 定的回答将河岸和小岛作为图的顶点，七座 桥为边，即可构成一个无向图，问题化为图论 中迹(每条边只走一次)的问题：[定义]欧拉通路（回路）与欧拉图：Ｇ＝（Ｖ，Ｅ）是连通图，称经过图中所 有边一次且仅一次的通路（回路）称为欧拉通 路（欧拉回路）具有欧拉回路的图称为欧拉图14[定理1]（欧拉定理）：无向图存在欧拉通路的充要条件是： (1)图是连通图； (2)图中有零个或者两个奇数度顶点若无奇数度顶点，则通路为回路；若有两个奇数 度顶点，则它们是每条欧拉通路的端点15证明：必要性：若存在欧拉通路，且没有０度顶点，则每个顶 点都有边关联，而边又全在欧拉通路上，故所有顶 点都连通除了起点，终点外，欧拉通路每经过一个顶点 ，使顶点的度增加２，故只有起点和终点才可能成 为奇度顶点据握手定理的推论，一个奇度顶点是 不可能的（两个都不是或者两个都是）。

当无奇度顶点时，是欧拉回路充分性：若(1），(2)成立,构造欧拉通路或回路 .L1: a, c, b*16L1+L2: a, d, b, a, c, bL2: a, d, b,aL1: a, c, b*17L1+L2: a, d, b, a, c, bL2: a, d, b,a欧拉通路*18说明：哥尼斯堡七桥问题，由于四个顶点都是 奇度的，不可能有欧拉通路19（1）（2）是欧拉图，（3）是半欧拉图*20图(4):欧拉图图(5):不是欧拉图，亦无欧拉通路21例８个顶点均为 3度，不能一 笔画出应用与推广：一笔画图一笔画图应用与推广：一笔画图 *22*23Hamilton(哈密顿)道路问题：１８５９年发明的一种游戏在一个实心的正十二面体，20个顶点标上 世界著名大城市的名字，要求游戏者从某一城 市出发，遍历各城市一次，最后回到原地这就是“绕行世界”问题即找一条经过 所有顶点（城市）一次且只一次的道路（回路 ）8.3 哈密顿图*24（a）正十二面体 （b）哈密顿图环游世界问题图示*25[定义]哈密顿路/回路：Ｇ＝（Ｖ，Ｅ），经过图中所有顶点一次 且只一次的通路（回路）称为哈密顿通路（回 路）。

具有哈密顿回路的图称为哈密顿图不具有哈密顿回路但具有哈密顿通路的图 称为半哈密顿图*26(1)是半哈密顿图: 存在哈密顿路，不存在哈密顿 回路 (2)为哈密顿图:存在哈密顿回路 (3)不是哈密顿图27哈密顿图存在的必要条件定理 设无向图G是哈密顿图，则对于顶点集的每一 个真子集V1均有：p(G－V1)| V1 |其中， p(G－ V1)为从G中删除V1(删除V1中各顶点及 关联的边)后所得图的连通分支数需注意，定理给出的条件是哈密顿图的必要条件，不 是充分条件，有些图满足这个条件，但不是哈密顿图 ，例如，彼德森图28| V1 |=3,p(G－V1)=4,故p(G- V1)| V1 | 不成立所以此图不是哈密尔顿图例1:*29解：取V1 ＝｛A1， A2 ｝例2:*30存在3个分支| V1 |=2,p(G－V1)=3,故p(G－ V1)| V1 |不 成立所以此图不是哈密尔顿图31在彼德森图中删除任意一个或两个顶点，仍是连通的；例3:彼德森图*32删除3个顶点，最多只能得到有两个连通分支的子图；删除4个顶点，最多只能得到有3个连通分支的子图；删除5个和5个以上的顶点，余下子图的顶点数都不大于5 ，故必不能有5个以上的连通分支数，所以，满足p(G－ V1)| V1 | 。

但此图是典型的非哈密尔顿图例3:彼德森图练习8.13：已只知下列事实：有7个人 a,b,c,d,e,f,g，a：会讲英语b：会讲英语和华语c：会讲英语和意大利语和俄语d：会讲日语和华语e：会讲德语和意大利语f：会讲法语和日语和俄语g：会讲法语和德语如何安排座位，才能使每个人都能和他身边 的两个人交谈？*33G= V={a,b,c,d,e,f,g}E={(u,v)|u,v属于V,u与v有共同语言}则将7人排座在圆桌周围左右能交谈在图G中找哈密顿回路34回顾P185:8.2*35*368.4 平面图[定义]平面图： 一个图G如果能以这样的方式画在平面上：除 顶点处外没有边交叉出现，则称G为平面图37*38v 设G是一个连通的平面图，G的边将G所在 的平面划分成若干个区域，每个区域称为G 的一个面 v 面积无限的区域称为无限面或外部面，常 记成R0 v 面积有限的区域称为有限面或内部面 v 包围每个面的所有边所构成的回路称为该 面的边界 v 边界的长度称为该面的次数，R的次数记为 deg(R)39R0的边界为：V1V2V3V4V1 deg (R0)=4R1的边界为：V1V2V3V4V1 deg (R1)=4R0的边界为：V1V2V3V6V3V4V1 deg (R0)=6R1的边界为：V1V2V3V4V5V4V1 deg (R1)=6*40R0的边界为：V1V2V2V3V6V3V5V4V1 deg (R0)=8R1的边界为：V1V2V3V4V1 deg (R1)=4 R2的边界为：V4V3V5V4 deg (R1)=3 R3的边界为：V2V2 deg (R3)=1*41定理 在一个平面图G中，所有面的次数之和 都等于边数m的2倍，即其中，r为面数。

推论 在任何平图中度为奇数的面的个数是 偶数极大平面图定义8.8 设G为简单平面图，若在G的任意不相 邻的顶点u，v之间加边(u，v)，所得图为非平 面图，则称G为极大平面图K1，K2，K3，K4，,K5-e(K5删除任意一条边)都是极大 平面图定理 极大平面图是连通的 定理 设G是n(n≥3)阶极大平面图，则G中不可能 存在割点和桥 定理 设G为n(n≥3)阶简单连通的平面图，G为极 大平面图当且仅当G的每个面的次数均为3. *42*43连通平面图的欧拉公式 定理 设G为任意的连通的平面图，则有n-m+r=2 成立其中，n为G中顶点数， m为边数，r为面数 (该定理中的公式称为欧拉公式)推论1: 设G是简单连通平面图,顶点数n3时, 边 数m 3(n-2)推论2: 设G是简单连通平面图,若每个平面由4条 或4条以上边围成, 则m 2(n-2).*44注意: 欧拉公式和推论1及推论2是判断一个图是 否平面图的必要条件.如果一个图具备这些条件,不一定是平面图.m= 16, n=8 16<3*(8-2)但该图不是平面图.如果一个图不具备这些条件, 一定不是平面图.*45利用欧拉公式及推论可证明K5 不是平面图。

K5有5个顶点，10条边， 则3(n-2)= 3(5-2)= 9<10， 与推论1中 m  3(n-2)矛盾的 ， 因而K5不是平面图46利用欧拉公式及推论可证明 K3,3不是平面图若K3,3是平面图，则每个面的 次数至少为4，由推论2： m 2(n-2)因而有9  2(6-2)=8， 这是矛盾的，因而K3,3不是平 面图47同胚 如果两个图G1和G2同构，或经过反复插入或消 去2度顶点后同构，则称G1与G2同胚插入消去同胚著有General Topology一书的 数学家John L. Kelley曾说：拓扑 学家是不知道甜 甜圈和咖啡杯的 分别的人48平面图的收缩设e是无向图G的一条边. 在G中收缩边e, 由 以下方法给出:当e=(u,u)是环时,删除边e; 当e=(u,v)是非环边时,删除边e, 用新的顶点 w取代u,v, 并使w除边e外继承一切与u、与v的边关联. 在G中收缩边e得到的图Ge用表 示. 平面图收缩边e的例子收缩图定义设G是无向图，在G中收缩边e称为G的一 个初等收缩若G经一系列的初等收缩得到 图H，则称H是G的一个收缩图或说图G可收 到图H。

1930年波兰数学家库拉托夫斯基 (Kuratowski)给出了平面图的一个判别准则 . *52库拉图斯基定理1930 一个图是平面图当且仅当它不含与K5同胚的子图 ，也不含与K3,3同胚子图瓦格那(K.Wagner)定理1937 一个无向图是平面图当且仅当它不含有可收缩到 K5或K3,3的子图53练习8.19：证明如下所示图G是哈密尔顿图，但不是平面图 解： 图中afbdcea为哈密尔顿回路，见红边所示，所以，该图为 哈密尔顿图将图中边{d，e} ，{e，f}，{f，d} 三条去掉，所得图为原来 图的子图，它为 K3，3 ，可取V1={a，b，c}，V2={d，e，f} ，由库拉图斯基定理可知，该图不是平面图练习：8.238.23 解： 6 个顶点11条边的非平面图子图与K3,3或K5同胚） K3,3 ：6个顶点9条边 K5 ： 5个顶点10条边 K3,3加2条边的图:。