第6章-一些特殊的图

第6章一些特殊的图内容导读:

二部图欧拉图哈密顿图平面图难点:各种图的判别定理2023/9/28离散数学1

ABCD2023/9/28离散数学2(1)(2)设无向图G=<V,E>有两个V的子集V1,V2,它们具有满足：V1∪V2=VV1∩V2=

图G中的每一边e均具有e=(vi,vj

)其中：vi∈V1,

vj∈V2则称G是一个二部图，2023/9/28离散数学3定义6.1若一个图G的结点集V能划分为两个子集V1和V2，使得G的每一条边{vi,vj}满足vi∈V1,vj∈V2,则称G是一个二部图，V1和V2称为G的互补结点子集。此时可将G记成G=<V1,V2,E>

若V1中任一结点与V2中每一结点均有边相连接,则称二部图为完全二部图。若|V1|=n,|V2|=m则记完全二部图G为Kn,m。(1)(2)K2,3K3,32023/9/28离散数学4(1)(2)例6.1

判断下列图是否是二部图？v1v3v5v2v4v6v1v4v8v5v2v3v6v7v1v2v3v4v5(3)在图(1)中,V1={v1,v3,v5},V2={v2,v4,v6},是一个完全二部图。在图(2)中,V1={v1,v4,v8,v5},V2={v2,v3,v7,v6},是一个二部图。在图(3)中,对于其中的顶点无法将它们分到两个不同的子集V1和V2,使其边能满足二部图的定义,所以它不是二部图。二部图是不是一定是连通图?2023/9/28离散数学5(4)(5)定理6.1一个无向图G=<V,E>是二部图当且仅当G中无奇数长度的回路。下图所示前3个图中,均无奇数长度的回路,所以它们都是二部图,其中图(2)所示为K2,3,图(3)所示为K3,3,它们分别与图(4)和(5)同构。(1)(2)(3)2023/9/28离散数学6(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在图(1)中，{e1},{e1,e7},{e5},{e4,e6}等都是图中的匹配。在图(2)中找出匹配。定义6.2

设G=<V,E>为无向图,E*E,若E*中任意两条边均不相邻,则子集E*称为G中的匹配(或边独立集),并把E*中的边所关联的两个结点称为在E*下是匹配的。2023/9/28离散数学7(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在图(1)中,{e5},{e1,e7},{e4,e6}{e3,e7},{e2,e6}是极大匹配，后4个是最大匹配，匹配数

1=2。若在E*中再加入任何一条边就都不是匹配了,则称E*为极大匹配。边数最多的极大匹配称为最大匹配，最大匹配中的元素(边)的个数称为G的匹配数，记为1(G),简记为1。2023/9/28离散数学8(2)e1e2e3e4e5e6e7在图(2)中,{e2,e5},{e3,e6},{e1,e7,e4}都是极大匹配,其中{e1,e7,e4}是最大匹配。2023/9/28离散数学9(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在图(1)中不存在完美匹配。在图(2)中,{e1,e7,e4}是最大匹配，同时也是完美匹配。今后常用M表示匹配，设M为G中一个匹配，vV(G),若存在M中的边与v关联，则称v为M饱和点，否则v为M非饱和点，若G中每个顶点都是饱和点，则称M为G中完美匹配。2023/9/28离散数学10v1v2v3v4v5v6v7v8v9v1v2v3v4v5v6v7v8(2)(1)在图(1)中的一个最大匹配是M={(v1,v2),(v3,v9),(v5,v6),(v7,v8)}在图(2)中的一个完美匹配是M={(v1,v2),(v3,v4),(v5,v6),(v7,v8)}2023/9/28离散数学11定义6.3

设G=<V1,V2,E>为二部图,M为G中一个最大匹配,

若|M|=min{|V1|,|V2|},则称M为G中的一个完备匹配,此时若|V1|≤|V2|,则称M为V1到V2的一个完备匹配。如果|V1|=|V2|,这时M为G中的完美匹配。G1G2G3在上图中,{e1,e2}为G1中的最大匹配,G1中不存在完备匹配,更无完美匹配。G2中{e1,e2,e3}为完备匹配,但G2中无完美匹配。G3中{e1,e2,e3}为完备匹配,同时也是完美匹配。e1e2e1e2e3e1e2e32023/9/28离散数学12例6.2我们班级成立了3个运动队:篮球队、排球队和足球队。今有张、王、李、赵、陈5位同学，若已知张、王为篮球队员；张、李、赵为排球队员；李、赵、陈为足球队员，问能否从这5人中选出3名不兼职的队长？解:构造二部图G=<V1,V2,E>其中V1=

篮球队,排球队,足球队,V2=

张,王,李,赵,陈

图中的边分别表示这5位同学是相应球队的队员,图中存在V1到V2的匹配,因此题目要求可以满足。如可选张为篮球队长,李为排球队长,陈为足球队长。篮排足张王李赵陈V1V22023/9/28离散数学13例6.3今有3人甲、乙、丙和3项工作a,b,c,已知甲能胜任3项工作a,b,c,乙能胜任2项工作a,b,丙能胜任2项工作b,c。能否给出2种不同的方案，使每个人各去完成一项他能胜任的工作？解:构造二部图G=<V1,V2,E>其中V1=

甲,乙,丙,V2=

a,b,c

若V1中某人能胜任V2中某项工作，则用边连接这两个结点，得到右图。显然(甲,a),(乙,b),(丙,c)和(甲,c),(乙,a),(丙,b)是符合题目要求的2种不同的方案请同学们考虑:还有第3种方案吗？甲乙丙abcV1V22023/9/28离散数学14几个问题1“一笔画”问题2“街道清扫车”设某封闭式小区的路网结构如图所示，请证明能否设计出一条路线使得清洁车从小区大门出发清扫每条道路恰好一次，且在清扫完最后一条道路后正好返回小区大门处。3七桥问题小区大门ABCD6.2欧拉图2023/9/28离散数学15ABCD在以下4个图中,不能一笔画出图①,②,而能一笔画出图③,④且在④中笔又能回到出发点。①②③④在③中存在关联所有顶点的简单通路,在④中存在关联所有顶点的简单回路2023/9/28离散数学16定义6.4通过图(无向图或有向图)中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路。通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。具有欧拉通路而无欧拉回路的图称为半欧拉图。规定：平凡图是欧拉图。2023/9/28离散数学17ABCDEe1e2e3e4例6.4

左下图既是欧拉回路，也是欧拉图

而右下图则是欧拉通路2023/9/28离散数学18推论无向图G是欧拉图

G是连通图，且G中没有奇度顶点。

无向图G是半欧拉图

G是连通图，且G中恰有两个奇度顶点。定理6.4无向图G具有欧拉通路

G是连通图，且G中有零个或两个奇度顶点。

若无奇度顶点，则通路为欧拉回路；若有两个奇度顶点，则它们是每条欧拉通路的端点。2023/9/28离散数学19例6.5考察下图是否为欧拉图或存在欧拉通路？∵存在两个奇度顶点∴根据定理6.4推论知不是欧拉图.存在一条欧拉通路2023/9/28离散数学20v4

v5

E

G4

Av2

v3

B

C

v1

D（a）(b)

图6－1例6.6求下列图是否为欧拉图或存在欧拉通路？v1v2v3v4v5•••••••••••EBFADC(1)(2)解:在图(1)中,d(v1)=d(v2)=d(v3)＝3有两个以上的结点的度为3.根据定理6.4知:图(1)中不存在欧拉通路，当然不存在欧拉回路,所以不是欧拉图.不能一笔画出.

在图(2)中,d(A)=2,d(B)=d(C)=d(D)=4 d(E)=d(G)=3只有两个奇数度的结点,有欧拉通路,根据定理6.4推论知不是欧拉图.存在一条欧拉通路,如EDBEFCABCDF2023/9/28离散数学21定理6.5有向图D具有欧拉通路

D

是连通的,且除了两个顶点外,其余顶点的入度均等于出度。在这两个特殊的顶点中,一个顶点的入度比出度大1,另一个顶点的入度比出度小1。推论一个有向图D是欧拉图

D是连通的，且所有顶点的入度等于出度。特别提醒：欧拉回路要求边不能重复，结点可以重复.笔不离开纸，不重复地走完所有的边，回到原处.就是所谓的一笔画.

2023/9/28离散数学22v0v1v2e10e’12e21e00e01e20e22e12e’01例6.7考察下图是欧拉通路或欧拉回路吗？三个顶点的度出度与入度相同是欧拉回路！∵沿着边

e00,e01,e12,e22,e21,e10,e’01,e’12,e20

回到出发点2023/9/28离散数学231234e1e2e3e4e5e1e2e3e4e5e1e2e3e4e5e6e3e1e2e4e2e1e3e4e5e2e1e3e456例6.6：判断各图是否存在欧拉通路或欧拉回路2023/9/28离散数学24v1v2v3v4e1e2e3e4e4e5e6e7例6.9

判定下图中，是否有欧拉回路？若有请把欧拉回路写出来.

在图中，D是连通的，且所有顶点的出度等于入度。根据定理6.5推论知：D是欧拉图，所以存在欧拉回路，一个欧拉回路为v1e1

v2e2

v3e5

v1e4

v3e3

v4

e6v2e7

v4e4v12023/9/28离散数学25几个问题在一个大城市，有很多取款机，那么，如何制定出一个最优的路线，使运钞车过每个提款机一次就能运送完钱钞？货郎担问题 旅行商人问题

(TravelingSalesmanProblem,TSP)

优化算法——近似解

演化算法6.3哈密顿图2023/9/28离散数学26几个问题1.在一个大城市，有很多取款机，那么，如何制定出一个最优的路线，使运钞车过每个提款机一次就能运送完钱钞？货郎担问题旅行商人问题(TSP)2.考虑在七天内安排七门课程的考试，要求同一位教师所任教的两门课程考试不安排在接连的两天里，如果教师所担任的课程都不多于四门，则是否存在满足上述要求的考试安排方案？ 时间表问题3.国际象棋的跳马是否可以遍历其棋盘，即从任一格出发跳到每一格仅一次并最后回到出发的棋盘格子？4.在一个至少有5人出席的圆桌会议上（会议需要举行多次），为达到充分交流的目的，会议主持者希望每次会议每人两侧的人均与前次不同，这是否可行？请应用图论知识进行论证。5.周游世界问题2023/9/28离散数学27哈密尔顿图问题

1859年爱尔兰数学家威廉·哈密尔顿（SirWilliamHamilton）发明了一个小游戏玩具：一个木刻的正十二面体，每面系正五角形，三面交于一角，共有20个角，每角标有世界上一个重要城市。哈密尔顿提出一个问题：要求沿正十二面体的边寻找一条路通过20个城市，而每个城市只通过一次，最后返回原地。哈密尔顿将此问题称为周游世界问题。游戏)求解 抽象为图论问题

哈密尔顿给出了肯定回答，该问题的解是存在的哈密尔顿回路(圈)哈密尔顿图运筹学、计算机科学和编码理论中的很多问题都可以化为哈密尔顿图问题

WilliamRowanHamilton(1805-1865)2023/9/28离散数学28定义6.5

经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。经过图中所有顶点一次且仅一次的回路称为哈密顿回路。具有哈密顿回路的图称为哈密顿图.具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图.注:平凡图是哈密顿图。6.3哈密顿图2023/9/28离散数学29例6.10指出下列各图是否哈密顿图,有无哈密顿通路,回路？解(1)容易判断,存在哈密顿回路,故是哈密顿图.(2)只有哈密顿通路,无哈密顿回路,故不是哈密顿图.(3)无哈密顿通路，显然不是哈密顿图.(1)(2)(3)2023/9/28离散数学30例6.11：判断各图是否是哈密顿图。1234e1e2e3e4e5e1e2e3e4e5e1e2e3e4e5e6e3e1e2e4e2e1e3e4e5e2e1e3e4562023/9/28离散数学31例6.12画出具有下列条件的有5个结点的无向图(1)

不是哈密顿图，也不是欧拉图；(2)有哈密顿回路，没有欧拉回路；(3)没有哈密顿回路，有欧拉回路；(4)是哈密顿图，也是欧拉图.解作图如图(4)(不唯一).(1)(2)(3)(4)2023/9/28离散数学32例6.12画出具有下列条件的有5个结点的无向图(1)

不是哈密顿图，也不是欧拉图；(2)有哈密顿回路，没有欧拉回路；(3)没有哈密顿回路，有欧拉回路；(4)是哈密顿图，也是欧拉图.解作图如图(4)(不唯一).(1)(2)(3)(4)2023/9/28离散数学33定理6.6——必要条件设无向图G=<V,E>是哈密顿图,对于任意V1

V且V1≠,均有p(G-V1)≤|V1|,其中p(G-V1)为G中删除V1(删除V1中各顶点及关联的边)后所得图的连通分支数。证:设C为G中任意一条哈密顿回路。①若V1中的顶点在C上彼此相邻，则p(C-V1)=1≤|V1|②设V1中的顶点在C上存在r(2≤r≤|V1|)个互不相邻，则p(C-V1)=r≤|V1|

一般说来,V1中的顶点在C上既有相邻的,又有不相邻的,因而总有p(C-V1)≤|V1|，而C是G的生成子图,∴p(G-V1)≤p(C-V1)≤|V1|2023/9/28离散数学34e1e2e3e4e5e6v1v2v3v4V1={v1,v4}或V1={v2,v3}

v5若V1中的顶点在C上彼此相邻，则P(C-V1)=1≤|V1|2023/9/28离散数学35e1e2e3e4e5e6e7V1={v1,v2,v3}或V1={v1,v4,v3}

v1v2v3v4v5设V1中的顶点在C上存在r(2≤r≤|V1|)个互不相邻，则P(C-V1)=r≤|V1|

2023/9/28离散数学36例6.13利用定理6.6可判断某些图不是哈密顿图设下图①为G1,取

V1={v},则P(G1-V1)=2>|V1|=1

G1-V1为图②所示,由定理6.6可知G1不是哈密顿图v①②2023/9/28离散数学37例6.13利用定理6.6可判断某些图不是哈密顿图设下图①为G2,在G2中取

V2={a,b,c,d,e,f,g},则G2-V2为图②所示,P(G2-V2)=9>|V2|=7

由定理6.6可知G2不是哈密顿图①②abcdefg2023/9/28离散数学38定理6.7

——充分条件设G是n(n≥3)阶无向简单图，若对G中任意不相邻的顶点vi,vj的度数之和大于等于n-1，即d(vi)+d(vj)≥n-1则G中存在哈密顿通路.推论

设G为n(n≥3)阶无向简单图，若对于G中任意两个不相邻的顶点vi,vj，均有

d(vi)+d(vj)≥n则G中存在哈密顿回路，从而G为哈密顿图。2023/9/28离散数学39e1e2e3e4e5e6d(vi)+d(vj)≥n-1存在哈密顿通路d(vi)+d(vj)≥n存在哈密顿回路2023/9/28离散数学40(2)(3)再如下图G任意两个不相邻的顶点vi,vjd(vi)+d(vj)≥n-1则G中存在哈密顿通路.d(vi)+d(vj)≥n则G中存在哈密顿回路，从而G为哈密顿图。abdc(1)(1)和(2)2023/9/28离散数学41例6.14判断下图是否是哈密顿图afedcb2023/9/28离散数学42定理6.6在n(n≥2)阶有向图D=<V,E>中，如果所有有向边均用无向边代替，所得无向图中含生成子图Kn,则有向图D中存在哈密顿通路.推论

n(n≥3)阶有向完全图G为哈密顿图。2023/9/28离散数学43例6.15已知有关人员a,b,c,d,e,f,g的有关信息a：说英语；

b：说英语或西班牙语；c；说英语，意大利语和俄语；d：说日语和西班牙语e：说德语和意大利语；f：说法语、日语和俄语；g：说法语和德语.试问：上述7人中是否任意两人都能交谈？(可借助其余5人中组成的译员链帮助) 2023/9/28离散数学44abcdefg解设7个人为7个结点,将两个懂同一语言的人之间连一条边(即他们能直接交谈),这样就得到一个简单图G,问题就转化为G是否连通.如图所示,因为G的任意两个结点是连通的,所以G是连通图.因此,上述7个人中任意两个人能交谈. a：说英语；b：说英语或西班牙语；C:说英语,意大利语和俄语；d：说日语和西班牙语e：说德语和意大利语；f：说法语、日语和俄语；g：说法语和德语.2023/9/28离散数学45abcdefg如果题目改为：试问这7个人应如何安排座位,才能使每个人都能与他身边的人交谈？解：用结点表示人，用边表示连接的两个人能将同一种语言，够造出哈密顿图如右上图所示。a：说英语；b：说英语或西班牙语；c；说英语，意大利语和俄语；d：说日语和西班牙语e：说德语和意大利语；f：说法语、日语和俄语；g：说法语和德语.英英西日法德意2023/9/28离散数学46对于平面图,先举一例,设有一个电路它有六个元件，三个分成一组，一个元件组的每个元件都用导线与另一组的每个元件相接，是否有这样的接法使得导线互不交叉？这个问题可用左下图表示,它的最少交叉点是一个，用右下图表示§6.4.平面图2023/9/28离散数学47定义6.6

一个图G能画在平面上，除顶点之外，再没有边与边相交.则称G为平面图。画出的没有边交叉的图称为G的一个平面嵌入或G的一个平面.在下图中(2)是(1)(K4