集合与图论学习笔记05

定义

定义 5.1 边集、点集、有向图、无向图、多重图、简单图、带权图、竞赛图

设是一个非空集，是上的二元关系，称有序对为有向图（directed graph，或 digraph）。的元素称为有向图的顶点（vertex），的元素称为有向图的边（edge）。如果，则称到有一条有向边，记作。称为有向图的顶点集，称为有向图的边集（弧集）

设是一个非空集，是上的无序二元关系，称有序对为无向图（undirected graph）。的元素称为无向图的顶点，的元素称为无向图的边。如果，则称和之间有一条无向边，记作。称为无向图的顶点集，称为无向图的边集

如果允许边集中存在重复的边，则称该图为多重图（multigraph）。否则，称该图为简单图（simple graph）

设是一个有向图或无向图，是定义在上的实值函数，称有序三元组为带权图（weighted graph）。称为权重函数，称为边的权重

设是一个有向图，且对于任意两个不同的顶点，恰有一条边连接它们（即要么，要么），则称该有向图为竞赛图（tournament）

定理 5.1.1

个顶点的完全图的边数为

个顶点的完全有向图的边数为

定义 5.2 度、入度、出度

设是一个无向图，。与顶点关联的边的数目（自环计算两次）称为顶点的度（dree），记作或。

图中顶点的最小度数称为图的最小度，记作；图中顶点的最大度数称为图的最大度，记作。

设是一个有向图，。以顶点为终点的边的数目称为顶点的入度（indree），记作或；以顶点为起点的边的数目称为顶点的出度（outdree），记作或。

定理 5.2.1

• 握手定理： 在无向图中，所有顶点的度数之和等于边数的两倍，即

证明： 点击查看证明

证明： 设无向图中有条边。每条边连接两个顶点，记作。则每条边对顶点度数的贡献为 2（因为每条边连接两个顶点）

因此，所有顶点的度数之和为：

定理 5.2.2

• 有向图的度数定理： 在有向图中，所有顶点的入度之和等于所有顶点的出度之和，且均等于边数，即。

证明： 点击查看证明

证明： 设有向图中有条边。每条边连接两个顶点，记作，其中是起点，是终点。 则每条边对入度和出度的贡献均为 1（因为每条边有一个起点和一个终点）

因此，所有顶点的入度之和为：。同理，所有顶点的出度之和也为：

定理 5.2.3

• 奇度定理： 在无向图中，度为奇数的顶点数目为偶数。

证明： 点击查看证明

证明： 设无向图中有个顶点。将顶点集分为两部分：度为奇数的顶点集和度为偶数的顶点集。设，则度为奇数的顶点数目为
为偶数为偶数，所以也为偶数。由于度为奇数的顶点数目为，每个顶点的度为奇数，因此为奇数的和。奇数个奇数之和为奇数，偶数个奇数之和为偶数。因此，必须为偶数

定理 5.2.4

• 完全图的度数： 完全图中每个顶点的度数为，即，其中

定理 5.2.5

• 完全有向图的度数： 完全有向图中每个顶点的入度和出度均为，即，其中

定理 5.2.6

• 竞赛图的度数1： 在竞赛图中，每个顶点的入度和出度之和均为，即，其中

• 竞赛图的度数2： 在竞赛图中，存在一个顶点，其出度至少为，即存在，使得

证明： 点击查看证明

证明： 设竞赛图中有个顶点。根据竞赛图的定义，每个顶点的入度和出度之和均为，即，其中

因此，所有顶点的出度之和为：。根据有向图的度数定理，，因此。

由于每条边都有一个起点和一个终点，因此。将其代入上式，得到

根据平均值原理，至少存在一个顶点，使得

• 竞赛图的度数3： 在竞赛图中，存在一个顶点，其入度至少为，即存在，使得

证明： 点击查看证明

证明：与出度证明类似

• 竞赛图的度数4：所有的顶点入度的平方和与出度的平方和相等，即

