图

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

1
2
3
4
5
  A
 / \
B   C
 \ /
  D

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

度数之和

一个重要的性质是图中所有顶点的度数之和等于边数的两倍。也就是说，如果我们将图中的每条边计数两次（因为每条边连接两个顶点），我们就得到了所有顶点的度数之和。数学上可以表示为：
$$\sum_{v \in V} \text{degree}(v) = 2|E|$$
这个性质在证明图的各种定理时非常有用。

路径、途径、环、回路

路径(path)是指一系列边的序列，任意边的终点与下一条边的起点相同，并且路径中的所有边和顶点都是不同的。例如，在上面的图中，路径$A \to B \to D$是一个有效的路径。数学上，我们可以将它表示为$P = {(v_1, v_2), (v_2, v_3), …, (v_{k-1}, v_k)}$，其中$v_i$是路径中的顶点。路径的长度是路径中边的数量，在这个例子中，路径$A \to B \to D$的长度是2。数学上，我们定义长度为$|P| = k - 1$，其中$k$是路径中顶点的数量。每条路径$P$包含$k$个顶点和$k-1$条边。
途径(walk)是指一系列边的序列，任意边的终点与下一条边的起点相同，但途径中的边和顶点可以重复。例如，在上面的图中，途径$A \to B \to D \to B$是一个有效的途径。
环(cycle)是指一条路径，其中起点和终点相同，并且除了起点和终点外，所有顶点都不相同。例如，在上面的图中，环$A \to B \to D \to C \to A$是一个有效的环。
回路(tour)是指一条途径，其中起点和终点相同，并且除了起点和终点外，但是顶点可以相同，也就是说可以有重复的边和顶点。

连通性

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

使用C++语言实现图

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

1
2
3
4
5
  A
 / \
B   C
 \ /
  D

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

1
2
3
4
A: B, C
B: A, D
C: A, D
D: B, C

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

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
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 4; // 顶点数量
    vector<vector<char>> adjList(n);

    // 添加边
    adjList[0].push_back('B'); // A-B
    adjList[0].push_back('C'); // A-C
    adjList[1].push_back('A'); // B-A
    adjList[1].push_back('D'); // B-D
    adjList[2].push_back('A'); // C-A
    adjList[2].push_back('D'); // C-D
    adjList[3].push_back('B'); // D-B
    adjList[3].push_back('C'); // D-C

    // 输出邻接表
    for (int i = 0; i < n; i++) {
        cout << "Vertex " << i << ": ";
        for (char neighbor : adjList[i]) {
            cout << neighbor << " ";
        }
        cout << endl;
    }

    return 0;
}

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

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

Königsberg七桥问题

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

1
2
3
4
5
6
7
 A ----+
/ \    |
\ /    |
 B ----D
/ \    |
\ /    |
 C ----+

在这个图中，顶点$A$、$B$、$C$和$D$分别代表Königsberg的四个部分，而边代表连接这些部分的七座桥。我们可以看到，顶点$A$的度数是3，顶点$B$的度数是3，顶点$C$的度数是3，顶点$D$的度数是3。根据前面提到的性质，图中所有顶点的度数之和是12，而边数是7，所以满足$\sum_{v \in V} \text{degree}(v) = 2|E|$。
欧拉回路(Eulerian tour)是指一条回路，其中每条边恰好被访问一次。对于Königsberg七桥问题，我们需要找到一条欧拉回路。

欧拉回路的存在条件

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

以下是一个示例代码：

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
#include <iostream>
#include <vector>
using namespace std;

vector<int> FindTour(const vector<vector<int>>& graph, vector<vector<bool>>& visited, int s) {
    vector<int> tour;
    int t = -1;
    for (int i : graph[s]) {
        if (!visited[s][i]) { // 如果边(s, i)未访问
            visited[s][i] = visited[i][s] = true; // 标记边(i, s)为已访问（无向图）
            t = i;
            break;
        }
    }
    if (t != -1) tour = FindTour(graph, visited, t); // 继续从t出发寻找回路
    else return vector<int>(); // 如果没有未访问的边，返回空回路
    tour.push_back(s); // 将当前顶点添加到回路中
    return tour;
}

