周报

欧拉通路/欧拉回路

2020年3月29日

欧拉图

经过图（无向图或有向图）中每条边一次且仅一次并且行遍图中每个顶点的回路（通路），称为欧拉回路（欧拉通路）。存在欧拉回路的图，称为欧拉图。具有欧拉通路但不具有欧拉回路的图称为半欧拉图。回路是指从一个点出发又回到那个点，通路不对终点有什么要求。

定理/判别方法

定理都摘自离散数学书。

  • 无向图

无向图G有欧拉回路，当且仅当G是连通图且无奇度顶点。

无向图G有欧拉通路、但无欧拉回路，当且仅当G是连通图且恰好有两个奇度顶点。这两个奇度顶点是欧拉通路的端点。

  • 有向图

有向图D有欧拉回路，当且仅当D是连通的且每个顶点的入度等于出度。

有向图D有欧拉通路、但无欧拉回路，当且仅当D是连通的，且除了两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。任何欧拉通路以前一个顶点为终点，以后一个顶点为始点。

关于证明，可以感性的想一想，对于无向图的欧拉通路，假如顶点的度数为偶数，那么就一定能够“通过”这个顶点，而不是死胡同。假如每个顶点都满足这个性质，那么最终就会回到起点。其他的也都类似。后面的如何求欧拉通路/回路也能帮助理解。（离散数学书上都没给完整证明）

如何求得欧拉通路/欧拉回路

仅针对有向图欧拉回路来说明了。（无向图类比）

  • 首先肯定要判断是否存在欧拉通路。利用上面的判定方法加油判断。

例如这样的图就是不行的，因为点4和点5的入度不等于出度。（点1为出发点）

这样的就是ok的。

  • 判断完成之后就开始找欧拉通路。这里使用dfs。从起点开始，遍历图，则必定会重新回到起点。

那么可能会遇到这样的情况：（第一次搜索到底，必定到达根节点）

在dfs点4的时候，先走向了点5，如何回到了起点。得到了路径1 2 3 4 5 6 7 8 1

然后继续从点4dfs，走向了点9。变成了下面这样：

如何将这两个环拼起来呢。不难发现，输出路径的时候先走点9，然后回到点4，再走向点5就能解决问题。

对于更复杂的图，一样能够解决问题。例如下面这张图，环上有环：

路径可以是这样：

是不是感觉听懂了，但是仔细一想这个dfs挺难写的。那就请忘记上面的，看看下面这个大佬的模板吧(ㄒoㄒ)，实在是tql。其中每条边在被使用之后，终点被赋值为-1。printf倒序输出经过的点，可以使用一个队列，实现正序输出。

vector<int> edge[MAXN];
void euler(int index)
{
    for (int i = 0; i < edge[index].size(); i++)
    {
        tmp = edge[index][i];
        if (tmp == -1)
            continue;
        edge[index][i] = -1;
        euler(tmp);
    }
    printf("%d\n", index);
}

POJ-2230 Watchcow

Bessie's been appointed the new watch-cow for the farm. Every night, it's her job to walk across the farm and make sure that no evildoers are doing any evil. She begins at the barn, makes her patrol, and then returns to the barn when she's done......

题目说每条路必须走两次，且方向不同，相当于一条无向边变成两条有向边。

#include <cstdio>
#include <vector>
//#include <queue>
#define MAXN 10005
#define MAXM 100005
using namespace std;
int n, m;
vector<int> edge[MAXN];
//queue<int> q;
void euler(int index)
{
	int tmp;
	for (int i = 0; i < edge[index].size(); i++)
	{
		tmp = edge[index][i];
		if (tmp == -1)
			continue;
		edge[index][i] = -1;
		euler(tmp);
	}
	//q.push(index);
	printf("%d\n", index);
}
int main(void)
{
	while (~scanf("%d%d", &n, &m))
	{
		for (int i = 0; i < m; i++)
		{
			static int a, b;
			scanf("%d%d", &a, &b);
			edge[a].push_back(b);
			edge[b].push_back(a);
		}
		euler(1);
		//while (!q.empty())
		//{
		//	printf("%d\n", q.front());
		//	q.pop();
		//}
		for (int i = 0; i < n; i++)
		{
			edge[i].clear();
		}
	}
	return 0;
}

Views: 291

发表评论