离散数学及应用 课件 6.2-3 欧拉图

DiscreteMathematics鄢小虎

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

4哥尼斯堡七桥问题

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

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

定理

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

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

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

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

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

定理

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

V且V1,均有p(G

V1)

|V1|.(连通分支数小于顶点个数)说明定理中的条件是哈密顿图的必要条件,但不是充分条件.目前为止，还没有简单方法判断一个图是否为哈密顿图.可利用该定理判断某些图不是哈密顿图.19周游世界问题观察出一条哈密顿