哈尔滨理工大学呻斛生課程 离影数 第15章欧拉图与哈密顿图 计算机系
第15章 欧拉图与哈密顿图 离 散 数 学 哈尔滨理工大学本科生课程 计算机系
本章内容 15.1欧拉图 15.2哈密顿图 15.3带权图与货郎担问题 基本要求 作业
本章内容 15.1 欧拉图 15.2 哈密顿图 15.3 带权图与货郎担问题 基本要求 作业
15,1欧抗图 口历史背景一一哥尼斯堡七桥问题 B B D 口欧拉图是一笔画出的边不重复的回路
15.1 欧拉图 ❑ 历史背景－－哥尼斯堡七桥问题 ❑ 欧拉图是一笔画出的边不重复的回路
定义15.1通过图(无向图或有向图)中所有边一次且仅一次 行遍图中所有顶点的通路称为欧拉通路,通过图中所有边 次并且仅一次行遍所有顶点的回路称为欧拉回路。具有 欧拉回路的图称为欧拉图,具有欧拉通路而无欧拉回路的 图称为半欧拉图。 说明欧拉通路是图中经过所有边的简单的生成通路(经过所 有顶点的通路称为生成通路)。 欧拉回路是经过所有边的简单的生成回路
欧拉图 定义15.1 通过图（无向图或有向图）中所有边一次且仅一次 行遍图中所有顶点的通路称为欧拉通路，通过图中所有边 一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有 欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的 图称为半欧拉图。 说明 欧拉通路是图中经过所有边的简单的生成通路(经过所 有顶点的通路称为生成通路)。 欧拉回路是经过所有边的简单的生成回路
举例 欧拉图 半欧拉图 无欧拉通路 欧拉图 无欧拉通路 无欧拉通路
举例 欧拉图 半欧拉图 无欧拉通路 欧拉图 无欧拉通路 无欧拉通路
无向欧抗图的判定定理 定理15.1无向图G是欧拉图当且仅当G是连通图,且G中没有奇 度顶点。 证明若G是平凡图,结论显然成立。 下面设G为非平凡图,设G是m条边的n阶无向图, 并设G的顶点集V={v,v2,…,vn 必要性。因为G为欧拉图,所以G中存在欧拉回路, 设C为G中任意一条欧拉回路,Vv∈V""都在C上, 因而v,v连通,所以G为连通图。 又vv∈Vv在C上每出现一次获得2度 若出现次就获得2k度,即(v)=2k, 所以G中无奇度顶点
无向欧拉图的判定定理 定理15.1 无向图G是欧拉图当且仅当G是连通图，且G中没有奇 度顶点。 证明 若G是平凡图，结论显然成立。 下面设G为非平凡图，设G是m条边的n阶无向图， 并设G的顶点集V＝{v1 ,v2 ,…,vn}。 必要性。因为G为欧拉图，所以G中存在欧拉回路， 设C为G中任意一条欧拉回路，vi,vj∈V，vi,vj都在C上， 因而vi,vj连通，所以G为连通图。 又vi∈V，vi在C上每出现一次获得2度， 若出现k次就获得2k度，即d(vi)＝2k， 所以G中无奇度顶点
定理15,1的证明 充分性。由于G为非平凡的连通图可知,G中边数m≥1 对m作归纳法。 (1)m=1时,由G的连通性及无奇度顶点可知, G只能是一个环,因而G为欧拉图。 (2)设m≤k(≥1)时结论成立,要证明m=k+1时,结论也成立 由G的连通性及无奇度顶点可知,δ(G≥2。 无论G是否为简单图,都可以用扩大路径法证明G中必含圈
定理15.1的证明 充分性。由于G为非平凡的连通图可知，G中边数m≥1。 对m作归纳法。 (1)m＝1时，由G的连通性及无奇度顶点可知， G只能是一个环，因而G为欧拉图。 (2)设m≤k(k≥1)时结论成立，要证明m＝k+1时，结论也成立。 由G的连通性及无奇度顶点可知，δ(G)≥2。 无论G是否为简单图，都可以用扩大路径法证明G中必含圈
定理15,1的证明 设C为G中一个圈,删除C上的全部边,得G的生成子图G 设G'有个连通分支G1,G'2,…,G's 每个连通分支至多有k条边,且无奇度顶点, 并且设G'与C的公共顶点为v,i=1,2,…,S, 由归纳假设可知,G1,G'2,…,G都是欧拉图, 因而都存在欧拉回路C′1,i=1,2 ··· 最后将C还原(即将删除的边重新加上), 并从C上的某顶点v开始行遍,每遇到v,就行遍G′中的欧拉 回路C';,i=1,2,…,s,最后回到v 得回路vr…n…ny2…n… 此回路经过G中每条边一次且仅一次并行遍G中所有顶点, 因而它是G中的欧拉回路(演示这条欧拉回路) 故G为欧拉图
定理15.1的证明 设C为G中一个圈，删除C上的全部边，得G的生成子图G ， 设G 有s个连通分支G 1 ,G 2 ,…,G s， 每个连通分支至多有k条边，且无奇度顶点， 并且设G i与C的公共顶点为v * ji，i＝1,2,…,s， 由归纳假设可知，G 1 ,G 2 ,…,G s都是欧拉图， 因而都存在欧拉回路C i，i＝1,2,…,s。 最后将C还原（即将删除的边重新加上）， 并从C上的某顶点vr开始行遍，每遇到v * ji，就行遍G i中的欧拉 回路C i，i＝1,2,…,s，最后回到vr， 得回路vr…v * j1…v * j1…v * j2…v * j2…v * js…v * js…vr， 此回路经过G中每条边一次且仅一次并行遍G中所有顶点， 因而它是G中的欧拉回路（演示这条欧拉回路）， 故G为欧拉图
半欧抗图的判定定理 定理15.2无向图G是半欧拉图当且仅当G是连通的,且G中恰有两 个奇度顶点。 证明必要性。设G是m条边的n阶无向图,因为G为半欧拉图, 因而G中存在欧拉通路(但不存在欧拉回路), 设「=von"1…Ym1mm.为G中一条欧拉通路,V≠vmno vv∈(G,若在「的端点出现,显然d()为偶数, 若咋在端点出现过,则d(为奇数, 因为「只有两个端点且不同,因而G中只有两个奇数顶点。 另外,G的连通性是显然的
定理15.2 无向图G是半欧拉图当且仅当G是连通的，且G中恰有两 个奇度顶点。 证明 必要性。设G是m条边的n阶无向图，因为G为半欧拉图， 因而G中存在欧拉通路(但不存在欧拉回路)， 设Г＝vi0 ej1 vi1…vim-1 ejmvim为G中一条欧拉通路，vi0≠vim。 v∈V(G)，若v不在Г的端点出现，显然d(v)为偶数， 若v在端点出现过，则d(v)为奇数， 因为Г只有两个端点且不同，因而G中只有两个奇数顶点。 另外，G的连通性是显然的。 半欧拉图的判定定理
半欧抗图的判定定理 定理15.2无向图G是半欧拉图当且仅当G是连通的,且G中恰有两 个奇度顶点。 证明充分性。设G的两个奇度顶点分别为u0和vo, 对G加新边(u0,v),得G′=GU(uo,), 则G是连通且无奇度顶点的图, 由定理15.1可知,G为欧拉图, 因而存在欧拉回路C’,而C=C′-(o,vo)为G中一条欧拉通路, 所以G为半欧拉图
定理15.2 无向图G是半欧拉图当且仅当G是连通的，且G中恰有两 个奇度顶点。 证明 充分性。设G的两个奇度顶点分别为u0和v0， 对G加新边（u0,v0），得G ＝G∪(u0,v0)， 则G 是连通且无奇度顶点的图， 由定理15.1可知，G 为欧拉图， 因而存在欧拉回路C ，而C＝C -(u0,v0)为G中一条欧拉通路， 所以G为半欧拉图。 半欧拉图的判定定理