离散数学/图论

简介

图是一种数学方式，用于表示“网络”的概念。

网络具有由线连接的点。在图中，我们为这些点和线赋予了特殊的名称。我们称这些点为顶点（有时也称为节点），线为边。

这是一个示例图。边为红色，顶点为黑色。

在该图中，$v_{1},v_{2},v_{3},v_{4}$ 是顶点，$e_{1},e_{2},e_{3},e_{4},e_{5}$ 是边。

图的定义

关于图，有几种大致等效的定义。集合论常被用来定义图。最常见的是，图 $G$ 被定义为一个有序对 $G=(V,E)$，其中 $V=\{v_{1},\ldots ,v_{n}\}$ 被称为图的顶点集，$E=\{e_{1},\ldots ,e_{m}\}\subset \{\{x,y\}|x,y\in V\}$ 被称为图的边集。给定一个图 $G$，我们通常用 $V(G)$ 表示顶点集，用 $E(G)$ 表示边集。为了可视化上述定义的图，我们画出 $n$ 个点，对应顶点 $v_{1},\ldots ,v_{n}$。然后，对于所有 $i,j\in \{1,\ldots ,n\}$，我们将在对应顶点 $v_{i},v_{j}$ 的点之间画一条线，当且仅当存在一条边 $\{v_{i},v_{j}\}\in E$。请注意，点的放置通常并不重要；许多不同的图片可以表示同一个图。

或者，以上面的图为例，我们可以将图定义为一个有序三元组 $G=(V,E,f)$

• 一组顶点，通常称为 V
• 一组边，通常称为 E
• 一个关系 $f:E\rightarrow \{\{x,y\}|x,y\in V\}$，它将每条边映射到一组端点，称为边端点关系。我们说一条边 $e\in E$ 与一个顶点 $v\in V$ 相邻，当且仅当 $v\in f(e)$。

在上面的例子中，

• V={v₁, v₂, v₃, v₄}
• E={e₁, e₂, e₃, e₄, e₅}
• f 使得 e₁ 映射到 {v₁, v₂}，e₂ 映射到 {v₁, v₃}，e₃ 映射到 {v₁, v₄}，e₄ 映射到 {v₂, v₄}，e₅ 映射到 {v₃, v₄}。

