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

欧拉回路性质与应用探究 湖南师大附中 仇荣琦 欧拉回路与七桥问题 欧拉回路是最古老的图论问题之一，它诞生于十八世纪的哥尼斯堡。 当时城中有七座桥，人们想从某个位置出发，不重复地走遍每一座桥，最后回到出发点。这便是最初的欧拉回路问题 。 相关概念 欧拉回路　不重复地经过每条边的回路。 欧拉路径　不重复地经过每条边的路径。 欧拉图　　存在欧拉回路的图。 半欧拉图　存在欧拉路径的图。 无向欧拉图的判定 无向图存在欧拉回路的充要条件：连通且没有奇点。 无向图存在欧拉路径的充要条件：连通且奇点个数为2。 有向欧拉图的判定 有向图存在欧拉回路的充要条件：基图连通且所有顶点入度等于出度。 有向图存在欧拉路径的充要条件：基图连通且存在某顶点入度比出度大1，另一顶点出度比入度大1，其余顶点入度等于出度。 求无向图欧拉回路的算法 在图中任意找一个回路C； 将图中属于C的边删除； 在残留图的各个极大连通分量中求欧拉回路； 将各极大连通分量中的欧拉回路合并到C上。 例题一　单词游戏 有N个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。 你需要给这些盘子按照合适的顺序排成一行，使得相邻两个盘子中，前一个盘子上面单词的末字母等于后一个盘子上面单词的首字母。 请你编写一个程序，判断是否能达到这一要求。如果能，请给出一个合适的顺序。 样例 malform mouse acm 样例 malform mouse acm m m m m 模型1 将每个盘子看作一个顶点。 如果盘子B能连接在盘子A后面，那么从A向B连一条有向边。 模型1 问题转化为在图中寻找一条不重复地经过所有顶点的路径，即哈密尔顿路。 但是，求哈密尔顿路是一个十分困难的问题，这样的建模没有给解题带来任何便利。我们必须另辟蹊径。 模型2 以26个英文字母作为顶点。 对于每一个单词，在图中从它的首字母向末字母连一条有向边。 模型2 问题转化为在图中寻找一条不重复地经过所有边的路径，即欧拉路径。 这个问题能够在O(|E|)时间内解决。 小结 比较以上两个模型，模型1过于直接，模型2则打破了“顶点表示元素，边表示元素之间关系”的思维定势，将元素表示在边上，而顶点则起到连接各个元素的作用。 例题二　中国邮递员问题 A城市的交通系统由若干个路口和街道组成，每条街道都连接着两个路口。 所有街道都只能单向通行。 每条街道都有一个长度值。 例题二　中国邮递员问题 一名邮递员传送报纸和信件，要从邮局出发经过他所管辖的每一条街道，最后返回邮局。每条街道可以经过不止一次。 他应该如何安排自己的路线，使得走过的总长度最短呢？ 样例 路线总长度为14 分析 容易看出题目给出的是一个图的模型。 在有向图中找一条权值最小的回路，使得它经过图中的每条边至少一次。 分析 如果问题有解，那么一定满足以下条件： 　1、基图连通； 　2、不存在某个顶点入度为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)0 p(v)=0 网络的汇点，从网络接收-p(v)单位的流； 网络的中间结点，接收的流量等于发出的流量。 分析 原问题转化为多源多汇的最大流问题。 我们可以通过附加超级源s和超级汇t的方法将其转化为单源单汇的经典最大流问题。 分析 下面我们考虑边的权值。 对于原图中的边e，将其费用值w(e)赋为对应边的长度； 其余的边不产生费用，将其费用值赋为0。 求网络中从s到t的最小费用最大流。 最后，我们只需根据各边的流量情况将原图进行改造，并在新图中求欧拉回路即可。 小结 本题的解答过程中，运用了欧拉图的一些性质对题目进行分析，通过联想、类比将问题对应到一个流网络模型上，并使用最小费用最大流算法解决问题。 拓展 如果将条件改成“所有街道都能够双向通行”，该如何解决？ 如果将条件改成“部分街道能够双向通行，部分街道只能单向通行”呢？ 例题三　赌博机 一台赌博机由n个整数发生器T1 ,T2,…,Tn组成。 Ti能够产生的整数集合为Si，Si是集合{1,2,…,n}的子集。 游戏开始时只有T1处于活动状态。 例题三　赌博机 设当前的活动发生器为Ti： 若Si≠Φ，游戏者可以在Si中选择一个数r，然后将r从Si中删除，且活动状态转移到Tr； 若Si=Φ，那么游戏结束。 例题三　赌博机 如果游戏结束时，最后一个活