2.1　图论基础

本节介绍本书涉及的图论基本定义、符号与理论 ^[1] ，包括图的定义与类型、图的度序列、图的运算、图的同构、图的矩阵，以及图着色。

2.1.1　图的定义与类型

用 表示非空集 的所有 -元子集构成的集族， 。基于此，给出图的定义：设 是一个非空集， ，则把有序对 称为一个 图 ，记作 ，并将 称为 的 顶点集 ， 称为 的 边集 ； 中的元素称为 的 顶点 ， 中的元素称为 的 边 。对于给定图 ，有时也用 和 分别表示 的顶点集和边集。设 ，通常用 来代替 ，并称顶点 与顶点 相邻 ，称顶点 （或 ）与边 （相互） 关联 。设 ， 或 表示图 中所有与顶点 相邻的顶点构成的集合，称为 的 邻域集 。如果图 中的两条边 、 与同一个顶点关联，则称它们 相邻 。设 ，如果 中的任意两个顶点均不相邻，则称 是 的一个 独立集 。类似地，设 ，若 中的任意两条边均不相邻，则称 是 的 匹配 ，或称 是 的一个 边独立集 。

注2.1 由于集合中元素不允许重复，因此 与 中均无重复的元素，且 为无序 2 元子集构成的集族。这就意味着：① 中没有重复的边；② 中的每条边 中的两个关联顶点不同；③ 。满足上述3点的图又称 简单无向图 。

若 与 中元素的数量均有限，则称 为 有限图 ，否则称为 无限图 。本书提到的图皆为有限图。通常，称 为 的 阶 ， 为 的 规模 ，并把具有 个顶点、 条边的图称为 ( n , m )-图 。

图 可在平面上用一个几何图形来表示：顶点用一个小圆点（称为点）表示，若顶点 与 相邻，则在 与 之间连接一条线。这种将 画在平面上的方法称为 的 图解 。用图解表示图，能更直观、清晰地展示图的结构，有助于理解图的性质，这也是图论的魅力所在。

设 是一个 阶简单图， 。若 ，则称 为 阶完全图 ，记作 ；图2.1（a）（b）所示为 的两种不同的图解。完全图的特征是：每对顶点均相邻。与完全图恰恰相反的是：若 中每对顶点均不相邻，即 ，则称 为 阶空图 ，又称 阶零图 ，记作 ，在不考虑顶点数时，通常称为 空图 或 零图 。

图 若满足 且 ，则称 为 长路 或 路 ，记作 ，图2.1（c）所示为 的一种图解；若 ， ，则称 为 -圈 ，记作 。图2.1（d）所示为 的一种图解。

注2.2 对于一个图的图解，我们不关心顶点和边的几何特征，即顶点的大小、形状、空心还是实心，以及边的长短、粗细、曲直等。

例2.1 设 是简单图，其中 ， ，则此图为著名的 彼得松图 （Peterson Graph），如图2.2（a）所示。图2.2（b）（c）所示为该图的两种图解。

若对 中每个顶点标名称，则称 为 标定图 ，否则称为 非标定图 。图 2.2（a）所示为标定图，图2.2（b）（c）所示均为非标定图。

在简单图 的定义中，边集 中的元素是互不相同的，即 边互不相同 。如果去掉这个限制，即 允许有相同元素 ，会导致图 G 中一对顶点之间可能有 （ i ＞1）条边，称为 -重边 。具有重边的图称为 重图 。更详细的论述如下。

将 扩展成一个允许含重复元素 ^[2] 的新集族，记作 。有序对 称为一个 重图 ，记作 ，其中 ；重复出现的元素称为 重边 。

例2.2 设 ，其中 ， ， ， ， ， ， ，则 是重图。图2.3（a）所示为它的一种图解。

重图 的 基础图 是一个基于 的简单图，记作 ：顶点集 ，且 中任意一对顶点相邻当且仅当该对顶点在 中至少有一条边相连。重图 的基础图 ，其中 ， ，如图2.3（b）所示；图2.3（c）所示为它的一个图解。

在简单图与重图的定义中，任意边 所关联的两个顶点不同，即 。如果去掉这个限制，即一条边所关联的两个顶点相同，则这种边称为图的 自环 ，且含有自环的图称为 伪图 。确切地讲，在简单图或重图中，可将 （或 ）扩展为允许含 中一个或多个元素 ^[3] 的新集族（记作 ），这时有序对 称为一个 伪图 ，记作 。其中， ，元素 称为 自环 ， 。

例2.3 图 是一个伪图，其中 ， 。在 中， 与 均为自环，如图2.4所示。

