《欧拉回路性质与应用探究》由会员分享，可在线阅读，更多相关《欧拉回路性质与应用探究（40页珍藏版）》请在金锄头文库上搜索。
1、欧拉回路性质与应用探究欧拉回路与七桥问题欧拉回路是最古老的图论问题之一，它诞 生于十八世纪的哥尼斯堡。当时城中有七座桥，人们想从某个位置出 发，不重复地走遍每一座桥，最后回到出 发点。这便是最初的欧拉回路问题。相关概念欧拉回路 不重复地经过每条边的回路。 欧拉路径 不重复地经过每条边的路径。 欧拉图 存在欧拉回路的图。半欧拉图 存在欧拉路径的图。无向欧拉图的判定无向图存在欧拉回路的充要条件： 连通且没有奇点。无向图存在欧拉路径的充要条件： 连通且奇点个数为2。有向欧拉图的判定有向图存在欧拉回路的充要条件： 基图连通且所有顶点入度等于出度。有向图存在欧拉路径的充要条件： 基图连通且存在某顶点入度
2、比出度大1， 另一顶点出度比入度大1，其余顶点入度 等于出度。求无向图欧拉回路的算法1.在图中任意找一个回路C；2.将图中属于C的边删除；3.在残留图的各个极大连通分量中求欧拉回路；4.将各极大连通分量中的欧拉回路合并到C上。例题一 单词游戏有N个盘子，每个盘子上写着一个仅由小 写字母组成的英文单词。你需要给这些盘子按照合适的顺序排成一 行，使得相邻两个盘子中，前一个盘子上 面单词的末字母等于后一个盘子上面单词 的首字母。请你编写一个程序，判断是否能达到这一 要求。如果能，请给出一个合适的顺序。 样例malformmouseacm样例malformmouseacmmmmm模型1将每个盘子看作一
3、个顶点。如果盘子B能连接在盘子A后面，那么从A 向B连一条有向边。模型1问题转化为在图中寻找一条不重复地经过 所有顶点的路径，即哈密尔顿路。但是，求哈密尔顿路是一个十分困难的问 题，这样的建模没有给解题带来任何便 利。我们必须另辟蹊径。模型2以26个英文字母作为顶点。对于每一个单词，在图中从它的首字母向 末字母连一条有向边。模型2问题转化为在图中寻找一条不重复地经过 所有边的路径，即欧拉路径。这个问题能够在O(|E|)时间内解决。小结比较以上两个模型，模型1过于直接，模 型2则打破了“顶点表示元素，边表示元素 之间关系”的思维定势，将元素表示在边上 ，而顶点则起到连接各个元素的作用。例题二 中
4、国邮递员问题A城市的交通系统由若干个路口和街道组 成，每条街道都连接着两个路口。所有街道都只能单向通行。每条街道都有一个长度值。例题二 中国邮递员问题一名邮递员传送报纸和信件，要从邮局出 发经过他所管辖的每一条街道，最后返回 邮局。每条街道可以经过不止一次。他应该如何安排自己的路线，使得走过的 总长度最短呢？样例路线总长度为14分析容易看出题目给出的是一个图的模型。在有向图中找一条权值最小的回路，使得 它经过图中的每条边至少一次。分析如果问题有解，那么一定满足以下条件：1、基图连通；2、不存在某个顶点入度为0或出度为0。分析为了简化问题，我们暂时不考虑边的权值。问题的核心条件是：“每条边经过至
5、少一次”。转化为如下形式：将图中的某些边拆分成若 干条平行边，使得图中存在欧拉回路。分析设顶点v的入度与出度之差为p(v)。对于p(v)0的顶点，需要增加p(v)条从v 出发的边；对于p(v)0网络的源点，向网络发出 p(v)单位的流；p(v)1)，则路径中进入vk的次数比 离开vk的次数大1。而vk的入度等于出度 ，所以此时一定存在一条离开vk的边没有 被访问过，这与游戏结束的条件不符！v1vk进入vk的次数：离开vk的次数：分析假设某次游戏过程在图G中对应回路C。将C从图G中删去得到残留图G0。显然，G0中v1的度为0（否则游戏不会结 束）。若G0中边数为0，那么这是一次失败的游 戏过程；
6、否则，G0至少存在一个不经过v1的回路。分析游戏者能够获胜，当且仅当图G中存在一 条不经过v1的回路。我们只需任意找一条这样的回路，将其从 图G中删去，然后在残留图中寻找一条欧 拉回路即可。如果不存在，则游戏必然失败。总结欧拉回路的应用主要有以下几个方面：通过巧妙的构图，将问题转化为在图中寻 找欧拉回路；利用欧拉图的性质作为解题的突破口，使 得看似棘手的问题迎刃而解；通过研究欧拉图的各种变形来解决问题。总结欧拉回路的优点是：简洁、清晰应用范围广算法高效欧拉回路的缺点是：思维难度大欧拉回路相关试题Depot Rearrangement（CEOI 2005 ）Primitivus（POI 1999 Stage III）千年盛典（CTSC 2003）Ouroboros Snake（MCERC 2000）Mosaic（Ural State 2001）
