第十五章欧拉图与哈密顿图课件.ppt
《第十五章欧拉图与哈密顿图课件.ppt》由会员分享,可在线阅读,更多相关《第十五章欧拉图与哈密顿图课件.ppt(62页珍藏版)》请在三一办公上搜索。
1、,欧拉图与哈密顿图,欧 拉 图,一欧拉通路、欧拉回路、欧拉图、半 欧拉图的定义,定义 通过图(无向图或有向图)中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路,通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图,具有欧拉通路而无欧拉回路的图称为半欧拉图。,从定义不难看出,欧拉通路是图中经过所有边的简单的生成通路(经过所有顶点的通路称为生成通路),类似地,欧拉回路是经过所有边的简单的生成回路。 在这里做个规定,即平凡图是欧拉图。,图,在图所示各图中,为()中的欧拉回路,所以()图为欧拉图。为()中的一条欧拉通路,但图中不存在欧拉回路,所以()为半欧拉图。
2、()中既没有欧拉回路,也没有欧拉通路,所以()不是欧拉图,也不是半欧拉图。为()图中的欧拉回路,所以()图为欧拉图。(),()图中都既没有欧拉回路,也没有欧拉通路,二、判别定理 定理 无向图是欧拉图当且仅当是连 通图,且中没有奇度顶点。 证: 若是平凡图,结论显然成立, 下面设为非平凡图,设是条边的阶 无向图。并设的顶点集,. 必要性: 因为为欧拉图,所以中存 在欧拉回路,设为中任意一条欧拉回路,, ,都在上,因而连通所以为连通图。又 ,在上每出现一次获得度,若出现次就获得度,即(),所以中无奇度顶点。 充分性: 由于为非平凡的连通图可知,中边数.对作归纳法。 ()时,由的连通性及无奇度顶点可
3、知,只能是一个环,因而为欧拉图。 ()设()时结论成立,要证明时,结论也成立。由的连通性及,无奇度顶点可知,().类似于例,用扩大路径法可以证明中存在长度大于或等于的圈,设为中一个圈,删除上的全部边,得的生成子图 ,设有个连通分支,,每个连通分支至多有条边,且无奇度顶点,并且设与的公共顶点为 ,,,由归纳假设可知,,都是欧拉图,因而都存在欧拉回路,,.最后将还原(即将,删除的边重新加上),并从上的某顶点开始行遍,每遇到 ,就行遍 中的欧拉回路 ,,,最后回到,得回路 ,此回路经过中每条边一次且仅一次并行遍中所有顶点,因而它是中的欧拉回路 ,故为欧拉图。,由定理立刻可知,图中的三个无向图中,只有
4、()中无奇度顶点,因而()是欧拉图,而()、()都有奇度顶点,因而它们都不是欧拉图。 定理 : 无向图是半欧拉图当且仅当是连通的,且中恰有两个奇度顶点。 证: 必要性 设是条边的阶无向图,因为为半欧拉图,因而中存在欧拉通路,(但不存在欧拉回路),设 为中一条欧拉通路, . (),若不在的端点出现,显然()为偶数,若在端点出现过,则()为奇数,因为只有两个端点且不同,因而中只有两个奇数顶点。另外,的连通性是显然的。充分性: 设的两个奇度顶点分别 为 和,对加新边(),,得 (),则是连通且无奇度顶点 的图,由定理可知,为欧拉图,因而存在欧拉回路,而 ()为中一条欧拉通路,所以为半欧拉图。 由定理
5、立即可知,图中()是半欧拉图,但()不是半欧拉图。 定理 有向图是欧拉图当且仅当是强连通的且每个顶点的入度都等于出度。本定理的证明类似于定理 .,定理 有向图是半欧拉图当且仅当是单向连通的,且中恰有两个奇度顶点,其中一个的入度比出度大,另一个的出度比入度大,而其余顶点的入度都等于出度。,图,由定理立即可知,图()图为欧拉图,本图既可以看成圈, ,之并(为清晰起见,将个圈画在()中),也可看成圈与圈之并(两个圈画在()中)。将()分解成若干个边不重的圈的并不是()图特有的性质,任何欧拉图都有这个性质。,定理 是非平凡的欧拉图当且仅当是连通的且为若干个边不重的圈的并。 本定理的证明可用归纳法。 例
6、 设是非平凡的且非环的欧拉图,证明:()().()对于中任意两个不同顶点,都存在简单回路含和.,证 ()由定理可知, (),存在圈,在中,因而()(),故不是桥。由的任意性(),即是边连通图。 () (),由的连通性可知,之间必存在路径,设 (),则在 中与还必连通,否则,与必处于 的不同的连通分支中,这说明在上存在中的桥,这与()矛盾。于,是在中存在到的路径,显然与边不重,这说明处于形成的简单回路上。三、求欧拉图中欧拉回路的算法 设为欧拉图,一般来说中存在若干条欧拉回路,下面介绍两种求欧拉回路的算法。,算法,能不走桥就不走桥: ()任取(),令.()设已经行遍,按下面方法来从(),中选取:(
7、)与相关联;()除非无别的边可供行遍,否则不应该为,中的桥。()当()不能再进行时,算法停止。,可以证明,当算法停止时所得简单回路()为中一条欧拉回路。 例 图()是给定的欧拉图。某人用算法求中的欧拉回路时, 走了简单回路 之后(观看他的错误走法),无法行遍了,试分析在哪步他犯了错误?,图,解: 此人行遍时犯了能不走桥就不走桥的错误,因而他没行遍出欧拉回路。当他走到时,为图()所示。此时为该图中的桥,而均不是桥,他不应该走,而应该走或,他没有走,所以犯了错误。注意,此人在行遍中,在遇到过桥,处遇到过桥,但当时除桥外他无别的边可走,所以当时均走了桥,这是不会犯错误的。,逐步插入回路法 设为阶无向
8、欧拉图,(),,求中欧拉回路的逐步插入回路法的算法如下: 开始 ,*,. 在中任取一条与关联的边(),将及加入到中得到.若 *,转,否则 ,转.,若()(),结束,否则,令(),在中任取一条与中某顶点关联的边,先将改写成起点(终点)为的简单回路,再置*, ,转. 现在再考虑例中图中图(),用逐步插入回路法可以走出多条欧拉回路。现在走出一条来: 开始时,置*,,,经过步得 , 是长度为的简单回路,见演示中红边所示。 在中有条边与上的顶点相关联,比如取与,先将改写成以为起点(终点)的简单回路: , 然后置*,再经过步得 (),后插入的回路为绿色的。,在中,均与上的顶点关联。比如取与,再将改写成以为
9、起点(终点)的简单回路再置*,再经过步得 ()又插入一个长度为的回路。 则()(),故是的一条欧拉回路。,哈密顿图 一、哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图的定义 定义 经过图(有向图或无向图)中所有顶点一次且仅一次的通路称为哈密顿通路。经过图中所有顶点一次且仅一次的回路称为哈密顿回路。具有哈密顿回路的图称为哈密顿图,具有哈密顿通路但不,具有哈密顿回路的图称为半哈密顿图。平凡图是哈密顿图。 图中所示的三个无向图都有哈密顿回路,所以都是哈密顿图。有向图中,()具有哈密顿回路,因而它是哈密顿图。()只有哈密顿通路,但无哈密顿回路,因而它是半哈密顿图,而()中既无哈密顿回路,也没有哈密顿通路
10、,因而不是哈密顿图,也不是半哈密顿图。,二、哈密顿图与半哈密顿图的一些必要与充分条件 从定义可以看出,哈密顿通路是图中生成的初级通路,而哈密顿回路是生成的初级回路。判断一个图是否为哈密顿图,就是判断能否将图中所有顶点都放置在一个初级回路(圈)上,但这不是一件易事。与判断一个图是否为欧拉图不一样,到目前为止,人们还没有找到哈密顿图简单的充分必要条件。,下面给出的定理都是哈密顿通路(回路)的必要条件或充分条件。 定理 设无向图是哈密顿图,对于任意 ,且 ,均有 () 其中,()为的连通分支数。 证 设为中任意一条哈密顿回路,易知,当中顶点在上均不相邻时,,()达到最大值,而当中顶点在上有彼此相邻的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十五 章欧拉图 哈密 课件
链接地址:https://www.31ppt.com/p-1454721.html