证明： 点击查看证明

证明： 设竞赛图中有个顶点。根据竞赛图的定义，每个顶点的入度和出度之和均为，即，其中

因此，。将其代入出度的平方和，得到：

根据有向图的度数定理，。由于竞赛图中有条边，因此

将其代入上式，得到：

• 竞赛图的度数5： 在竞赛图中，任意两个不同顶点的入度之差等于它们出度之差的相反数，即

证明： 点击查看证明

证明： 设竞赛图中有个顶点。根据竞赛图的定义，每个顶点的入度和出度之和均为，即，其中

因此，。对于任意两个不同顶点，有：

定理 5.2.7

证明： 点击查看证明

证明：

设图中有个顶点和条边。根据握手定理，所有顶点的度数之和为，即

因此，顶点的平均度数为

由于最小度数不大于平均度数，最大度数不小于平均度数，因此有

定义 5.3 可图化 可简单图化

设是非负整数序列。如果存在一个图，其顶点的度数依次为，则称该序列是可图化的（graphical）

如果存在一个简单图，其顶点的度数依次为，则称该序列是可简单图化的（simply graphical）。

定理 5.3.1

• 一个图是可图化的充分必要条件是其度数序列的和为偶数

证明： 点击查看证明

证明： 必要性：设图中有条边。根据握手定理，所有顶点的度数之和等于边数的两倍，即。由于是偶数，因此所有顶点的度数之和也必须为偶数

充分性：

中有偶数个奇数，记为，奇数分别为

采用下面的方法构造一个图

顶点集，首先在顶点和之间加入一条边，

若为偶数，令；若为奇数，令。则中全为偶数

再在上加入条自环，则得到一个图，其顶点的度数依次为，所以是可图化的

定理 5.3.2

• 一个简单图是可简单图化的充分必要条件是其度数序列满足埃尔德什-加拉伊定理

埃尔德什-加拉伊定理： 点击查看内容

设是非负整数序列，且。则该序列是可简单图化的充分必要条件是：

• 1. 为偶数;
• 2. 对每个，，都有

证明：

度数之和为偶数的必要性已在前面证明

对于第二个条件的必要性，设简单图的顶点集为，其中。考虑前个顶点之间的边数最多为条，每个顶点与其他个顶点之间的边数最多为条。因此，前个顶点的度数之和不能超过

充分性：

设是满足埃尔德什-加拉伊定理的非负整数序列。我们可以通过归纳法构造一个简单图，使其顶点的度数依次为，构造方法如下：

• 1. 初始化一个空图，其顶点集为。
• 2. 对于每个顶点，按照的值从大到小依次连接边，确保不违反简单图的定义（即不允许自环和多重边）。
• 3. 重复步骤 2，直到所有顶点的度数达到指定的值。
• 4. 最终得到的图即为所需的简单图。

定理 5.3.3

• 哈基米定理

是一个有限多个非负整数组成的非递减序列，可简单图化当且仅当有穷序列只含有非负整数且是可简单图化的

证明： 点击查看证明

证明：

必要性：设简单图的顶点集为，其中。选择度数最大的顶点，将其与其他个顶点连接边。这样，连接后的顶点的度数分别减少 1，得到新的度数序列。由于连接边不会引入自环或多重边，因此新的图仍然是简单图，因此是可简单图化的

充分性：设是可简单图化的。根据假设，存在一个简单图，其顶点的度数依次为

通过添加一个新的顶点，并将其与其他个顶点连接边，来构造一个新的简单图

新的图的顶点的度数依次为，因此是可简单图化的

定义 5 4 图的同构

设和是两个图。如果存在一个双射，使得对于任意，当且仅当，则称图与图同构（isomorphic），记作。函数称为同构映射（isomorphism）

定理 5.4.1

图和同构当且仅当对某一顶点的顺序，它们的邻接矩阵相同

证明： 点击查看证明

证明：

