欧拉回路

March 22, 2011

今天做了下SGU，发现第二题是欧拉回路，于是大喜，结果WA，最后发现对欧拉回路的理解还不够深刻，总结一下：

欧拉回路的模型：

本来来自欧拉的七桥问题：

用图论抽象就是：一副无向图，每条边只能通过一次，问是否存在一条路径经过所有的边，这样的路径叫欧拉路径，如果起点和终点相同，则成为欧拉回路。

欧拉路径存在的条件：

1.图是连通的；

2.奇数度的顶点只允许有0个(存在欧拉回路)或者2个(存在欧拉路径)。

算法思想：

对于每一个访问到的顶点，先解决这个顶点的欧拉回路问题，此时肯定还剩一条边，这条边上的另一个端点就是下个要访问的点，如此可以找到所有的欧拉回路。

因为奇数度顶点为2的问题可以转换为奇数度顶点为0的，所有下面只讨论欧拉回路的情况。(转换方法：设两个度为奇数的点为s和e，而且这两个点肯定是顶点和终点，则从s到e肯定存在某条路径，因为图是想通的，删去这条路径，则剩下的子图的顶点的度权威偶数，因为这条路径上除了s和e，其余点都又进又出，删去的度为2。这样，就把欧拉路径问题转换为了欧拉回路的问题。)

这里有几个问题可能比较难以想通，首先，在解决被访问到的欧拉回路问题时，能确保路径还能回到这一点？答案是肯定的，因为所有顶点度为偶数，如果从一个偶数度的点出去而回不来的话，说明这个顶点的两条路径出去的子图是不相通的，这样的话这两个子图的度的综合就要为奇数，这与先前设定是矛盾的。

所有，基本思想就是访问可访问的节点，对于每个节点，首先解决自己节点的欧拉回路问题，除了进来的边和要出去的边，这样等节点遍历完了，欧拉回路也就出来了。

代码如下：

void findEuler(int v)
{
    int i;
    for(i=0;i<N;++i)
    {
        if(connected(v,i)) 
        {
            delEdge(v,i);
            findEuler(i);
        }
    }
    euler[eulerPos++]=v;
 
}

至于有向图的欧拉回路问题，和上面类似。

如果一个有向图所有顶点的入度等于出度，则该图存在欧拉回路。如果有顶点x的出度比入度大1，y的入度比出度大1，其余顶点的入度等于出度，则存在从x到y的欧拉路径。

至于混合图，有待学习。。。