~/posts/graph-and-eulerian-tours.md

图、欧拉回路和树

2026-02-18 11 分钟 · 5048 字11 min · 5048 words graph / mathematics / algorithm graphmathematicsalgorithm
目录Contents

图

什么是图(graph)?图是由顶点(vertex/node)和边(edge)组成的数学对象。假设我们有一个图,那么它可以表示为,其中是顶点的集合,是边的集合。每条边连接两个顶点。例如,考虑一个简单的图:

text
       A
      / \
     B   C
      \ /
       D

在这个图中,顶点集合,边集合。图即为这些顶点和边的集合。 图可以是有向的或无向的。在有向图中,边有方向,例如从顶点到顶点的边表示为,而在无向图中,边没有方向,例如表示连接和的边。 度数(degree)是指一个顶点连接的边的数量。在无向图中,顶点的度数是2,因为它连接了两条边和。在有向图中,我们区分入度(in-degree)和出度(out-degree)。入度是指有多少条边指向该顶点,出度是指有多少条边从该顶点出发。 在接下来的讨论中,如果没有特别说明,我们将默认图是无向的,并且两个顶点之间最多有一条边。

度数之和

一个重要的性质是图中所有顶点的度数之和等于边数的两倍。也就是说,如果我们将图中的每条边计数两次(因为每条边连接两个顶点),我们就得到了所有顶点的度数之和。数学上可以表示为:

这个性质在证明图的各种定理时非常有用。

路径、途径、环、回路

路径(path)是指一系列边的序列,任意边的终点与下一条边的起点相同,并且路径中的所有边和顶点都是不同的。例如,在上面的图中,路径是一个有效的路径。数学上,我们可以将它表示为,其中是路径中的顶点。路径的长度是路径中边的数量,在这个例子中,路径的长度是2。数学上,我们定义长度为,其中是路径中顶点的数量。每条路径包含个顶点和条边。 途径(walk)是指一系列边的序列,任意边的终点与下一条边的起点相同,但途径中的边和顶点可以重复。例如,在上面的图中,途径是一个有效的途径。 环(cycle)是指一条路径,其中起点和终点相同,并且除了起点和终点外,所有顶点都不相同。例如,在上面的图中,环是一个有效的环。 回路(tour)是指一条途径,其中起点和终点相同,并且除了起点和终点外,但是顶点可以相同,也就是说可以有重复的边和顶点。

连通性

一个图是连通的,如果对于图中的任意两个顶点,都存在一条路径连接它们。例如,在上面的图中,顶点和之间存在路径,所以这个图是连通的。如果一个图不是连通的,那么它被称为非连通的。例如,如果我们将上面的图分成两个部分,一个部分包含顶点和,另一个部分包含顶点和,那么这个图就是非连通的。

使用C++语言实现图

我们可以使用邻接表(adjacency list)来表示图。邻接表是一种常用的数据结构,用于存储图中的边。对于每个顶点,我们维护一个列表,列出与该顶点相邻的所有顶点。例如,下面是一个简单的图:

text
       A
      / \
     B   C
      \ /
       D

我们可以这样表示这个图的邻接表:

text
A: B, C
B: A, D
C: A, D
D: B, C

在C++中,我们可以用一个vector<vector<char>>来表示邻接表,其中每个元素是一个顶点的邻接列表。例如:

cpp
 1#include <iostream>
 2#include <vector>
 3using namespace std;
 4
 5int main() {
 6    int n = 4; // 顶点数量
 7    vector<vector<char>> adjList(n);
 8
 9    // 添加边
10    adjList[0].push_back('B'); // A-B
11    adjList[0].push_back('C'); // A-C
12    adjList[1].push_back('A'); // B-A
13    adjList[1].push_back('D'); // B-D
14    adjList[2].push_back('A'); // C-A
15    adjList[2].push_back('D'); // C-D
16    adjList[3].push_back('B'); // D-B
17    adjList[3].push_back('C'); // D-C
18
19    // 输出邻接表
20    for (int i = 0; i < n; i++) {
21        cout << "Vertex " << i << ": ";
22        for (char neighbor : adjList[i]) {
23            cout << neighbor << " ";
24        }
25        cout << endl;
26    }
27
28    return 0;
29}

由此,我们可以使用邻接表来表示图,并且可以方便地进行各种图的操作,例如添加边、删除边、遍历图等。 例如,想要删除边,我们可以在邻接表中删除顶点在的邻接列表中的出现,以及顶点在的邻接列表中的出现。

cpp
1// 删除边 A-B
2adjList[0].erase(remove(adjList[0].begin(), adjList[0].end(), 'B'), adjList[0].end()); // 从A的邻接列表中删除B
3adjList[1].erase(remove(adjList[1].begin(), adjList[1].end(), 'A'), adjList[1].end()); // 从B的邻接列表中删除A