注2.3 在重图中，边集 必含重边；在伪图中，边集 E _O 必含自环。

在重图中，如果把关联同一对顶点的边的数量标于该边在基础图中对应的边上，则相当于给 边赋权值 。例如，对于图2.3（a）所示的重图 ，按边的重数定义各边的赋权 w 分别为 、 、 、 ，则边赋权图如图2.3（c）所示。更一般地， 边赋权图 G 可表示为一个三元有序组 ，其中( V , E )是一个简单图。令 ，则 为 赋权向量 ， （ ）为边 的 权值 。按此定义，在图2.3（c）所示的边赋权图中， 。

边赋权图的应用场景较多，如交通网络和生物神经网络。在交通网络中，顶点表示城市，边表示两个城市之间的公路、铁路、飞行航线或航海线等，边的权值则表示两个城市之间的距离（包括公路距离、铁路距离、飞行距离和航海距离等）。在生物神经网络中，顶点表示生物体（如人）的神经元，边表示两个神经元之间的突触，边的权值表示对应突触的厚度。人脑约有 个神经元，以及 ～ 个突触，但关于突触厚度的研究相对较少，这方面的深入研究对脑科学的研究至关重要。

与边赋权图相似，下面给出点赋权图的定义：一个三元有序组 称为一个 点赋权图 ，其中 为简单图， 为 的 顶点赋权向量 ， （ ）是顶点 的权值。图2.5所示为一个点赋权图，其中 ， 。注意，该例中， 中每个顶点的权值属于 ，且每条边的两端权值不同。因此，这种点赋权可视为对该图的 顶点着色 ，其中权值代表颜色，颜色集为 。

点赋权图的应用场景也较多，如用于解决交通信号灯设计问题、调度问题和航线规划问题等 ^[2] 。

对一个简单图 的顶点与边同时赋权的图，称为 混合型赋权图 （通常将它简称为 赋权图 ），它具有更丰富的应用场景。混合型赋权图是一个四元组 ，其中 为简单图， 分别为定义在 、 上的赋权向量，与边赋权图中的 、点赋权图中的 相同，这里不赘述。

综上所述，无向图可分为简单图、重图、伪图、赋权图。赋权图可进一步分为边赋权图、点赋权图及混合型赋权图。

注2.4 若无特别声明，本书提及的图皆为有限简单无向图。

在图的定义中，把 中的 无序 改成 有序 ，便得到有向图的概念。

设 ， 表示 中所有有序对之集，并把从 到 的有序对记作 ，简记为 （ ）。如 ， 。基于 ，可类似地定义有向图如下。

设 是非空集， ，则有序对 为一个 简单有向图 ，记作 ，并称 为 的 顶点集 、 为 的 弧集 ，即 中的元素为 的 顶点 ， 中的元素为 的 弧 。设 且 ，则 为从 连接到 的弧， 为 的 尾 ， 为 的 头 。在有些情况下，可称 关联 和 、 邻接于 、 控制 等。

形如 和 的一对弧为 对称弧 。设 是一个有向图，它的 逆 记作 ，定义为 ， 。有向图 的 基础图 记作 ，是指用无向图的边来代替 中的每一条弧而得到的图。图2.6所示为有向图 、它的逆 ，以及它的基础图 。

完全对称图 是每对顶点之间恰有一对对称弧连接的有向图，图 2.7（a）所示为一个 5 阶完全对称有向图。 竞赛图 是一类具有较多应用场景的有向图，它的每对顶点之间恰有一条弧。换言之，竞赛图就是基础图为完全图的有向图。图2.7（b）所示为一个5阶竞赛图。

上述有向图均为简单有向图。与无向图的分类相似，有向图也可分为 4类：简单有向图、多重有向图、伪有向图及赋权有向图。其中，赋权有向图可进一步分为弧赋权有向图、点赋权有向图和混合型赋权有向图。

本书主要考虑无向图，故本小节仅简要介绍有向图的基本概念与分类，更系统的有向图理论可查阅文献[2]。无向图的详细定义、记号及基本理论可查阅文献[3-4]。

2.1.2　图的度序列

设 是一个简单图， ，则与 关联的边数为 的 度数 （简称 度 ），记作 ，在不致混淆的情况下可用 表示。显然，有

，或 （2.1）

图 的 最大度 是指图 中所有顶点的度数最大值，图 的 最小度 是指图 中所有顶点的度数最小值：

，

其中， 。

若 ，则称 G 是 k -正则图 。

我们把度数为0的顶点称为 孤立点 ，度数为1的顶点称为 悬挂点 。

