【图论】欧拉路和哈密顿图

更新于 分类于 ， 阅读次数： 本文字数： 2k 阅读时长 ≈ 2 分钟

欧拉路的部分包括代码，哈密顿图是离散数学的内容

欧拉道路&欧拉回路

经过每条边且一个边只走一遍，区别是一个是回路一个是道路

理论

  • 无向连通图的充分必要条件
    • 欧拉道路：度数为奇数的节点数=0或2
    • 欧拉回路：没有奇数度的节点
  • 有向连通图的充分必要条件
    • 欧拉道路：所有点入度=出度 or 有一个点入度=出度+1，有一个点出度=入度+1，其余入度=出度
    • 欧拉回路：所有点入度=出度
  • 构造：不断删边直到成为零图，删边的原则是若只有割边走割边，否则绝不走割边

方法

dfs（非递归版）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
stack<int> stk, ans; // dfs栈和答案栈
bool vst[M]; // 记录边是否访问过
void Euler()
{
	stk.push(1); // 起点
	while (!stk.empty())
	{
		int cur = stk.top();
		int i = head[cur];
		while (i && vst[i])
			i = edge[i].nxt; 
		if (i) // 找到下一条能走的路
		{
			stk.push(edge[i].to);
			vst[i] = vst[i ^ 1] = true;
			head[cur] = edge[i].nxt;
		}
		else
		{ // 与x相连的所有边均已访问，模拟回溯过程，并记录
			stk.pop();
			ans.push(cur); // 记录答案
		}
	}
}

Hierholzers

求欧拉道路，倒序输出，字典序最小

1
2
3
4
5
6
7
8
9
10
11
// 将起点设为1，若找到奇数度的节点就设它为起点
void dfs(int x)
{
	for (int i = 1; i <= n; i++)
		if (g[x][i])
		{
			g[x][i]--, g[i][x]--;
			dfs(i);
		}
	ans.push(x);
}

Fluery

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
stack<int> stk;
bool vst[M]; // 边是否访问过
void dfs(int u)
{
	stk.push(u);
	for (int i = head[u]; i; i = edge[i].nxt)
	{
		if (vst[i])
			continue;
		vst[i] = vst[i ^ 1] = true;
		dfs(edge[i].to);
		break;
	}
}
void Fleury(int st)
{
	stk.push(st);
	while (!stk.empty())
	{
		bool flag = false;
		int cur = stk.top();
		stk.pop();
		for (int i = head[cur]; i; i = edge[i].nxt)

			if(!vst[i])
			{
				flag = true;
				break;
			}
		if (!flag)
			printf("%d\n", u);
		else
			dfs(u);
	}
}

哈密顿图

  • 哈密顿道路：经过每个节点的基本道路

  • 哈密顿圈：经过每个节点的回路

  • 哈密顿图：具有哈密顿圈的图

  • 必要条件：

    • 哈密顿图$G=(V, E)\Rightarrow 任意任意V$ 的非空子集SS 都有ω(G−S)<=∣S∣\omega(G-S)<=|S|
    • 哈密顿圈CC ， ∑i=1n(i−2)(fi(1)−fi(2))=0\sum_{i=1}^{n}(i-2)\left(f_{i}^{(1)}-f_{i}^{(2)}\right)=0，其中 fi(1)f_{i}^{(1)} 和 fi(2)f_{i}^{(2)} 分别是含在圈 CC 内部和外部的 ii 度面的数目。

  • 充分条件：

    • n≥3n\geq 3 的简单图，∀u,v∈V,f(u)+f(v)≥n⇒\forall u,v \in V,f(u)+f(v)\geq n\Rightarrow 哈密顿图
    • nn 阶简单图∀u,v∈V,f(u)+f(v)≥n−1⇒\forall u,v \in V,f(u)+f(v)\geq n-1\Rightarrow 图中有哈密顿道路

  • 充要条件：简单图是哈密顿图⇔\Leftrightarrow图的闭包图是哈密顿图

分枝界定法

精确解，不复杂的图

  • 消去操作：每行找最小元，同行减去；每列找最小元，同列减去；减去的数累和得到下界。
  • 第一行找最小元，分类讨论：
    • 包含在最优解中：
      • 将所在行列删去，最小元对称位置（指原矩阵中的对称位置）的元设为正无穷
      • 继续操作剩下的矩阵
    • 不包含在最优解中：查看当前值是否最优，不是的话暂停搜索
      • 将该元设为正无穷
      • 对剩下矩阵进行消去操作
  • 重复以上操作，每次都选取当前的最优解