算法合集之《欧拉回路性质与应用探究》.ppt

《算法合集之《欧拉回路性质与应用探究》.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、欧拉回路性质与应用探究湖南师大附中仇荣琦欧拉回路与七桥问题欧拉回路是最古老的图论问题之一，它诞生于十八世纪的哥尼斯堡。当时城中有七座桥，人们想从某个位置出发，不重复地走遍每一座桥，最后回到出发点。这便是最初的欧拉回路问题。相关概念欧拉回路　不重复地经过每条边的回路。欧拉路径　不重复地经过每条边的路径。欧拉图　　存在欧拉回路的图。半欧拉图　存在欧拉路径的图。无向欧拉图的判定无向图存在欧拉回路的充要条件：连通且没有奇点。无向图存在欧拉路径的充要条件：连通且奇点个数为2。有向欧拉图的判定有向图存在欧拉回路的充要条件：基图连通且所有顶点入度等于出度。有向图存

2、在欧拉路径的充要条件：基图连通且存在某顶点入度比出度大1，另一顶点出度比入度大1，其余顶点入度等于出度。求无向图欧拉回路的算法在图中任意找一个回路C；将图中属于C的边删除；在残留图的各个极大连通分量中求欧拉回路；将各极大连通分量中的欧拉回路合并到C上。例题一　单词游戏有N个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子按照合适的顺序排成一行，使得相邻两个盘子中，前一个盘子上面单词的末字母等于后一个盘子上面单词的首字母。请你编写一个程序，判断是否能达到这一要求。如果能，请给出一个合适的顺序。样例malformmouseacm样例mal

3、formmouseacmmmmm模型1将每个盘子看作一个顶点。如果盘子B能连接在盘子A后面，那么从A向B连一条有向边。模型1问题转化为在图中寻找一条不重复地经过所有顶点的路径，即哈密尔顿路。但是，求哈密尔顿路是一个十分困难的问题，这样的建模没有给解题带来任何便利。我们必须另辟蹊径。模型2以26个英文字母作为顶点。对于每一个单词，在图中从它的首字母向末字母连一条有向边。模型2问题转化为在图中寻找一条不重复地经过所有边的路径，即欧拉路径。这个问题能够在O(

4、E

5、)时间内解决。小结比较以上两个模型，模型1过于直接，模型2则打破了“顶点表示元素，边表示元素之间关系

6、”的思维定势，将元素表示在边上，而顶点则起到连接各个元素的作用。例题二　中国邮递员问题A城市的交通系统由若干个路口和街道组成，每条街道都连接着两个路口。所有街道都只能单向通行。每条街道都有一个长度值。例题二　中国邮递员问题一名邮递员传送报纸和信件，要从邮局出发经过他所管辖的每一条街道，最后返回邮局。每条街道可以经过不止一次。他应该如何安排自己的路线，使得走过的总长度最短呢？样例路线总长度为14分析容易看出题目给出的是一个图的模型。在有向图中找一条权值最小的回路，使得它经过图中的每条边至少一次。分析如果问题有解，那么一定满足以下条件：1、基图连通；2、不存在

7、某个顶点入度为0或出度为0。分析为了简化问题，我们暂时不考虑边的权值。问题的核心条件是：“每条边经过至少一次”。转化为如下形式：将图中的某些边拆分成若干条平行边，使得图中存在欧拉回路。分析设顶点v的入度与出度之差为p(v)。对于p(v)>0的顶点，需要增加p(v)条从v出发的边；对于p(v)<0的顶点，需要增加-p(v)条到v结束的边；对于p(v)=0的顶点，需要增加相等数量的从v出发的边和到v结束的边。分析p(v)>0网络的源点，向网络发出p(v)单位的流；p(v)<0p(v)=0网络的汇点，从网络接收-p(v)单位的流；网络的中间结点，接收的流量等于发

8、出的流量。分析原问题转化为多源多汇的最大流问题。我们可以通过附加超级源s和超级汇t的方法将其转化为单源单汇的经典最大流问题。分析下面我们考虑边的权值。对于原图中的边e，将其费用值w(e)赋为对应边的长度；其余的边不产生费用，将其费用值赋为0。求网络中从s到t的最小费用最大流。最后，我们只需根据各边的流量情况将原图进行改造，并在新图中求欧拉回路即可。小结本题的解答过程中，运用了欧拉图的一些性质对题目进行分析，通过联想、类比将问题对应到一个流网络模型上，并使用最小费用最大流算法解决问题。拓展如果将条件改成“所有街道都能够双向通行”，该如何解决？如果将条件改成“

9、部分街道能够双向通行，部分街道只能单向通行”呢？例题三　赌博机一台赌博机由n个整数发生器T1,T2,…,Tn组成。Ti能够产生的整数集合为Si，Si是集合{1,2,…,n}的子集。游戏开始时只有T1处于活动状态。例题三　赌博机设当前的活动发生器为Ti：若Si≠Φ，游戏者可以在Si中选择一个数r，然后将r从Si中删除，且活动状态转移到Tr；若Si=Φ，那么游戏结束。例题三　赌博机如果游戏结束时，最后一个活动发生器是T1，并且所有Si=Φ，那么游戏者失败，否则获胜。对于一台给定的赌博机，请你判断能否获胜。如果能，给出一个获胜的策略。样例下图是一个能够获胜的赌博

10、机。一种选数方案为：T1T2T32133231样例下图则是一个不