第10章 一些特殊的图

1、1 10.1 欧拉图10.2 哈密尔顿图10.3 平面图10.4 二部图 第10章 几种典型图几种典型图 一、Euler图哥尼斯堡七桥问题：无向图的欧拉通路、欧拉图（即一笔画问题）经过图中每条边一次且仅一次并且行遍图中每个顶点的通路(回路),称为欧拉通路或欧拉迹(欧拉回路或欧拉闭迹).有欧拉通路的图称半欧拉图;存在欧拉回路的图,称为欧拉图.定理定理 无向图无向图G具有具有欧拉通路欧拉通路,当且仅当当且仅当G是连通图且是连通图且有零个或两个奇度顶点有零个或两个奇度顶点.若若无奇度顶点无奇度顶点,则通路则通路为回路为回路;若若有两有两个奇度顶点个奇度顶点,则它们是每条则它们是每条欧拉通路欧拉通路的

2、端点的端点.推论推论 无向图无向图G为欧拉图为欧拉图(具有欧拉回路具有欧拉回路)当且仅当当且仅当G是连通的是连通的,且且G中无奇度顶中无奇度顶点点. (1)、 (2)不是半欧拉图,也不 是欧拉图.(3)是半欧拉图，但不是欧拉图； (4) 是欧拉图.例是欧拉图；不是欧拉图，但存在欧拉通路；即不是欧拉图，也不存在欧拉通路。例(蚂蚁比赛问题)甲、乙两只蚂蚁分别位于如下图中的结点a，b处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点c处。如果它们的速度相同，问谁先到达目的地？2.一笔画问题Fleury算法 设G是欧拉图。（1）任选G的一个顶点0为起点，并

3、设零条边的通路为0=0。（2）设已选好的简单通路为i=0e11e22eii， 则按下述方法从Ee1,e2,，ei中选取边 ei+1： （i）ei+1与i关联； （ii）除非没有别的边可选择,否则ei+1不是 Gi=Ge1，e2，ei的割边（桥）。 当第2步不能继续进行时（所有的边已走遍）, 算法终止。 有向图的Euler图给定给定G是一个无孤立结点的有向图，是一个无孤立结点的有向图，若存在一条若存在一条单向通路单向通路(回路回路)，经过，经过图中每边一次且仅仅一次，则称此图中每边一次且仅仅一次，则称此单向通路单向通路(回路回路)为该图的一条单向为该图的一条单向欧拉通路欧拉通路(回路回路)。具有

4、单向欧拉回。具有单向欧拉回路的图称为路的图称为欧拉图欧拉图。定理定理 一个有向图一个有向图D具有欧拉通路具有欧拉通路,当且仅当当且仅当D是连通是连通的的,且除了两且除了两个顶点外个顶点外,其余顶点的其余顶点的入度均等入度均等于出度于出度.这两个特殊的顶点中这两个特殊的顶点中,一一个顶点的个顶点的入度比出度大入度比出度大另一另一个顶点的个顶点的入度比出度小入度比出度小1.有向图的Euler图推论 一个有向图D是欧拉图(具有欧拉回路),当且仅当D是连通的,且所有顶点的入度等于出度.只具欧拉通路,无欧拉回路的图不是欧拉图.(1)既无欧拉回路,也无欧拉通路.(2)中存在欧拉通路,但无欧拉回路.(3)中