Königsberg七桥问题

Königsberg七桥问题是一个著名的数学问题,起源于18世纪的普鲁士城市Königsberg(现在的俄罗斯加里宁格勒)。这个城市被普雷戈尔河分成了四个部分,并且有七座桥连接这些部分。问题是:是否存在一条路径,可以通过每座桥一次且仅一次,最终回到起点?

text
    A ----+
   / \    |
   \ /    |
    B ----D
   / \    |
   \ /    |
    C ----+

在这个图中,顶点、、和分别代表Königsberg的四个部分,而边代表连接这些部分的七座桥。我们可以看到,顶点的度数是3,顶点的度数是3,顶点的度数是3,顶点的度数是3。根据前面提到的性质,图中所有顶点的度数之和是12,而边数是7,所以满足。 欧拉回路(Eulerian tour)是指一条回路,其中每条边恰好被访问一次。对于Königsberg七桥问题,我们需要找到一条欧拉回路。

欧拉回路的存在条件

对于无向图来说,如果一个顶点被访问,那么必然要从一条边进入这个顶点,并且要从另一条边离开这个顶点。因此,如果一个图存在欧拉回路,那么每个顶点的度数必须是偶数。反过来说,如果一个图的每个顶点的度数都是偶数,并且图是连通的,那么我们可以构造一条欧拉回路。 有如下定理: 定理:一个无向图存在欧拉回路当且仅当图是连通的,并且每个顶点的度数都是偶数。 我们给出一个算法来构造欧拉回路:

  1. 从任意一个顶点开始,沿着边走,直到回到起点。
  2. 如果在这个过程中访问了所有的边,那么我们就得到了一个欧拉回路。
  3. 如果还有未访问的边,那么我们从回路中任意一个顶点出发,沿着未访问的边走,直到回到这个顶点。
  4. 将这个新的回路插入到之前的回路中。
  5. 重复步骤3和4,直到访问了所有的边。

接下来我们证明这个算法确实构造出了一个欧拉回路。

  1. 首先,因为每个顶点的度数都是偶数,因此我们可以从任意一个顶点出发,沿着边走,直到回到起点。这是因为每次进入一个顶点,我们都可以找到一条边离开这个顶点。
  2. 我们将步骤1中访问的边标记为已访问。移除这些边后,图可能会变成非连通的,但每个顶点的度数仍然是偶数。假设产生了一系列子图,其中每个子图都是连通的,并且每个顶点的度数仍为偶数。
  3. 对于每个子图,我们可以从回路中任意一个顶点出发,沿着未访问的边走,直到回到这个顶点。这是因为每个顶点的度数都是偶数,因此我们可以找到一条边离开这个顶点。
  4. 将这个新的回路插入到之前的回路中,我们得到了一个更长的回路。重复这个过程,直到访问了所有的边,我们就得到了一个欧拉回路。

由此,我们证明了如果一个无向图是连通的,并且每个顶点的度数都是偶数,那么它存在欧拉回路。对于Königsberg七桥问题,由于每个顶点的度数都是3(奇数),因此不存在欧拉回路,也就是说不存在一条路径可以通过每座桥一次且仅一次,最终回到起点。

用C++语言实现欧拉回路算法

我们可以使用深度优先搜索(DFS)来实现欧拉回路算法。 我们可以先用一个伪代码来描述这个算法:

text
FindTour(G, visited, s): // 从点s出发,找到任意回路,并避开所有已访问的边
    tour = empty list
    if there is an edge (s, t) in G that is not visited
        mark (s, t) as visited
        tour = FindTour(G, visited, t)
    tour = tour + s
    return tour
Euler(G, s):
    visited = 2D array initialized to false
    tour = FindTour(G, visited, s)
    let G_1, G_2, ..., G_k be the subgraphs of G after removing the edges in tour
    EulerTour = tour
    for each G_i:
        if G_i has edges:
            let v be a vertex in G_i that is also in tour
            newTour = Euler(G, visited, v)
            EulerTour = insert newTour into EulerTour at the position of v
    return EulerTour

以下是一个示例代码:

cpp
 1#include <iostream>
 2#include <vector>
 3using namespace std;
 4
 5vector<int> FindTour(const vector<vector<int>>& graph, vector<vector<bool>>& visited, int s) {
 6    vector<int> tour;
 7    int t = -1;
 8    for (int i : graph[s]) {
 9        if (!visited[s][i]) { // 如果边(s, i)未访问
10            visited[s][i] = visited[i][s] = true; // 标记边(i, s)为已访问(无向图)
11            t = i;
12            break;
13        }
14    }
15    if (t != -1) tour = FindTour(graph, visited, t); // 继续从t出发寻找回路
16    else return vector<int>(); // 如果没有未访问的边,返回空回路
17    tour.push_back(s); // 将当前顶点添加到回路中
18    return tour;
19}
20
21vector<int> Euler(const vector<vector<int>>& graph,int s) {
22    int n = graph.size();
23    vector<vector<bool>> visited(n, vector<bool>(n, false)); // 初始化访问状态
24    vector<int> tour = FindTour(graph, visited, s); // 找到初始回路
25
26    // 处理剩余的子图
27    for (int i = 0; i < n; i++) {
28        for (int j : graph[i]) {
29            if (!visited[i][j]) { // 如果还有未访问的边
30                vector<int> newTour = FindTour(graph, visited, i); // 从未访问的边出发找到新的回路
31                // 将newTour插入到tour中
32                auto it = find(tour.begin(), tour.end(), i);
33                tour.insert(it, newTour.begin(), newTour.end());
34            }
35        }
36    }
37    return tour;
38}

树

树(tree)是一种特殊的图,如下图所示:

text
       A
      / \
     B   C
    / \
   D   E

定义

如何定义树?根据上图的特征,我们可以提出这些定义:

  • 树是一个连通的无向图,并且没有环
  • 树是一个连通的无向图,并且边数等于顶点数减一
  • 树是一个无向图,并且任意两个顶点之间有且仅有一条路径
  • 树是一个连通的无向图,并且去掉任意一条边都会变成非连通的
  • 树是一个连通的无向图,并且连接任意两个顶点都会产生一个环

这些定义都是等价的,我们可以从其中一个定义出发,推导出其他定义。例如,如果我们从第一个定义出发,假设树是一个连通的无向图,并且没有环,那么我们可以证明树满足其边数等于顶点数减一的性质。 我们先来证明一个引理:

引理:如果一个顶点在图中度数为一,那么去掉这个顶点和与之相连的边后,图仍然是连通的。

证明:对于,因为是连通的,所以存在一条路径连接和。如果这条路径不经过,那么去掉后,这条路径仍然存在,因此和仍然是连通的。如果这条路径经过,那么我们可以将这条路径分成两段:从到的部分和从到的部分。因为的度数为一,所以只有一条边连接,因此我们可以直接连接和,形成一条新的路径。因此,无论哪种情况,去掉顶点后,图仍然是连通的。

现在我们来证明树满足边数等于顶点数减一的性质。我们使用数学归纳法来证明这个结论。

定理:如果是一个树,那么。

证明:

  • 基础情况:当时,树只有一个顶点,没有边,因此,结论成立。
  • 归纳假设:假设对于任意一个树,如果,那么。
  • 归纳步骤:现在考虑一个树,其中。因为是一个树,所以它至少有一个顶点的度数为一。根据引理,去掉这个顶点和与之相连的边后,得到一个新的图,其中。根据归纳假设,。因为我们去掉了一个顶点和一条边,所以。因此,,结论成立。

那么反过来是否成立呢?

定理:如果一个连通的无向图满足,那么是一个树。

证明:

  • 基础情况:当时,图只有一个顶点,没有边,因此,结论成立。
  • 归纳假设:假设对于任意一个连通的无向图,如果,并且,那么是一个树。
  • 归纳步骤:现在考虑一个连通的无向图,其中,并且。可以算出所有度数之和为。故平均度数为。因此,图中至少有一个顶点的度数为一。去掉这个顶点和与之相连的边后,得到一个新的图,其中,并且。根据归纳假设,是一个树。因为我们去掉了一个顶点和一条边,所以也是一个树。因此,我们证明了如果一个连通的无向图满足,那么是一个树。

因此,我们得到了树的一个重要性质:一个连通的无向图是树当且仅当它的边数等于顶点数减一。

平面图和完全图

**平面图(planar graph)是指可以在平面上绘制的图,并且在绘制过程中没有边相交。**例如,下面的图是一个平面图:

text
       A
      / \
     B   C
    / \
   D   E

**完全图(complete graph)是指每对不同的顶点之间都有一条边连接的图。**例如,下面的图是一个完全图:

text
       A
      /|\
     B-C-D
      \|/
       E

完全图是指有个顶点的完全图,其中每对不同的顶点之间都有一条边连接。因此,完全图的边数为,因为每对不同的顶点之间都有一条边连接。 平面图和完全图之间有一个重要的关系:对于,完全图不是平面图。它的证明之后会谈到。

2026年2月18日。

gitalk --repo Huaji-tye2007/MyBlog-Comments

滚动到这里时加载评论…Comments load when you scroll here…