若这两个图同构，则存在一个双射，使得对于任意，当且仅当。这意味着在邻接矩阵中，如果顶点和之间有边，则在对应的邻接矩阵中，位置和的值为 1，否则为 0

对应的，有和位置的值也为 1 或 0

因此，通过重新排列顶点的顺序，可以使得两个图的邻接矩阵相同

定义 5.5 子图、补图

设是一个图。如果是由的部分顶点和部分边构成的图，即，其中且，则称为图的子图（subgraph），记作

设是一个图。图的补图（complement graph）记作，其中。即补图包含了图中没有的所有边

若一个图和它的补图同构，则称该图为自补图（self-complementary graph）

自补图的性质：

• 自补图的顶点数满足

定义 5.6 路径、回路、简单路径、简单回路

设是一个图，的一个有限点边交替序列，其中，，且，称为图中从顶点到顶点的一条路径（path），记作

路径的长度为边的数目。如果，则称该路径为回路（circuit）或闭路径（closed path）

边称为路径上的边，顶点称为路径上的顶点

若边互不相同，则称这个路径为链（简单路径），若顶点互不相同，则称这个路径为路

类似的，可以定义有向路径，有向路，有向链，有向闭路径，有向回路，有向闭链等

定理 5.6.1

• 路径与度数的关系1： 若图中每个顶点的度数至少为 2，则图中存在一条回路

证明： 点击查看证明

证明：

设图中每个顶点的度数至少为 2

若包含自环或者多重边，结论显然成立

若是简单图，任取顶点构造一个顶点序列，从其相邻点中任取一个顶点，再从的相邻点中任取一个未出现过的顶点，依此类推（每个点的度数至少为 2 保证了这个过程可以继续），直到某一步无法继续为止

设此时的顶点序列为

由于图是有限图，必然存在和，使得，且。因此，顶点序列构成了一条回路

定理 5.6.2

• 是简单图，若，则中有长度为的路

证明： 点击查看证明

证明：设的一条极大路为，则的长度为

设路的一个端点，由于是极大的，说明的所有邻接点都在路上，否则可继续扩展，与的极大性矛盾

因此，的度数，又由于，所以有

则，即路的长度至少为

故图中有长度为的路

定义 5.7 连通图、强连通图、连通分支

若两个不同的顶点之间存在一条路径，则称顶点和顶点是连通的（connected）

设是一个无向图。如果对于任意两个不同的顶点，都存在一条从到的路，则称图为连通图（connected graph）

设是一个无向图。的极大连通子图称为图的连通分支（connected component）

即：每个顶点的导出子图都是的一个连通分支，且与（）没有公共顶点

有个连通分支，则称图为-连通图，当时，称图为连通图

设是一个有向图。如果对于任意两个不同的顶点，都存在一条从到的有向路，则称图为强连通图（strongly connected graph）

定理 5.7.1

• 路径与度数的关系2： 若图中恰有两个顶点的度数为奇数，则图中存在一条从一个奇度顶点到另一个奇度顶点的路径

证明： 点击查看证明

证明：

如果是连通图，则从一个奇度顶点出发，沿着边不断前进，必然会到达另一个奇度顶点，从而构成一条路径

如果不是连通图，有连通分支，则奇度顶点必然存在至少 2 个位于同一个连通分支中，这是因为：

每个连通分支中的顶点度数之和为偶数，因此每个连通分支中奇度顶点的数目为偶数

定理 5.7.2

• 设图是有个顶点的简单图，若有条边，个分支，则有

证明： 点击查看证明

证明：

先证明左边

设图的连通分支为，每个连通分支有个顶点和条边，则有且。由于每个连通分支至少有条边，因此有：

再证明右边

去掉某一个连通分支有即，且

由于每个连通分支最多有条边，因此有：

因此，有：

定理 5.7.3

• 是简单图，有个顶点，，则是连通图

证明： 点击查看证明

证明：

