资源描述：
《（王俊生）离散论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、关于欧拉图与哈密尔顿图的算法作者住俊生作者简介：内蒙古农业大学职业技术学院信息管理系软10件技术班王俊生摘要:关键字：1•哈密尔顿图2.环球世界1736年瑞士数学家欧拉发表了图论的第一篇著名论文“哥尼斯堡七桥问题”（下称七桥问题）。这个问题是这样的：哥尼斯堡城有一条横贯全城的普雷格尔河，城的各部分用七桥联结，每逢节假日，有些城市居民进行环城周游，于是便产生了能否“从某地出发，通过每桥恰好一次，在走遍了七桥后又返回到原处”的问题。在图8.1.1画出了哥尼斯堡城图，城的四块陆地部分以A,B,C,和D标记。欧拉巧妙地
2、把哥尼斯堡城图化为图8・1・2所示图G,他把陆地设为图G中的结点，把桥画成相应地联结陆地即结点的边。于是，通过哥尼斯堡城中每座桥恰好一次问题，等价于在图G中从某一结点出发找出一条链，它通过每条边恰好次后回到原出发结点,亦即等价于在图G中寻找一个圈，它通过G中每一条边恰好一次。AD欧拉在这篇论文中提出了一条简单准则，确定七桥问题是不能解的。下面就来讨论这个问题。定义8.1.1图G中的一圈（或回路），若它通G中的每一条边（或弧）恰好一次，则称该圈（或回路）为欧拉圈（或回路），具有这种圈（或回路）的图称为欧拉无向（或
3、有向）图。定理&1・1给定连通无向图G,G有欧拉圈oG中每个结点都是偶度结点。由定义&1・1可知，具有欧拉圈的图是欧拉图，故图G为欧拉图OG中每个结点都是偶度结点。由于七桥问题所对应的图中每个结点都是奇度结点，根据上述定理可知，七桥问题无解。定义8.1.2图G中的一条链（或路），若它通过G中的每条边（或弧）恰好一次，则称该链（或路）为欧拉链（或路）。定理8.1.2给定连通无向图G=,u9v^V且uHv,u与V间存在欧拉链OG中仅有W和v为奇度结点。定理&1・3给定弱连通有向图G,G有欧拉回路oG中的每
4、个结点的入度等于出度。给定弱连通有向图G=,w,vey且uHy,u与v存在欧拉路oG中唯有u和v的入度不等于岀度，且w的入度比其出度大于1和v的出度比其入度小于1（或者反之）。这两个定理的证明，可以看作是关于无向图的欧拉圈和欧拉链的推广。因为对于有向图的任意一个结点来说，如果入度与出度相等,则该结点为偶度结点；如果入度与出度之差为1时，该结点必是奇度结点，所以定理8.1.3和8.1.4与前面两个定理的证明类似。与欧拉圈和链（或回路和路）非常类似的问题是哈密尔顿圈和链（或回路和路）的问题。1859年，爱
5、尔兰数学家哈密尔顿（W.R.Hamilton）首先提出“环球周游”问题。他用一个正十二面体的20个顶点代表世界上20个大城市（见图8.1.4（a））,这个正十二面体同构于一个平面图（见图8.1.40）,平面图的定义稍后给出），要求旅游者能否找到沿着正十二面体的棱，从某个顶点（即城市）出发，经过每个顶点（即每座城市）恰好一次，然后回到出发顶点?这便是著名的哈密尔顿问题。按图8丄4（c）中所给的编号进行旅游，便是哈密尔顿问题的解。对于任何连通图也有类似的问题。定义8.1.3图G中的一圈（或回路），若它通过G中每个结
6、点恰好一次，则该圈（或回路）称为哈密尔顿圈（或回路），具有哈密尔顿圈（或回路）的图称为哈密尔顿无向（或有向）图。由该定义可知，完全图必是哈密尔顿图。定义8・1・4图G中的一链（或路），若它通过G中的每个结点恰好一次，则该链（或路）称为哈密尔顿链（或路）。哈密尔顿图尽管在形式上与欧拉图极其相似，但其结论上却有很大不同，至今还没有得到关于哈密尔顿图的非平凡的充要条件，这是图论尚未解决的主要问题之一。然而，还是有不少重要成果，下面给出几个必要和充分条件的定理。定理8丄5若连通图G=是哈密尔顿图，S是V的任意
7、真子集，则O（G・S）WISI。本定理给出是哈密尔顿图的一个必要条件（G是连通分支数）,但这个条件又不便于使用，因为它要求对G的结点集合的所有真子集进行验证。尽管如此，利用它还可以证明某些图不是哈密尔顿图。下面给出图G是哈密尔顿图的充分条件，这个结果是于1952年G.A.Dirac研究得到的。定理8・1・6给定简单图G=,IVI=n,若和5三〃/2,则G是哈密尔顿图。请注意，本定理给出的仅是充分条件，§是图G的最小度数。例如，十多边形显然是哈密尔顿图，但5=2并不M=5。F面给出图G是哈密尔顿图的充分
8、条件，这个结果是于1952年G.A.Dirac研究得到的。给定简单图G=9IVI=n,若心3和5R/2,则G是哈密尔顿图。请注意，本定理给出的仅是充分条件，§是图G的最小度数。例如，十多边形显然是哈密尔顿图，但5=2并不鼻=5oBondy和Chvatol于1969年证明了更强的充分条件。他们的方法是建立下面两个引理之上的O引理8.1.1给定图G=,IVI=n^3o若
