离散数学 7-4 欧拉图和汉.ppt

《离散数学 7-4 欧拉图和汉.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、7-4欧拉图和汉密尔顿图要求：1、理解欧拉图、汉密尔顿图的定义。2、掌握欧拉图的判定方法。3、会判断一些图不是汉密尔顿图。4、熟悉一些欧拉图和汉密尔顿图。一、欧拉图1、哥尼斯堡七桥问题ABCD近代图论的历史可追溯到18世纪的七桥问题—穿过哥尼斯堡城的七座桥，要求每座桥通过一次且仅通过一次。七桥问题等价于在图中求一条回路，此回路经过每条边一次且仅有一次。欧拉在1736年的论文中提出了一条简单的准则，确定了哥尼斯堡七桥问题是不能解的。2、欧拉图(Euler)如果无孤立结点图G上有一条经过G的所有边一次且仅一次的路径，则称该路径为图G的欧拉路径（Eulerwalk）。如果图G上有一

2、条经过G边一次且仅一次的的回路，则称该回路为图G的欧拉回路。具有欧拉回路的图称为欧拉图（Eulergraph）。定理7-4.1无向图G具有一条欧拉路，当且仅当G连通，并且有零个或两个奇数度结点。证明思路：1)先证必要性:G有欧拉路G连通且（有0个或2个奇数度结点）设G的欧拉路是点边序列v0e1v1e2…ekvk，其中结点可能重复，但边不重复。因欧拉路经过（所有边）所有结点，所以图G是连通的。对于任一非端点结点vi，在欧拉路中每当vi出现一次，必关联两条边，故vi虽可重复出现，但是deg(vi)必是偶数。对于端点,若v0=vk，则deg(v0)必是偶数，即G中无奇数度结点

3、。若v0≠vk，则deg(v0)必是奇数，deg(vk)必是奇数,即G中有两个奇数度结点。必要性证完。2)再证充分性:(证明过程给出了一种构造方法)G连通且（有0个或2个奇数度结点）G有欧拉路(1)若有2个奇数度结点,则从其中一个结点开始构造一条迹,即从v0出发经关联边e1进入v1,若deg(v1)为偶数,则必可由v1再经关联边e2进入v2,如此下去,每边仅取一次,由于G是连通的,故必可到达另一奇数度结点停下,得到一条迹L1:v0e1v1e2…ekvk。若G中没有奇数度结点,则从任一结点v0出发,用上述方法必可回到结点v0,得到一条闭迹。(2)若L1通过了G的所有边,L1就

4、是一条欧拉路。(3)若G中去掉L1后得到子图G’,则G’中每个结点度数都为偶数,因为原来的图G是连通的,故L1与G’至少有一个结点vi重合,在G’中由vi出发重复(1)的方法,得到闭迹L2。(4)当L1与L2组合,若恰是G,得欧拉路,否则重复(3),可得闭迹L3,依此类推可得一条欧拉路。充分性证完由于有了欧拉路和欧拉回路的判别准则，因此哥尼斯堡七桥问题立即有了确切的否定答案，因为从图中可以看到deg(A)＝5，deg(B)＝deg(C)＝deg(D)=3，故欧拉回路必不存在。定理7-4.1的推论无向图G具有一条欧拉回路，当且仅当G连通且所有结点度数皆为偶数。4、一笔画问题要

5、判定一个图G是否可一笔画出，有两种情况：一是从图G中某一结点出发，经过图G的每一边一次仅一次到达另一结点。另一种就是从G的某个结点出发，经过G的每一边一次仅一次再回到该结点。v1v2v3v4v5为欧拉路，有从v2到v3的一笔画。为欧拉回路，可以从任一结点出发，一笔画回到原出发点。5.定义7-4.2：给定有向图G，通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。可以将欧拉路和欧拉回路的概念推广到有向图中。6.定理7-4.2(1)有向图G为具有一条单向欧拉回路，当且仅当G连通，并且每个结点的入度等于出度。(2)有向图G有单向欧拉路，当且仅当G连通，并且恰有两

6、个结点的入度与出度不等，它们中一个的出度比入度多1，另一个入度比出度多1。证明思路与定理7-4.1类似例1有向欧拉图应用示例：计算机鼓轮的设计。鼓轮表面分成24=16等份，其中每一部分分别用绝缘体或导体组成，绝缘体部分给出信号0，导体部分给出信号1，在下图中阴影部分表示导体，空白体部分表示绝缘体，根据鼓轮的位置，触点将得到信息4个触点a,b,c,d读出1101(状态图中的边e13),转一角度后将读出1010(边e10)。问鼓轮上16个部分怎样安排导体及绝缘体才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二进制数信息。01111111100000001110abcd设有

7、一个八个结点的有向图，如下图所示。其结点分别记为三位二进制数{000，001，……，111}，设ai{0,1}，从结点a1a2a3可引出两条有向边，其终点分别是a2a30以及a2a31。该两条边分别记为a1a2a30和a1a2a31。按照上述方法，对于八个结点的有向图共有16条边，在这种图的任一条路中，其邻接的边必是a1a2a3a4和a2a3a4a5的形式，即是第一条边标号的后三位数与第二条边的头三位数相同。由于图中16条边被记为不同的二进制数，可见前述鼓轮转动所得到16个不同位置触点上的二进制信息，