欧拉回路

发表于 更新于 分类于 ，

1. 欧拉回路定义

从一个顶点出发沿着图的边前进，切好经过每条边一次并且回到顶点，我们称为该图是否含有欧拉回路

定理一： 连通多重图具有欧拉回路当前仅当他的每个顶点都有偶数度
定理二： 连通多重图具有欧拉通路当前仅当它恰有两个奇数度顶点

在欧拉通路里，两个具有奇数度的顶点在建立一条虚拟边，那么就可以实现每个顶点都是偶数度，从而形成一条欧拉回路

1.1 欧拉路的判断

  1. 判断欧拉通路是否存在的方法
  • 有向图：图连通，有一个顶点出度比入度大1，有一个顶点入度比出度大1，其余都是出度=入度。
  • 无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。
  1. 判断欧拉回路是否存在的方法
  • 有向图：图连通，所有的顶点出度=入度。
  • 无向图：图连通，所有顶点都是偶数度。

2. 路径求解

经常会有求欧拉回路的问题， 我们可以使用欧拉回路构造的方式解决

2.1 欧拉回路的构造（Hierholzer算法）

1
2
3
4
5
6
7
8
9
10
11
Euler(G) 
    circuit := 从 G 里任意节点开始，连续的遍历该节点的边，直到形成回路
    H := 删除这条回路后剩余的图G
    while H 还存在边
    begin
        subcircuit := 在既是H的顶点也是circuit边的端点处开始的H里找一条回路
        H := 删除subcircuit 的所有边和孤立点之后的H
        circute := 在circute适当顶点插入subcircuit
    end

    circute 即为所得欧拉回路

// TODO 待补充图片示例

2.2 佛勒里算法(Fleury)

G 为无向图
1、任取G中一个顶点$V_0$(如果是找欧拉通路，那么选任度为奇数的点),使$P_0=V_0$
2、假设沿$P_i= V_0e_1V_1e_2V_2…e_iV_i$ 走到顶点$v_i$,在下面的步骤中从$E(G) - {e_1e_2…e_i}$中选择$e_{i+1}$

  • $e_{i+1}$ 与 $e_i$ 相关联
  • 除非没有其他选择，否则$e_{i+1}$ 不应该是{$E(G) - {e_1e_2…e_i}$}中的桥

3、 当步骤2不能在进行时停止

2.2.1 桥

设无向图G(V,E)为连通图，若边集$E_l 属于 E$,在图中删除$E_l$所有边后形成的子图为非连通图，而删除$E_l$ 某一子集后得到的子图仍是连通图，那么说明$E_l$是图G的割边集

如果一条边就是那个割边集，那么我们说这条边为割边，或者称之为桥

2.2.2 桥的求解算法(TODO)

方案一：枚举去掉每个点的情况，DFS判断时间复杂度O(n^2)
方案二：Tarjan实现

3. LC示例

LC753: 破解保险箱

因为该题一定会存在欧拉回路

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
func crackSafe(n int, k int) string {

	if n <= 0 || k <= 0 {
		return ""
	}

	var buf bytes.Buffer
	if n == 1 {
		for i := 0; i < k; i++ {
			buf.WriteString(strconv.Itoa(i))
		}
		return buf.String()
	}

	// 记录接点是否被访问过
	visit := make(map[string]bool)

	// 从 0 * (n-1) 开始 遍历
	s := ""
	for i := 0; i < n-1; i++ {
		s += "0"
    }
    // 从 n-1 的0状态开始遍历
	dfs753(&buf, visit, s[:], k)
	buf.WriteString(s)
	return buf.String()
}

var count = 0

/*
 * visit 记录节点是否被访问过
 * s 是当前的状态
 */
func dfs753(buf *bytes.Buffer, visit map[string]bool, s string, k int) {
    // 这里用k是因为每个状态的下一个状态都有k中选择，所以直接依次遍历每种情况
    // 如果在其他图中，这个遍历的是和当前状态想关联的边的集合
	for i := 0; i < k; i++ {
		nei := s + strconv.Itoa(i)
		// 如果已经被访问过，那么继续
		if visit[nei] {
			continue
		}
        visit[nei] = true // 先记录该点所对应的状态边被访问过
        // 深度遍历以该点为交点的另一连通部分的访问路径
        dfs753(buf, visit, nei[1:], k)
        // 记录下该点
		(*buf).WriteString(strconv.Itoa(i))
	}
}

4. 参考链接