一些特殊的图

1、第8章 一些特殊的图 1 二部图 欧拉图 哈密尔顿图 平面图第8章 一些特殊的图10/2/2022 7:06 AM28.1二部图定义：若能将无向图G=(V,E)的顶点集V划分成两个子集V1和V2（V1V2 ）,使得G中任何一条边的两个端点一个属于V1,另一个属于V2，则称G为二部图。若V1中任一顶点与V2中任一顶点均有且仅有一条边相关联，则称此二 部图为完全二部图。10/2/2022 7:06 AM3定理： 一个无向图是二部图当且仅当G中无奇数长度的回路。10/2/2022 7:06 AM4匹配二部图G=(V,E)中, 若ME, 且M中任意两条边都没有公共顶点，则称M为G中的匹配。极大匹配 若

2、在M中再加入任何1条边就不是匹配了，则称为极大匹配。最大匹配 边数最多的极大匹配称为最大匹配 。最大匹配中边的个数称为匹配数。基本术语10/2/2022 7:06 AM5饱和点与非饱和点 属于匹配M的边的所有顶点称为关于M饱和点，否则称为M非饱和点。完美匹配 若G中的每个顶点都是M的饱和点，称M是G的完美匹配。完备匹配 设V1和V2是二部图G的互补顶点集，若G中的匹配M使得|M|=min|V1|,|V2|，称该匹配是完备匹配。10/2/2022 7:06 AM6Hall定理 相异性定理二部图G = (V1,V2 ,E )， |V1|V2| ，存在从V1到V2的完备匹配 当且仅当V1中任意k（=

3、1，2，|V1|）个顶点至少连接V2中的k个顶点。t 条件定理10/2/2022 7:06 AM7例：某中学有3个课外小组：物理组、化学组、生物组。今有张、王、李、赵、陈5名同学，若已知：(1)张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员；(2)张为物理组成员，王、李、赵为化学组成员，王、李、赵、陈为生物组成员；(3)张为物理组和化学组成员，王、李、赵、陈为生物组成员。问在以上3种情况下能否各选出3名不兼职的组长？ 10/2/2022 7:06 AM8解：设v1,v2,v3,v4,v5分别表示张、王、李、赵、陈。u1,u2,u3分别表示物理组、化学组、生物组。在3种情况下

4、作二部图分别记为G1,G2,G3，如图所示。10/2/2022 7:06 AM9练习：在下图所示的各图中，是二部图的为A。在二部图中存在完美匹配的是B，它们的匹配数是C。 10/2/2022 7:06 AM10分析无奇数长度回路的只有图(3)，(4)，(5)，因而它们都是二部图；也可根据定义，直接将两个顶点集找出，进而判断是否是二部图。一个图存在完美匹配的一个必要条件是具有偶数个顶点，只有图(4)具有偶数个顶点，并且它存在完美匹配，匹配数是3。 10/2/2022 7:06 AM118.2 欧拉图Konigsberg(哥尼斯堡)七桥问题问题：能否从河岸或小岛出发，通过每一座桥，而且仅仅通过一次

5、就回到原地。10/2/2022 7:06 AM12 Euler(欧拉)1736年对这个问题，给出了否定的回答。将河岸和小岛作为图的顶点，七座桥为边，即可构成一个无向图，问题化为图论中迹(每条边只走一次)的问题：定义欧拉通路（回路）与欧拉图： （，）是连通图，称经过图中所有边一次且仅一次的通路（回路）称为欧拉通路（欧拉回路）。 具有欧拉回路的图称为欧拉图。10/2/2022 7:06 AM13定理1（欧拉定理）：无向图存在欧拉通路的充要条件是：(1)图是连通图；(2)图中有零个或者两个奇数度顶点。若无奇数度顶点，则通路为回路；若有两个奇数度顶点，则它们是每条欧拉通路的端点。10/2/2022 7

