确定欧拉回路的一种方法

确定欧拉回路的一种方法确定欧拉回路的一种方法欧拉目踌连通囤,角圆一族…报图1995~2 确触拉姚 0 在离散数学教材图论一章中,一般只介绍了判定一个无向连通图是否为欧拉图的方法,而对于如何确定欧拉图中的欧拉回路,没有介绍,对于较简单的图,确定欧拉回路很容易但是, 对于更复杂的图,怎样能迅速,准确的找出欧拉回路,这里介绍一种方法. 定义:对于连通图G,若存在一条简单回路,通过G的所有的边,则称这条回路为G的欧拉回路,具有欧拉回路的图称为欧拉图. 定理:无向连通图G是欧拉图的充分必要条件是G的每个结点度数均为...

确定欧拉回路的一种方法欧拉目踌连通囤,角圆一族…报图1995~2 确触拉姚 0 在离散数学教材图论一章中,一般只介绍了判定一个无向连通图是否为欧拉图的方法,而对于如何确定欧拉图中的欧拉回路,没有介绍,对于较简单的图,确定欧拉回路很容易但是, 对于更复杂的图,怎样能迅速,准确的找出欧拉回路,这里介绍一种方法. 定义:对于连通图G,若存在一条简单回路,通过G的所有的边,则称这条回路为G的欧拉回路,具有欧拉回路的图称为欧拉图. 定理:无向连通图G是欧拉图的充分必要条件是G的每个结点度数均为偶数. 问题:已知图G(V,E)是欧拉图,试在图G中确定一条欧拉回路. 由假设,对于任一结点V0?V,deg(vo)?0,所以_定可以找到e=<o,>?E,若-= .v.,则找到了G的一条回路.否则,由于de~(v)为偶数.一定可以找到e2=<vt,V2>?E,且e2 ?e.若v:=vo,则找到了G的一条回路.否则,又由于deg(v)为偶数,可以找到ea=<v:,Vs >6E,且e,?e2,?e”若v,=,则找到G的一条回路.……如此进行下去,每边仅取一次, 并且每到一结点就沿着该结点的关联边中没走过的一条边走,只有当没有其它选择时才选未走过的边所构成子图的割边走.因为E是有限集,故一定存在ete2”*-e,使e-的终点为V0,从而构成G的一条欧拉回路C:Voe1v1e2…VjeI+1..?V一1envo. 由此可得以下算法: 一 ,分别为结点vc?V建立与之相关联的边的集合E={<v,1’vJ2>一)i=0,1,2…fi--1 建立集合时若有与vt相关联的割边应将其放在最后,每连只应出现在一个边集E中. 二,程序流程 1.1i 2.若E-为空集,转到7 3.显示Et中的第一个元素<vVt> 4.从集合E-中删除元素<V-…V> 5.t=i 6.转到2 7.程序结束若用此方法确定欧拉回路,那么我们不仅能迅速,准确地找出一个欧拉图中的欧拉回路, 而且改变E-中元素的顺序,还可以将该图中各种不同的欧拉回路一一找出来. 参:考文献:J.A捧迪VSR.默蒂着《图论及其应用》 1994年l2月20日收稿一一 32一

                    本文档为【确定欧拉回路的一种方法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

确定欧拉回路的一种方法

你可能还喜欢