设图中有个顶点，且每个顶点的度数至少为

假设图不是连通图，设有个连通分支，它们的顶点数分别为，则有且

每个连通分支的顶点度最多为，因此有：

，即

累加有：

当为偶数时，，则有，即，与矛盾！

当为奇数时，，则有，即。由于，因此，则

当且为奇数时，不妨设顶点数分别为和，则有

不妨设，则有

又

为奇数可知，不可能为整数，矛盾！

因此，图必须是连通图

定理 5.7.4

• 图是有个顶点的简单图，若对于任意两个不相邻的顶点，都有，则是连通图

证明： 点击查看证明

证明：

假设图不是连通图，设有个连通分支，它们的顶点数分别为，则有且

选择两个不同连通分支和，分别取其中的顶点和，则和不相邻

因此，有。然而，由于和分别属于不同的连通分支，它们的度数之和最多为，其中和分别是连通分支和的顶点数

因此，有，即。然而，由于，这意味着其他连通分支的顶点数之和为，矛盾

因此，图必须是连通图

定理 5.7.5

• 设是有个顶点的简单图，若对于任意两个不相邻的顶点，都有，则是强连通图

证明： 点击查看证明

证明：

假设图不是强连通图，设有个强连通分支，它们的顶点数分别为，则有且

选择两个不同强连通分支和，分别取其中的顶点和，则和不相邻

因此，有。然而，由于和分别属于不同的强连通分支，它们的度数之和最多为，其中和分别是强连通分支和的顶点数

因此，有，即。然而，由于，这意味着其他强连通分支的顶点数之和为，矛盾

因此，图必须是强连通图

定理 5.7.6

• 设是简单连通图，每一个顶点都是偶顶点，则

证明： 点击查看证明

证明：

去除后的图中有个连通分支，每个连通分支中顶点的度数之和为偶数，因此每个连通分支中奇点的数目为偶数

每个与相连的顶点都是奇点，设为与某个连通分支相连的边数，则该连通分支中奇点的数目为，因此必须为偶数

又是连通的，所以

因此，，其中每个都是正偶数，所以有

即

定义 5.8 邻接矩阵、路径矩阵

设图，其中。图的邻接矩阵（adjacency matrix）是一个的矩阵，其中：

$$ m_{ij} = \begin{cases} 1, & \text{如果 } \{v_i, v_j\} \in E \ 0, & \text{否则} \end{cases} $$

图的路径矩阵（path matrix）是一个的矩阵，其中：

是一个布尔矩阵，是连通图当且仅当中所有元素均为 1

无向图的邻接矩阵是对称矩阵

定理 5.8.1

• 设图的邻接矩阵为，则图的路径矩阵可由下式计算得到：

证明： 点击查看证明

证明：

设图中有个顶点，其邻接矩阵为。根据邻接矩阵的定义，当且仅当存在一条从顶点到顶点的边

的元素表示从顶点到顶点的长度为的路径的数量

图中存在一条从顶点到顶点的路径，当且仅当存在某个，使得，且

图的路径矩阵可以表示为：

所以，路径矩阵可以通过邻接矩阵的幂次和来计算得到：

此外，可以改为并逻辑运算来表示路径矩阵：

定理 5.8.2

• 设图的邻接矩阵为，则图的路径矩阵可由下式计算得到：

证明： 点击查看证明

证明：

设图中有个顶点，其邻接矩阵为。根据邻接矩阵的定义，当且仅当存在一条从顶点到顶点的边

是的单位矩阵，其对角线元素为 1，其他元素为 0

的元素表示从顶点到顶点的路径的数量，包括长度为 0 的路径（即从顶点到自身的路径）

的元素表示从顶点到顶点的长度不超过的路径的数量

图中存在一条从顶点到顶点的路径，当且仅当存在某个，使得，且

图的路径矩阵可以表示为：

所以，路径矩阵可以通过邻接矩阵的幂次和来计算得到：