离散数学及应用 课件 第6章 特殊的图

DiscreteMathematics鄢小虎

离散数学2第6章特殊的图6.1二部图6.2欧拉图6.3哈密顿图6.4平面图36.1二部图

二部图完全二部图判断定理4二部图

定义设无向图G=<V,E>,若能将V划分成V1和V2(V1

V2=V,V1

V2=),使得G中的每条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图,记为<V1,V2,E>,称V1和V2为互补顶点子集.定义若G是简单图,且V1中每个顶点都与V2中每个顶点相邻,则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|.

5二部图(续)

例下述各图是否是二部图?

不是(?)6二部图(续)

定理无向图G=<V,E>是二部图当且仅当G中没有长度为奇数的回路

练习：第151页，例6.8题的第一问，是不是二部图，为什么？DiscreteMathematics鄢小虎

离散数学86.2欧拉图欧拉通路与欧拉回路存在欧拉通路和欧拉回路的充分必要条件9哥尼斯堡七桥问题

10哥尼斯堡七桥问题

要求边不重复地一笔画出整个图中文讲解：/video/BV1kp4y1i7Dt?from=search&seid=10286761314152734386&spm_id_from=333.337.0.011欧拉图

欧拉通路:图中行遍所有顶点且恰好经过每条边一次的通路.欧拉回路:图中行遍所有顶点且恰好经过每条边一次的回路（注意：顶点没有说只1次）欧拉图:有欧拉回路的图.半欧拉图:有欧拉通路,但无欧拉回路的图.说明：上述定义对无向图和有向图都适用.规定平凡图为欧拉图（？）.欧拉通路是简单通路,欧拉回路是简单回路.环不影响图的欧拉性.12实例根据定义判断是否为欧拉图或半欧拉图?欧拉图欧拉图半欧拉图半欧拉图不是(至少2次边)不是(无通路)13欧拉图的判别法

定理

无向图G为欧拉图当且仅当G连通且无奇度顶点.G是半欧拉图当且仅当G连通且恰有两个奇度顶点.14实例例1哥尼斯堡七桥问题4个奇度顶点,不存在

欧拉通路,更不存在欧拉回路练习：判断下面图是否为欧拉图或半欧拉图?15有向欧拉图的判别法

定理有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度.D是半欧拉图当且仅当D连通且恰有两个奇度顶点,其中一个入度比出度大1,另一个出度比入度大1,其余顶点的入度等于出度.课堂练习16练习：判断下面图是否为欧拉图或半欧拉图?课前复习17二部图判断定理：G中没有长度为奇数的回路

欧拉通路与欧拉回路图中行遍所有顶点且恰好经过每条边一次的通（回）路存在欧拉通路和欧拉回路的充分必要条件无向图G为欧拉图当且仅当G连通且无奇度顶点.G是半欧拉图当且仅当G连通且恰有两个奇度顶点.

18课堂练习课本154页，习题6.7，哪些是欧拉图、半欧拉图？一笔画游戏(3分钟)19三个图能否一笔画(笔不离纸、不重复)出来?206.3哈密顿图哈密顿通路和哈密顿回路存在哈密顿通路和哈密顿回路的充分条件与必要条件21哈密顿周游世界问题每个顶点是一个城市,有20个城市,要求从一个城市出发,恰好经过每一个城市一次,回到出发点.12面体投射到平面/item/%E5%93%88%E5%AF%86%E9%A1%BF%E5%9B%BE/2587317?fr=aladdin22哈密顿图的定义哈密顿通路:经过图中所有顶点一次且仅一次的通路.哈密顿回路:经过图中所有顶点一次且仅一次的回路.哈密顿图:具有哈密顿回路的图.半哈密顿图:具有哈密顿通路而无哈密顿回路的图.注意：边无需全部经过说明：平凡图是哈密顿图.环与平行边不影响图的哈密顿性.23课堂练习根据定义判断是否为哈密顿图,半哈密顿图?哈密顿图哈密顿图半哈密顿图不是24无向哈密顿图的一个必要条件

定理

设无向图G=<V,E>是哈密顿图,则对于任意V1

V且V1,均有p(G

V1)

|V1|.(连通分支数小于顶点个数)说明定理中的条件是哈密顿图的必要条件,但不是充分条件.目前为止，还没有简单方法判断一个图是否为哈密顿图.可利用该定理判断某些图不是哈密顿图.25周游世界问题观察出一条哈密顿回路右图(周游世界问题)中红边给出一条哈密顿回路,故它是哈密顿图.26课堂练习判断是否为(半)哈密顿图，并绘制出来27课堂练习答案DiscreteMathematics鄢小虎

离散数学296.4平面图平面图与平面嵌入平面图的面欧拉公式30为什么学习平面图？31平面图和平面嵌入定义如果能将图G除顶点外边不相交地画在平面上,则称G是平面图.这个画出的无边相交的图称作G的平面嵌入.没有平面嵌入的图称作非平面图.

32平面图和平面嵌入(续)今后称一个图是平面图,可以是指定义中的平面图,又可以是指平面嵌入,视当时的情况而定.当讨论的问题与图的画法有关时,是指平面嵌入.设G

G,若G为平面图,则G

也是平面图;若G

为非平面图,则G也是非平面图.平行边与环不影响图的平面性.33实例练习：判断下面图是否为平面图?34平面图的面与次数设G是一个平面嵌入G的面:由G的边将平面划分成的每一个区域无限面(外部面):面积无限的面,用R0表示有限面(内部面):面积有限的面,用R1,R2,…,Rk表示面Ri的边界:包围Ri的所有边构成的回路组面Ri的次数:Ri边界的长度，用deg(Ri)表示35平面图的面与次数(续)定理

平面图各面的次数之和等于边数的2倍.实例右图有4个面,deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0