6、:06 AM14证明： 必要性： 若存在欧拉通路，且没有度顶点，则每个顶点都有边关联，而边又全在欧拉通路上，故所有顶点都连通。 除了起点，终点外，欧拉通路每经过一个顶点，使顶点的度增加，故只有起点和终点才可能成为奇度顶点。据握手定理的推论，一个奇度顶点是不可能的（两个都不是或者两个都是）。 当无奇度顶点时，是欧拉回路。充分性： 若(1），(2)成立,构造欧拉通路或回路.10/2/2022 7:06 AM15L1: a, c, bL1+L2: a, d, b, a, c, bL2: a, d, b,a10/2/2022 7:06 AM16L1: a, c, bL1+L2: a, d, b, a,

7、 c, bL2: a, d, b,a欧拉通路10/2/2022 7:06 AM17说明： 哥尼斯堡七桥问题，由于四个顶点都是奇度的，不可能有欧拉通路。10/2/2022 7:06 AM18（1）（2）是欧拉图，（3）是半欧拉图10/2/2022 7:06 AM19图(4):欧拉图 图(5):不是欧拉图，亦无欧拉通路。10/2/2022 7:06 AM20例个顶点均为3度，不能一笔画出 应用与推广：一笔画图10/2/2022 7:06 AM21应用与推广：一笔画图 10/2/2022 7:06 AM22Hamilton(哈密顿)道路问题： 年发明的一种游戏。 在一个实心的正十二面体，20个顶点标

8、上世界著名大城市的名字，要求游戏者从某一城市出发，遍历各城市一次，最后回到原地。 这就是“绕行世界”问题。即找一条经过所有顶点（城市）一次且只一次的道路（回路）。8.3 哈密顿图10/2/2022 7:06 AM23（a）正十二面体 （b）哈密顿图 环游世界问题图示10/2/2022 7:06 AM24定义哈密顿路/回路： （，），经过图中所有顶点一次且只一次的通路（回路）称为哈密顿通路（回路）。 具有哈密顿回路的图称为哈密顿图。 不具有哈密顿回路但具有哈密顿通路的图称为半哈密顿图10/2/2022 7:06 AM25(1)是半哈密顿图: 存在哈密顿路，不存在哈密顿回路(2)为哈密顿图:存在哈

9、密顿回路(3)不是哈密顿图。10/2/2022 7:06 AM26哈密顿图存在的必要条件定理 设无向图G是哈密顿图，则对于顶点集的每一个真子集V1均有：p(GV1)| V1 |其中， p(G V1)为从G中删除V1(删除V1中各顶点及关联的边)后所得图的连通分支数。需注意，定理给出的条件是哈密顿图的必要条件，不是充分条件，有些图满足这个条件，但不是哈密顿图，例如，彼德森图。10/2/2022 7:06 AM27| V1 |=3,p(GV1)=4,故p(G- V1)| V1 |不成立。所以此图不是哈密尔顿图。例1:10/2/2022 7:06 AM28解：取V1 A1， A2 例2:10/2/2

10、022 7:06 AM29存在3个分支| V1 |=2,p(GV1)=3,故p(G V1)| V1 |不成立。所以此图不是哈密尔顿图。10/2/2022 7:06 AM30在彼德森图中删除任意一个或两个顶点，仍是连通的；例3:彼德森图10/2/2022 7:06 AM31删除3个顶点，最多只能得到有两个连通分支的子图；删除4个顶点，最多只能得到有3个连通分支的子图；删除5个和5个以上的顶点，余下子图的顶点数都不大于5，故必不能有5个以上的连通分支数，所以，满足p(G V1)| V1 | 。但此图是典型的非哈密尔顿图。例3:彼德森图10/2/2022 7:06 AM32练习8.13：已只知下列事

11、实：有7个人a,b,c,d,e,f,g，a：会讲英语b：会讲英语和华语c：会讲英语和意大利语和俄语d：会讲日语和华语e：会讲德语和意大利语f：会讲法语和日语和俄语g：会讲法语和德语如何安排座位，才能使每个人都能和他身边的两个人交谈？10/2/2022 7:06 AM33 G= V=a,b,c,d,e,f,gE=(u,v)|u,v属于V,u与v有共同语言则将7人排座在圆桌周围左右能交谈在图G中找哈密顿回路。10/2/2022 7:06 AM34回顾P185:8.210/2/2022 7:06 AM358.4 平面图定义平面图：一个图G如果能以这样的方式画在平面上：除顶点处外没有边交叉出现，则称G

12、为平面图。10/2/2022 7:06 AM3610/2/2022 7:06 AM37设G是一个连通的平面图，G的边将G所在的平面划分成若干个区域，每个区域称为G的一个面。面积无限的区域称为无限面或外部面，常记成R0。面积有限的区域称为有限面或内部面。包围每个面的所有边所构成的回路称为该面的边界。边界的长度称为该面的次数，R的次数记为deg(R)。10/2/2022 7:06 AM38R0的边界为：V1V2V3V4V1 deg (R0)=4R1的边界为：V1V2V3V4V1 deg (R1)=4R0的边界为：V1V2V3V6V3V4V1 deg (R0)=6R1的边界为：V1V2V3V4V5V

13、4V1 deg (R1)=610/2/2022 7:06 AM39R0的边界为：V1V2V2V3V6V3V5V4V1 deg (R0)=8R1的边界为：V1V2V3V4V1 deg (R1)=4R2的边界为：V4V3V5V4 deg (R1)=3R3的边界为：V2V2 deg (R3)=110/2/2022 7:06 AM40定理 在一个平面图G中，所有面的次数之和都等于边数m的2倍，即其中，r为面数。推论 在任何平图中度为奇数的面的个数是偶数。10/2/2022 7:06 AM41极大平面图定义8.8 设G为简单平面图，若在G的任意不相邻的顶点u，v之间加边(u，v)，所得图为非平面图，则称

14、G为极大平面图。 K1，K2，K3，K4，,K5-e(K5删除任意一条边)都是极大平面图。 定理 极大平面图是连通的。 定理 设G是n(n3)阶极大平面图，则G中不可能存在割点和桥。 定理 设G为n(n3)阶简单连通的平面图，G为极大平面图当且仅当G的每个面的次数均为3. 10/2/2022 7:06 AM42连通平面图的欧拉公式定理 设G为任意的连通的平面图，则有 n-m+r=2 成立。其中，n为G中顶点数， m为边数，r为面数。 (该定理中的公式称为欧拉公式。)推论1: 设G是简单连通平面图,顶点数n3时, 边数m 3(n-2)推论2: 设G是简单连通平面图,若每个平面由4条或4条以上边围

15、成, 则m 2(n-2).10/2/2022 7:06 AM43注意: 欧拉公式和推论1及推论2是判断一个图是否平面图的必要条件.如果一个图具备这些条件,不一定是平面图.m= 16, n=8 163*(8-2)但该图不是平面图.如果一个图不具备这些条件,一定不是平面图.10/2/2022 7:06 AM44利用欧拉公式及推论可证明K5不是平面图。K5有5个顶点，10条边， 则3(n-2)= 3(5-2)= 910，与推论1中 m 3(n-2)矛盾的， 因而K5不是平面图。10/2/2022 7:06 AM45利用欧拉公式及推论可证明K3,3不是平面图。若K3,3是平面图，则每个面的次数至少为4

16、，由推论2： m 2(n-2)因而有9 2(6-2)=8，这是矛盾的，因而K3,3不是平面图。10/2/2022 7:06 AM46同胚如果两个图G1和G2同构，或经过反复插入或消去2度顶点后同构，则称G1与G2同胚。插入消去10/2/2022 7:06 AM47同胚著有General Topology一书的数学家John L. Kelley曾说：拓扑学家是不知道甜甜圈和咖啡杯的分别的人。10/2/2022 7:06 AM48平面图的收缩设e是无向图G的一条边. 在G中收缩边e, 由以下方法给出:当e=(u,u)是环时,删除边e; 当e=(u,v)是非环边时,删除边e, 用新的顶点w取代u,v

17、, 并使w除边e外继承一切与u、与v的边关联. 在G中收缩边e得到的图Ge用表示. 49 平面图收缩边e的例子50收缩图定义设G是无向图，在G中收缩边e称为G的一个初等收缩。若G经一系列的初等收缩得到图H，则称H是G的一个收缩图或说图G可收到图H。1930年波兰数学家库拉托夫斯基(Kuratowski)给出了平面图的一个判别准则. 51库拉图斯基定理1930一个图是平面图当且仅当它不含与K5同胚的子图，也不含与K3,3同胚子图。 瓦格那(K.Wagner)定理1937一个无向图是平面图当且仅当它不含有可收缩到K5或K3,3的子图。10/2/2022 7:06 AM5210/2/2022 7:0

18、6 AM53练习8.19：证明如下所示图G是哈密尔顿图，但不是平面图。 解：图中afbdcea为哈密尔顿回路，见红边所示，所以，该图为哈密尔顿图。 将图中边d，e，e，f，f，d三条去掉，所得图为原来图的子图，它为 K3，3 ，可取V1=a，b，c，V2=d，e，f，由库拉图斯基定理可知，该图不是平面图。54练习：8.23558.23 解：6 个顶点11条边的非平面图。（子图与K3,3或K5同胚）K3,3 ：6个顶点9条边K5 ： 5个顶点10条边 K3,3加2条边的图:56K5加1个顶点，1条边的图：57对偶图 与着色设平面图G，有r个面，v个顶点，e条边，构造G的对偶图G*如下：1.在G的每个面中任取一点作为G*的顶点。2.对G中每条边，如果边是两个面的公共边界，则连接两个面中对应顶点所得的边为G*的边；如果G中边只是一个面的边界，则以该面中顶点做与此边相交的环，该环亦为 G*的边。这样所得的图为G的对偶图.10/2/2022 7:06 AM5810/2/2022 7:06 AM5910/2/2022 7:06 AM60 图中，两个蓝边图是同构的，但它们的对偶图(红边图