如果 $f$ 不是单射的——也就是说，如果 $\exists e,e'\in E$ 使得 $e\neq e',f(e)=f(e')$——那么我们说 $G$ 是一个多重图，我们将任何这样的边 $e,e'\in E$ 称为多重边。此外，我们称边 $e\in E$ 使得 $|f(e)|=1$ 为环。没有多重边或环的图称为简单图。

理论上，图也可以是无限的，因此我们对集合 V 和 E 没有限制。这里我们不会讨论无限图。

方向、权重和流量

我们将有向图定义为一个图，使得 $f$ 映射到有序对集合 $\{(x,y)|x,y\in V\}$ 而不是映射到二元组集合的族 $\{\{x,y\}|x,y\in V\}$。我们可以将边 $e\in E$ 视为从 $x$ 指向 $y$，使得 $f(e)=(x,y)$。因此，可以说 $x$ 是边 $e$ 的尾，而 $y$ 是头。不过，这只是图论符号中的一种怪癖。我们也可以将 $x$ 视为头，$y$ 视为尾。为了表示有向图，我们可以按照上述描述和图形进行绘制，但将箭头放在每个边上以表示其方向。

一般来说，图 $G$ 上的权重是某个函数 $c:E(G)\rightarrow \mathbb {R}$。

流 $(G,c)$ 是一个有向图 $G=(V,E,f)$ 与一个权重函数配对，使得“流入”任何顶点的权重与“流出”该顶点的权重相同。为了更正式地表达这一点，定义集合

• $f^{+}(v)=\{e\in E(G)|f(e)=(v,x),x\in V(G)\},\;\forall v\in V(G)$
• $f^{-}(v)=\{e\in E(G)|f(e)=(x,v),x\in V(G)\},\;\forall v\in V(G)$

然后，正式地说，我们对权重函数的要求是 $\sum _{e\in f^{+}(v)}c(e)=\sum _{e\in f^{-}(v)}c(e),\;\forall v\in V(G).$

代数图论

虽然在讨论图时经常使用集合论，但其他方法可以简化某些操作。可以使用邻接矩阵 $A$ 来定义集合，其中元素 $a_{i,j}$ 为 1，如果顶点 i 和顶点 j 之间存在边，否则为 0。

特殊图

6 个顶点的完全图

在图论中，一些图出现的频率很高，因此值得特别提及。其中一种图是 n 个顶点的完全图，通常用 K_n 表示。这个图由 n 个顶点组成，每个顶点都与其他每个顶点相连，每对顶点之间恰好有一条边。另一种图是循环图，它有n 个顶点（n 至少为 3）。这个图用 C_n 表示，定义为 V := {1,2,..,n} 和 E := {{1,2},{2,3}, ..., {n-1,n},{n,1}}。更简单的是空图，它有n 个顶点，没有边！注意 N₁ = K₁ 且 C₃ = K₃。

一些术语

如果两个顶点之间存在边，则称它们相邻。“关联”一词有两个含义

• 如果v 是e 的端点，则称边e 与顶点v 关联。
• 如果两条边都与同一个顶点关联，则称它们也彼此关联。

如果从G 的顶点集到H 的顶点集存在一个一对一函数（或者，如果你愿意，则存在顶点集之间的一一对应），使得G 中的两个顶点相邻当且仅当它们在H 中的像相邻，则称两个图G 和H 是同构的。（从技术上讲，边的重数也必须保留，但我们的定义足以用于简单图。）

子图

生成子图

子图是一个类似于子集的概念。子图具有顶点集 V 的子集、边集 E 的子集，并且更大图中每条边的端点在子图中具有相同的边。一个

子图 $H$ 由顶点集合 {$a,b,c,...$}$\in H$ 生成，如果 $H$ 的边集包含 $G$ 的边集中的所有边，这些边连接 $H=${$a,b,c,...$} 中的顶点。

路径 是边序列 $<e_{1},...,e_{N}>$，使得对于从 1 到 N-1 的所有 i，e_i 与 e_i+1 相邻。如果存在连接两个顶点的路径，则称这两个顶点是相连的。

树和二部图

树 是一个图，它 (i) 是连通的，并且 (ii) 没有环。等效地，树是一个具有恰好 $n-1$ 条边的连通图，其中树中存在 $n$ 个节点。

二部图 是一个图，其节点可以划分为两个不相交的集合 U 和 W，使得图中的每条边都与 U 中的一个节点和 W 中的一个节点相邻。树是一个二部图。

完全二部图 是一个二部图，其中 U 中的每个节点都与 W 中的每个节点相连；U 有 $n$ 个顶点，V 有 $m$ 个顶点的完全二部图表示为 $K_{n,m}$。

相邻、关联、端点顶点

自环、平行边、顶点度

悬挂顶点：度数为一的顶点 “悬挂顶点” 孤立顶点：度数为零的顶点 “孤立顶点”

哈密顿路径和欧拉路径

哈密顿回路：哈密顿回路得名于第一个研究旅行商问题的威廉·哈密顿爵士。哈密顿回路是访问每个顶点一次且仅一次的路径，即它是一个行走，其中没有重复边（轨迹），因此是一个不重复顶点的轨迹（路径）。注意它也是一个回路，最后一个顶点连接到第一个顶点。

如果可能遍历每条边一次且仅一次，则称该图为欧拉图，即它没有奇数顶点，或者它有偶数个奇数顶点（半欧拉图）。这对哥尼斯堡问题有影响。可以更容易地将其想象为是否可以用铅笔追踪图的边而不抬起铅笔或重复任何线条。

平面图

平面图 是一个无向图，它可以以这样一种方式绘制在平面上或球面上，使得没有两条边交叉，其中边 $e=(u,v)$ 被绘制为从 u 到 v 的连续曲线（它不一定是直线）。

库拉托夫斯基证明了关于平面图的一个 remarkable 事实：一个图是平面的当且仅当它不包含同胚于 $K_{5}$ 或者 $K_{3,3}$ 的子图。(两个图被称为同胚的，如果我们可以将每个图的某些分量缩减为单个节点，并最终得到相同的图。非正式地说，这意味着非平面性是由两件事造成的——即具有 $K_{5}$ 或 $K_{3,3}$ 的结构）。

图着色

一个图被称为平面的，如果它可以在平面上绘制，使得没有边相互交叉，当然除了在顶点处相遇之外。

每学期，某大学的排课办公室必须为每场期末考试分配一个时间段。这并不容易，因为有些学生正在上几门有期末考试的课，而且一个学生在一个特定时间段内只能参加一次考试。排课办公室希望避免所有冲突，但要尽量缩短考试时间。

我们可以将这个排课问题改写成关于图顶点着色的问题。为每门有期末考试的课程创建一个顶点。如果某个学生正在上这两门课，就在两个顶点之间画一条边。例如，排课图可能看起来像这样：接下来，用颜色识别每个时间段。例如，星期一上午是红色，星期一下午是蓝色，星期二上午是绿色，等等。

将考试分配到时间段现在等同于对相应的顶点着色。主要约束是相邻的顶点必须得到不同的颜色；否则，某个学生将在同一时间参加两场考试。此外，为了缩短考试时间，我们应该尝试使用尽可能少的不同颜色来对所有顶点着色。对于我们的示例图，三种颜色就足够了：红色、绿色、蓝色。

着色对应于在星期一上午（红色）安排一场期末考试，在星期一下午（蓝色）安排两场期末考试，在星期二上午（绿色）安排两场期末考试……

K 着色

许多其他资源分配问题都归结为对某些图进行着色。一般来说，一个图 G 是 k 可着色的，如果每个顶点可以被分配 k 种颜色中的一种，使得相邻的顶点得到不同的颜色。最小的足够颜色数称为 G 的色数。图的色数通常很难计算，但下面的定理提供了一个上限。

定理 1. 最大度数不超过 k 的图是 (k + 1) 可着色的。

---

证明。我们使用归纳法来证明图中顶点的数量，我们用 n 来表示。令 P(n) 表示一个 n 顶点图，其最大度数不超过 k，是 (k + 1) 可着色的。一个 1 顶点图的最大度数为 0，并且是 1 可着色的，所以 P(1) 为真。

现在假设 P(n) 为真，并令 G 为一个 (n + 1) 顶点图，其最大度数不超过 k。移除一个顶点 v，留下一个 n 顶点图 G。G 的最大度数不超过 k，因此根据我们的假设 P(n)，G 是 (k + 1) 可着色的。现在添加回顶点 v。我们可以给 v 分配一个与所有相邻顶点不同的颜色，因为 v 的度数不超过 k，并且有 k + 1 种颜色可用。因此，G 是 (k + 1) 可着色的。该定理由归纳法得出。

加权图

一个加权图将一个标签（权重）与图中的每条边相关联。权重通常是实数，并且通常表示与边相关的“成本”，无论是就建模的实体而言，还是就正在解决的优化问题而言。