图论基础——顶点、边与基本概念

图论研究的是图，也就是由顶点和边组成的结构。顶点表示对象，边表示两个对象之间的关系。

如果你在查找图论基础，可以先从这个想法开始：图是一种清晰表示连接关系的方法。社交网络中的人、由道路连接的城市，以及彼此链接的网页，都可以用图来表示。

数学中的图是什么意思

在无向图中，一条边表示两个顶点相连，而且这种连接没有方向。如果 $A$ 与 $B$ 相连，那么 $B$ 也与 $A$ 相连。

在有向图中，边是有方向的，所以 $A \to B$ 和 $B \to A$ 是不同的说法。很多入门例子使用的是简单无向图，也就是没有自环，并且同一对顶点之间没有重复边。

这个条件很重要，因为很多定义通常都会先在简单无向图的情形下引入。如果图的类型变了，术语的含义也可能随之改变。

你首先需要掌握的图论术语

顶点和边

顶点是你想要跟踪的对象。边是你想要跟踪的连接关系。

如果一个图表示城市和道路，那么城市是顶点，道路是边。

度

在无向图中，一个顶点的度是与它相接的边的条数。

如果一个城市有通往另外三个城市的道路，那么它的度就是 $3$。

路径

路径是一个顶点序列，其中每一对相邻顶点都由一条边连接。

如果从一个顶点到另一个顶点存在路径，你就可以沿着边从一个走到另一个。

环

环是起点和终点为同一顶点的路径。在通常的基础定义中，其他顶点不能重复出现。

环说明图中存在一个闭合回路。

连通图与连通分量

如果无向图中每个顶点都可以通过某条路径到达其他任意顶点，那么这个图就是连通的。

如果不满足这一点，图就会分裂成若干个连通分量。每个分量都是图中的一个连通部分。

例题：一个小图

假设一个图有顶点 $A$、$B$、$C$、$D$ 和 $E$，边为

$$AB,\ AC,\ BC,\ CD$$

这表示在 $A$、$B$ 和 $C$ 上构成了一个三角形，另外还有一条从 $C$ 到 $D$ 的边，以及一个孤立顶点 $E$。

现在主要概念就很容易看出来了。

各顶点的度为

$$\deg(A)=2,\ \deg(B)=2,\ \deg(C)=3,\ \deg(D)=1,\ \deg(E)=0$$

从 $A$ 到 $D$ 存在一条路径：

$$A-C-D$$

存在一个环：

$$A-B-C-A$$

这个图不是连通图，因为无法从其他顶点到达 $E$。所以这个图有两个连通分量：一个包含 $A,B,C,D$，另一个只包含 $E$。

这一个例子就展示了度、路径、环、孤立顶点和连通分量是如何联系在一起的。

一个快速检查：度数之和

对于任意有限无向图，

$$\sum \deg(v) = 2|E|$$

这是因为每条边恰好连接两个端点，所以每条边都会给两个顶点的度数各增加 $1$。

在上面的例子中，度数之和是

$$2+2+3+1+0=8$$

边的条数是 $4$，所以

$$2|E| = 2 \cdot 4 = 8$$

当你手动统计各顶点的度时，这是一个很有用的检查方法。如果数字对不上，那就说明哪里出了问题。

图论中的常见错误

混淆顶点和边

顶点是对象。边是它们之间的关系。

忘记自己处理的是哪一类图

对于简单无向图成立的结论，换成有向图或允许自环的图时，可能就需要修改。

把路径当成环

路径不一定要回到起点。环必须回到起点。

忽略孤立顶点

度为 $0$ 的顶点仍然是图的一部分。它可能会影响图是否连通。

图论基础用在哪里

这些概念会出现在计算机网络、路径规划、调度、推荐系统和社交网络中。应用场景会变，但核心问题总是类似的：哪些是连通的，哪些可以到达，以及哪里存在回路？

这就是为什么图论会在离散数学和计算机科学中较早出现。

试试一个类似的图

画出四个顶点 $P$、$Q$、$R$ 和 $S$。加入边 $PQ$、$QR$、$RS$ 和 $SP$。

然后回答三个问题：每个顶点的度是多少，这个图是否连通，以及这个图是否包含一个环？