5、存在欧拉回路.v(1)既无欧拉回路,也无欧拉通路.v(2)中存在欧拉通路,但无欧拉回路.v(3)中存在欧拉回路.下面是有向欧拉图的一个典型应用。例10.1.2 计算机鼓轮设计问题设计旋转鼓轮，要将鼓轮表面分成16个扇区，如图（a）所示，每块扇区用导体（阴影区）或绝缘体（空白区）制成，如图(b）所示，四个触点a、b、c和d与扇区接触时，接触导体输出1，接触绝缘体输出0。鼓轮顺时针旋转，触点每转过一个扇区就输出一个二进制信号。问鼓轮上的16个扇区应如何安排导体或绝缘体，使得鼓轮旋转一周，触点输出一组不同的二进制信号？ABCDABCD (a) (b) (c)18 10.1 欧拉图10.2 哈密尔顿图

6、10.3 平面图10.4 二部图 第10章 几种典型图几种典型图 哈密尔顿图哈密尔顿通路(回路)、哈密尔顿图经过图中每个顶点一次且仅一次的通路(回路)称为哈密尔顿通路(回路).存在哈密尔顿回路的图称为哈密尔顿图.图中 (1), (3),不是哈密尔顿图,(2) 为哈密尔顿图. 是不是哈密尔顿图?至今没有哈密尔顿图判定的充分必要条件哈密尔顿图的判定定理(必要条件1) 设无向图G=是哈密尔顿图,V1是V的任意的非空子集, p(G-V1)V1.其中, p(G-V1)为从G中删除V1(删除V1中各顶点及关联的边)后所得图的连通分支数.证明:设C为G中的一条哈密尔顿回路.(1)若V1中的顶点在C上彼此相邻

7、,则 p(C-V1)=1 V1 (2)设V1中的顶点在C上存在r(2r V1)个互不相邻,则 p(C-V1)= rV1 一般说来,V1中的顶点在C上既有相邻的,又有不相邻的,因而总有 p(C-V1) V1.又因为C是G的生成子图,故 p(G-V1) p(C-V1) V1. (1)图不是哈密尔顿图. (3) 图也不是哈密尔顿图.例在图中，虽然对任意的结点集合V1 ，都满足p(G-V1)|V1|，但它仍然不是哈密尔顿图。定理(充分条件1)设G是简单无向图。如果对任意两个不相邻的结点u，vV，均有：deg(u)+deg(v)|V|-1，则G中存在哈密尔顿通路；如果对任意两个不相邻的结点u，vV，均有

8、：deg(u)+deg(v)|V|，则G中存在哈密尔顿回路，即G是哈密尔顿图。例在图中，任意两个结点的度数之和为4，结点数为6，即有46，但它仍然是哈密尔顿图。定理6. G有n个顶点，m条边，如果 ，则G是哈密尔顿图。证明.任取不相邻的两个顶点u，vG，G中去掉u，v后导出子图G,G有n2个顶点，至多 条边.U,v到G的边数有 D(u)+D(v)n.由充分条件1得，G是哈密尔顿图。21mn3n62 （ ）2n2(n2)(nC23)2n2n3n6(n2)(nmCn2223)v推论 n阶简单无向图G中， n2,任意顶点的度数大于等于n/2，则G有哈密尔顿回路。充分条件2完全图Kn，n2，是哈密尔顿

9、图。归纳可证。定理 在n(n2)阶有向图D=中,如果所有有向边均用无向边代替,所得无向图中含生成子图Kn,则有向图D中存在哈密尔顿通路.推论 n(n3)阶有向完全图为哈密尔顿图.例:考虑在七天内安排七门课的考试,使得同一位教师所任的两门课程考试不排在连续的两天中,证明如果没有教师担任多于四门课程,则符合上述要求的考试安排总是可能的.证明: 设G为具有七个节点的图，每个节点对应于一门课程考试，如果这两个节点对应的考试是不同教师担任的，那么这两个节点间有一条边，因为每个教师所任课程数不超过4，故每个节点的度数至少是3，任两个节点的度数和至少为6，故总是包含一条汉密尔顿路，它对应于一个七门考试课的一

10、个适当的安排。37 10.1 欧拉图10.2 哈密尔顿图10.3 平面图10.4 二部图 第10章 几种典型图几种典型图 平面图一个图G如果能以这样的方式画在平面上;除顶点处外没有边交叉出现,则称G为平面图.画出的没有边交叉出现的图称为G的一个平面嵌入或G的一个平图.图中,(2)是(1)(K4)的平面嵌入,所以(1)是平面图. (2)是平面图. (3),(5)都不是平面图,即K5和K3,3都不是平面图.平面图中的一些概念设G是一个连通的平面图(指G的某个平面嵌入),G的边将G所在的平面划分成若干个区域,每个区域称为G的一个面.其中面积无限的区域称为无限面或外部面,常记成R0.包围每个面的所有边

11、所构成的回路称为该面的边界,边界的长度称为该面的次数,R的次数记为deg(R).对于非连通的平面图G有k(k2)个连通分支,则G的无限面R0的边界由k个回路围成.图(1)所示为连通的平面图,共有3个面R0,R1,R2.R1的边界为回路v1v3v4v1,deg(R1)=3.R2的边界为回路v1v2v3v1,deg(R2)=3.R0的边界为复杂回路v1v4v5v6v5v4v3v2v1,deg(R0)=10.例abcdefghijklmR1R2R3R4R0图(2)与(3)都是(1)的平面嵌入,它们都与(1)同构。图(2),deg(R0)=3;图(3),deg(R0)=4.定理 在一个平面图G中,所有

12、面的次数之和都等于边数n的2倍, 即(r为面数) 1deg()2riiRm极大平面图、极小非平面图设G为一个简单平面图,如果在G中任意不相邻的两个顶点之间再加一条边,所得图为非平面图,则称G为极大平面图.若在非平面图G中任意删除一条边,所得图为平面图,则称G为极小非平面图.例K5, K3,3是极小非平面图， K5任意删除一条边后所得图是极大平面图性质 极大平面图有以下性质;v (1)极大平面图是连通的;v (2)任何n(n3)阶极大平面图中,每个面的次数均为3.v (3)任何n(n4)阶极大平面图G中,均有(G)3.欧拉公式设G为任意的连通的平面图,则有 n-m+r2成立.其中,n为G中顶点数

13、,m为边数,r为面数.证明证明 对边数m作归纳法.v (1)m0时,G为孤立点,此时n1,r1,结论自然成立.v (2)设mk-1(k1)时结论成立,要证明mk时结论成立.证明v首先,若G为树,任取一树叶v并删除它,得GG-v, G中有nn-1个顶点mm-1条边,rr,由归纳假设有下式成立; n-m+r2,即 (n-1)-(m-1)+r2,整理后得 n-m+r2. 证明v其次,G不是树,证明则G中必有初级回路.设C为一初级回路,e在C上.令GG-e,由于e在C上,所以,G仍连通,在G中,nm,mm-1,rr-1,利用归纳假设可得 n-m+r2. 欧拉公式的推广v对于任意的p(p2)个连通分支的

14、平面图G,有 n-m+rp+1成立.定理v设G是连通的平面图,且每个面的次数至少为l(l3),则 (2)2lmnlv证明. 2mlr,v n-mr2,vln-lm2m ln-lmlr2l,v lm-2mln-2lv (2)2lmnl推广v设G是p(p2)个连通分支的平面图,每个面的次数至少为l(l3),则(1)2lmnplK5和K3,3vK5和K3,3都不是平面图.若K5是平面图,则每个面的次数至少为3.但是由前面的定理有; 103(5-2)9这是矛盾的,因而K5不是平面图. 类似地,K3,3也不是平面图. 定理6v设G为连通的简单的平面图,则G中至少存在一个顶点v,有d(v)5. v证明.v

15、假设任意顶点v,d(v)6.v 6n2m,3r2mv 3nmv n-mr2v 63n-3m3rm-3m2m0 这不可能.消去 插入v 在图(1)中,从左到右的变换称为消去2度顶点w.图(2)中从左到右的变换称为插入2度顶点w.同胚 初等收缩v如果两个图G1和G2同构,或经过反复插入或消去2度顶点后同构,则称G1与G2同胚.v图G中相邻顶点u,v之间的初等收缩由下面方法给出;删除边(u,v),用新的顶点w取代u,v,使w关联u,v关联的一切边(除(u,v)外).库拉图斯基定理v一个图是平面图当且仅当它不含与K5同胚子图,也不含与K3,3同胚子图.v另一种叙述形式; 一个图是平面图当且仅当它没有可

16、以收缩到K5的子图,也没有收缩到K3,3的子图.agcdefhibj收缩边(a, f), (b, g), (c, h), (d, i), (e, j)，所得图为K5。或者令G=G-(j, g), (d, c)，则G与K3,3同胚例abcdefg令G=G-(d, f), (g, c)，易知G与K5同胚。令G=G-(a, e), (a, f), (b, g), (g, f)，则G与K3,3同胚G2不满足t条件,但满足相异性条件,因而也存在完备匹配,图中粗边所示匹配就是其中的一个完备匹配. G3不满足t条件,也不满足相异性条件,因而不存在完备匹配,故选不出3名不兼职的组长来.67 10.1 欧拉图1

17、0.2 哈密尔顿图10.3 平面图10.4 二部图 第10章 几种典型图几种典型图 若能将无向图G=的顶点集V划分成两个子集V1和V2(V1V2=),使得G中任何一条边的两个端点一个属于V1,另一个属于V2,则称G为二部图(也称为偶图).V1,V2称为互补顶点子集,此时可将G记成G=,若V1 =n, V2=m,则记完全二部图G为Kn,m.二部图 在下图中,(1)所示为K2,3,(2)所示为K3,3. K3,3是重要的完全二部图,它与K5一起在平面图中起着重要作用.判断二部图的定理一个无向图G=是二部图当且仅当G中无奇数长度的回路.图10.2123456624153图10.2所示3个图中,均无奇

18、数长度的回路,所以,它们都是二部图.其中图(2)所示为K2,3,图(3)所示为K3,3,它们分别与图10.1中(1),(2)所示的图同构. 设G=为无向图,E*E,若E*中任意两条边均不相邻,则称E*为G中的匹配(或边独立集).若在E*中再加入任何1条边就都不是匹配了,则称E*为极大匹配.边数最多的极大匹配称为最大匹配,最大匹配中的元素(边)的个数称为G的匹配数,记为1(G),简记为1.匹 配今后常用M表示匹配.设M为G中一个匹配.vV(G),若存在M中的边与v关联,则称v为M饱和点,否则称v为M非饱和点,若G中每个顶点都是M饱和点,则称M为G中完美匹配. 在图 (1)中，e1,e1,e7,e

19、5,e4,e6等都是图中的匹配.其中e5,e1,e7,e4,e6是极大匹配,e1,e7,e2,e6是最大匹配,匹配数1=2. 图中不存在完美匹配.在图(2)中,e2,e5,e3,e6,e1,e7,e4都是极大匹配,其中e1,e7,e4是最大匹配,同时也是完美匹配,匹配数为3.完备匹配u设G=为一个二部图,M为G中一个最大匹配,若M =minV1,V2,则称M 为G中的一个完备匹配.u此时若V1 V2,则称M为V1到V2的一个完备匹配.如果V1= V2,这时M为G中的完美匹配.图10.4存在完备匹配吗?存在完美匹配吗?.Hall定理设二部图G=,V1V2,G中存在从V1到V2的完备匹配当且仅当V1中任意k个顶点(k=1,2, V1)至少邻接V2中的k个顶点.设二部图G=,如果u (1)V1中每个