vector<int> Euler(const vector<vector<int>>& graph,int s) {
    int n = graph.size();
    vector<vector<bool>> visited(n, vector<bool>(n, false)); // 初始化访问状态
    vector<int> tour = FindTour(graph, visited, s); // 找到初始回路

    // 处理剩余的子图
    for (int i = 0; i < n; i++) {
        for (int j : graph[i]) {
            if (!visited[i][j]) { // 如果还有未访问的边
                vector<int> newTour = FindTour(graph, visited, i); // 从未访问的边出发找到新的回路
                // 将newTour插入到tour中
                auto it = find(tour.begin(), tour.end(), i);
                tour.insert(it, newTour.begin(), newTour.end());
            }
        }
    }
    return tour;
}

树

树(tree)是一种特殊的图，如下图所示：

1
2
3
4
5
    A
   / \
  B   C
 / \
D   E

定义

如何定义树？根据上图的特征，我们可以提出这些定义：

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

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

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

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

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

定理：如果$T$是一个树，那么$|E(T)| = |V(T)| - 1$。

证明：

  • 基础情况：当$|V(T)| = 1$时，树$T$只有一个顶点，没有边，因此$|E(T)| = 0 = 1 - 1$，结论成立。
  • 归纳假设：假设对于任意一个树$T’$，如果$|V(T’)| < n$，那么$|E(T’)| = |V(T’)| - 1$。
  • 归纳步骤：现在考虑一个树$T$，其中$|V(T)| = n$。因为$T$是一个树，所以它至少有一个顶点$v$的度数为一。根据引理，去掉这个顶点$v$和与之相连的边后，得到一个新的图$T’$，其中$|V(T’)| = n - 1$。根据归纳假设，$|E(T’)| = |V(T’)| - 1 = (n - 1) - 1 = n - 2$。因为我们去掉了一个顶点和一条边，所以$|E(T)| = |E(T’)| + 1 = (n - 2) + 1 = n - 1$。因此，$|E(T)| = |V(T)| - 1$，结论成立。

那么反过来是否成立呢？

定理：如果一个连通的无向图$G$满足$|E(G)| = |V(G)| - 1$，那么$G$是一个树。

证明：

  • 基础情况：当$|V(G)| = 1$时，图$G$只有一个顶点，没有边，因此$|E(G)| = 0 = 1 - 1$，结论成立。
  • 归纳假设：假设对于任意一个连通的无向图$G’$，如果$|V(G’)| < n$，并且$|E(G’)| = |V(G’)| - 1$，那么$G’$是一个树。
  • 归纳步骤：现在考虑一个连通的无向图$G$，其中$|V(G)| = n$，并且$|E(G)| = |V(G)| - 1$。可以算出所有度数之和为$D = 2|E(G)| = 2(|V(G)| - 1) = 2n - 2$。故平均度数为$\frac{D}{|V(G)|} = \frac{2n - 2}{n} = 2 - \frac{2}{n} < 2$。因此，图$G$中至少有一个顶点$v$的度数为一。去掉这个顶点$v$和与之相连的边后，得到一个新的图$G’$，其中$|V(G’)| = n - 1$，并且$|E(G’)| = |E(G)| - 1 = (n - 1) - 1 = (n - 1) - 1 = |V(G’)| - 1$。根据归纳假设，$G’$是一个树。因为我们去掉了一个顶点和一条边，所以$G$也是一个树。因此，我们证明了如果一个连通的无向图$G$满足$|E(G)| = |V(G)| - 1$，那么$G$是一个树。

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

平面图和完全图

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

1
2
3
4
5
    A
   / \
  B   C
 / \
D   E

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

1
2
3
4
5
  A
 /|\
B-C-D
 \|/
  E

完全图$K_n$是指有$n$个顶点的完全图，其中每对不同的顶点之间都有一条边连接。因此，完全图$K_n$的边数为$\frac{n(n-1)}{2}$，因为每对不同的顶点之间都有一条边连接。
平面图和完全图之间有一个重要的关系：对于$n \geq 5$，完全图$K_n$不是平面图。它的证明之后会谈到。

2026年2月18日。