欧拉图与哈密顿图.ppt

该【欧拉图与哈密顿图 】是由【3827483】上传分享，文档一共【41】页，该文档可以免费在线阅读，需要了解更多关于【欧拉图与哈密顿图 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。中国地质大学本科生课程
离 散 数 学
第15章 欧拉图与哈密顿图
本章内容
1 欧拉图
1
2 哈密顿图
2
欧拉图
历史背景－－哥尼斯堡七桥问题
欧拉图是一笔画出的边不重复的回路。
欧拉图
通路:设G为无向标定图，G中顶点与边的交替序列Г＝ vi0ej1vi1ej2vi2…ejivil称为vi0到vil的通路，其中，vi0，vil分别称为Г的始点与终点。
回路:若vi0＝vil，则称通路为回路。
简单通路:通路中，若Г的所有边各异;
简单回路: 简单通路中，若vi0＝vil；
初级通路或路径：若Г的所有顶点(除vi0与vij可能相同外)各异，
所有边也各异；
初级回路或圈：初级通路或路径中，若vi0＝vil，
欧拉图
欧拉通路: 通过图（无向图或有向图）中所有边一次且仅
一次行遍图中所有顶点的通路;
欧拉回路: 通过图中所有边一次并且仅一次行遍所有顶点
的回路。
欧拉图: 具有欧拉回路的图;
半欧拉图:具有欧拉通路而无欧拉回路的图。
举例
欧拉图
欧拉图
半欧拉图
无欧拉通路
无欧拉通路
无欧拉通路
无向欧拉图的判定定理
01
无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。
添加标题
02
无向图G是半欧拉图当且仅当G是连通的，且G中恰有两个奇度顶点。
添加标题
有向欧拉图的判定定理
有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度。
有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度。
01
举例
02
有向欧拉图的判定定理
G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈的并。

设G是非平凡的且非环的欧拉图，证明：
λ(G)≥2。
对于G中任意两个不同顶点u,v，都存在简单回路C含u和v。
证明 (1)，e∈E(G)，存在圈C，e在C中，
因而p(G-e)＝p(G)，故e不是桥。
由e的任意性λ(G)≥2，即G是2边-连通图。