图 的 度序列 是由该图中所有顶点的度数依次构成的序列，一般单调递增或单调递减。确切地讲，设 ， （ ），如果有

（2.2）

则称 是图 的度序列，并记作 。

有时，也采用递增序列

（2.3）

作为图 的度序列，即 。

例如，图2.3（b）所示图的度序列为 或 。

关于图的度序列，易证得定理2.1。

定理2.1 设 是一个 -图， ， （ ），则有以下结论成立。

（1） 。

（2）在 中至少存在两个值相等。

（3） 。

证明 V ( G )中的顶点至多与其余 个顶点相邻，也有孤立顶点的可能性，故（1）成立；根据鸽巢原理可证得（2）；图中的每条边对 的贡献数为2， 条边的贡献数为 ，故（3）成立。

2.1.3　图的运算

与数、向量和矩阵相似，图与图之间，以及图自身存在许多运算，这些运算代表了不同的功能。随着图论研究的深入，未来还会产生更多的图运算。本小节介绍一些基本的图运算。

1.子图与图的一元运算

对于图 G 和 H ，如果 并且 ，那么称 H 是 的 子图 ；进一步，若 或者 ，则称 H 是 的 真子图 。在图的子图中，有两类特殊且重要的子图：生成子图与导出子图。

设 为 的一个子图，若 ，则称 为 的 生成子图。 设 且 ，由 导出的子图为 顶点导出子图 ，记作 ，它是图 的一个子图： ， 。与顶点导出子图相似，可定义 边导出子图 （简称 边导子图） ：设 是图 的非空边子集，以 为边集，以 中边的端点的全体为顶点集所构成的子图称为由 导出的 的子图 ，记作 。

（1）删点运算。导出子图 简记为 （ ），它是从 中删去 中的顶点及与这些顶点相关联的全部边得到的子图。特别地，当 时， 简记为 ，称为 的删点子图。

（2）删边运算。若 ，则从 中删去边 所得之图记作 ，称为删边子图。若 且 ，则 表示从 中删去 得到的子图。图2.8所示为各种子图的示例。

基于子图的概念，下面给出连通图与树的定义。

设 是一个 阶图。若 ，在 中存在从 到 的一条路，则称 是 连通的 ，或称 为 连通图 。令 H 是 G 的一个子图，如果 H 是连通的，并且 H 不是 G 的任何连通子图的真子图，那么称 H 是 G 的一个 连通分支 。若在 中存在一个子图是圈，则称 是 含圈图 ，否则称 为 森林 。特别地，连通的森林被称为 树 。换言之，树就是连通的无圈图。

删点运算与删边运算均为图的 一元运算 ，它们是针对一个图的运算。

2.二元运算

下面给出5种常用的两个图之间的运算，也称为 图的二元运算 ：并运算、交运算、差运算、环和运算、联运算。这里，用 和 表示两个图。

（1）并运算，记作 。

若 与 无公共边，即 和 的边不重合，则称 为 和 的直和，故本书提及直和运算时，参与运算的图之间没有公共边。

（2）交运算，记作 。

（3）差运算，记作 ，是指从 中删除 的边所得的子图。

（4）环和运算，记作 ，是指由 与 的并减 与 的交所得到的图，即 。

上述4种运算的示例如图2.9所示。

（5）联运算，记作 。顶点集与边集分别为

图2.10所示为 与 和它们的联图 。

3.其他一元运算

删点运算、删边运算均为 图的一元运算 ，下面给出另外两个常用的一元运算： 补运算 与 收缩运算 。

（1）补运算。设 是简单图，将 的 补运算 （简称 补 ）记作 ，其中 ，边集 且 。图 2.11 所示为图 与它的补 。易证：一个 阶简单图 与它的补 的并图是一个 阶完全图 ，即 。故有

注2.5 当且仅当一个图的补是空图时这个图是完全图。

在网络分析或系统分析研究中，图 与它的补之间的相互关系有直接应用：一个网络的结构越复杂，它的补网络的结构就越简单。所以，可通过研究补网络来分析原网络的特性。

（2）收缩运算。设 是一个简单图， 。 在 中，收缩 是指：把 中的顶点子集 视为一个（新的）顶点，记作 ；删除 G 中顶点都在 中的边； 中原来与 中顶点关联的边变成与 关联； 中其余的顶点与边保持不变。我们把这样得到的新图称为图 关于 的收缩图 ，记作 ，并把此过程称为关于顶点子集 的 收缩运算 。特别地，且当 ， 且 时，称 为在 中 收缩边 得到的图，记作 ，并把此过程称为 缩边运算 。图 2.12 所示为图 与关于顶点子集 、边 及 的收缩图 、 及 。