欧拉回路
March 22, 2011
今天做了下SGU,发现第二题是欧拉回路,于是大喜,结果WA,最后发现对欧拉回路的理解还不够深刻,总结一下:
欧拉回路的模型:
本来来自欧拉的七桥问题:
用图论抽象就是:一副无向图,每条边只能通过一次,问是否存在一条路径经过所有的边,这样的路径叫欧拉路径,如果起点和终点相同,则成为欧拉回路。
欧拉路径存在的条件:
1.图是连通的;
2.奇数度的顶点只允许有0个(存在欧拉回路)或者2个(存在欧拉路径)。
算法思想:
对于每一个访问到的顶点,先解决这个顶点的欧拉回路问题,此时肯定还剩一条边,这条边上的另一个端点就是下个要访问的点,如此可以找到所有的欧拉回路。
因为奇数度顶点为2的问题可以转换为奇数度顶点为0的,所有下面只讨论欧拉回路的情况。(转换方法:设两个度为奇数的点为s和e,而且这两个点肯定是顶点和终点,则从s到e肯定存在某条路径,因为图是想通的,删去这条路径,则剩下的子图的顶点的度权威偶数,因为这条路径上除了s和e,其余点都又进又出,删去的度为2。这样,就把欧拉路径问题转换为了欧拉回路的问题。)
这里有几个问题可能比较难以想通,首先,在解决被访问到的欧拉回路问题时,能确保路径还能回到这一点?答案是肯定的,因为所有顶点度为偶数,如果从一个偶数度的点出去而回不来的话,说明这个顶点的两条路径出去的子图是不相通的,这样的话这两个子图的度的综合就要为奇数,这与先前设定是矛盾的。
所有,基本思想就是访问可访问的节点,对于每个节点,首先解决自己节点的欧拉回路问题,除了进来的边和要出去的边,这样等节点遍历完了,欧拉回路也就出来了。
代码如下:
至于有向图的欧拉回路问题,和上面类似。
如果一个有向图所有顶点的入度等于出度,则该图存在欧拉回路。如果有顶点x的出度比入度大1,y的入度比出度大1,其余顶点的入度等于出度,则存在从x到y的欧拉路径。
至于混合图,有待学习。。。