集合与图论学习笔记06

定义

定义 6.1 子图、生成子图、边导出子图、导出子图

设是一个无向图，也是一个无向图。如果且，则称是的一个子图

若是的一个子图，且，则称是的一个生成子图

若对于，以为边集，所关联的所有顶点为顶点集，，图是的一个边导出子图，记为

设，以为顶点集，且中的每一条边都连接中的顶点，则图是的一个导出子图，记为

显然，完全图的导出子图还是完全图

定理 6.1.1

每个个顶点的简单图同构于的一个子图

证明： 点击查看证明

证明：

设是一个有个顶点的简单图，

构造映射，使得，其中是的顶点。由于是简单图，任意两顶点间最多有一条边，因此对于任意边，在中对应的边也存在

反之，如果在中存在，则对应的边也在中存在

因此，映射保持了顶点间的连接关系，即同构于的一个子图

定义 6.2 二分图

图如果存在的一个划分，使得的每一条边都连接中的一个顶点和中的一个顶点，这样的图称为二分图（偶图）

如果二分图中，，且中的每一条可能的边都存在，则称为完全二分图，记为

定理 6.2.1

一个图是二分图的充分必要条件是它不包含奇回路

证明： 点击查看证明

证明：(必要性)

设是一个二分图，是的一个划分

假设中存在一个奇数长度的回路，则必须交替经过和的顶点

由于回路的长度为奇数，起点和终点必须在同一集合中，这与二分图的定义矛盾

因此，二分图中不可能存在奇数长度的回路。

(充分性) 设是一个不包含奇数长度回路的图

选择任意顶点，令为到所有奇数长度路径的终点集合，为到所有偶数长度路径的终点集合

下面证明是的一个划分

是连通的，所以，且，否则存在一个顶点同时在和中，这意味着存在一条从到的奇数长度路径和一条偶数长度路径，这将形成一个奇数长度回路，与假设矛盾

下面证明的每一条边都连接中的一个顶点和中的一个顶点

假设存在一条边，其中，则存在从到的奇路和从到的奇路，将这两条路径与边连接起来，将形成一个奇数长度回路，这与假设矛盾

同理，如果，也会导致矛盾

因此，的每一条边都连接中的一个顶点和中的一个顶点，是一个二分图

定理 6.2.2

设是一个二分图，则

证明： 点击查看证明

证明：

设，，则中的每一条边都连接中的一个顶点和中的一个顶点

因此，中的边数不超过中的每个顶点与中的每个顶点之间可能的连接数，即

即

定理 6.2.3

二分图的每个生成子图仍然是二分图

证明： 点击查看证明

证明：

设是一个二分图，是的一个生成子图，其中

由于是二分图，的每一条边都连接中的一个顶点和中的一个顶点

因此，中的每一条边也连接中的一个顶点和中的一个顶点

所以，仍然是一个二分图

定义 6.3 欧拉图

设是一个无向图，如果中存在一条经过每一条边且仅经过一次的闭迹（闭链）（回路），则称为欧拉图，这样的闭迹称为欧拉闭链（欧拉回路）（欧拉链）

如果存在一条过每一条边且仅经过一次的开迹（开链），则称为半欧拉图，这样的开迹称为欧拉开链

显然，欧拉图除了孤立点外是连通的，而孤立点的有无不影响图的性质，所以不妨设欧拉图是连通的

若连通有向图存在一条经过每一条有向边且仅经过一次的闭链，则称该有向图为有向欧拉图

定理 6.3.1

设是一个连通图，则是欧拉图的充分必要条件是的每个顶点的度都是偶数

证明： 点击查看证明

证明：(必要性)

设是一个欧拉图，存在一条经过每一条边且仅经过一次的闭迹

在闭迹中，每次经过一个顶点时，都会使用两条边：一条进入，另一条离开。因此，顶点的度数必须是偶数

(充分性)

设是一个连通图，且每个顶点的度都是偶数

可以通过以下步骤构造一条经过每一条边且仅经过一次的闭迹：

1. 从任意顶点出发，沿着未经过的边行走，直到回到起点，形成一个闭迹
2. 如果已经经过了所有的边，则完成。如果还有未经过的边，选择一个在上的顶点，从出发，沿着未经过的边行走，直到回到，形成另一个闭迹，由于顶点的度是偶数，又是连通的，所以这样的总能找到
3. 将闭迹插入到闭迹中，形成一个更长的闭迹
4. 重复步骤 2 和 3，直到所有的边都被经过

由于每个顶点的度都是偶数，以上过程总能完成，最终形成一条经过每一条边且仅经过一次的闭迹，因此是欧拉图

定理 6.3.2

是一个连通图，则是半欧拉图的充分必要条件是恰有两个奇度顶点

证明： 点击查看证明

证明：(必要性)

设是一个半欧拉图，存在一条经过每一条边且仅经过一次的开迹，其起点为，终点为

在开迹中，除了起点和终点外，每次经过一个顶点时，都会使用两条边：一条进入，另一条离开。因此，顶点的度数必须是偶数

对于起点，它有一条边离开但没有边进入，因此其度数是奇数。同理，终点也有一条边进入但没有边离开，因此其度数也是奇数

(充分性)

设是一个连通图，且恰有两个奇度顶点和

可以通过以下步骤构造一条经过每一条边且仅经过一次的开迹：

1. 从奇度顶点出发，沿着未经过的边行走，直到到达奇度顶点，形成一条开迹
2. 如果已经经过了所有的边，则完成。如果还有未经过的边，选择一个在上的顶点，从出发，沿着未经过的边行走，直到回到，形成一个闭迹，由于顶点的度是偶数，又是连通的，所以这样的总能找到
3. 将闭迹插入到开迹中，形成一个更长的开迹
4. 重复步骤 2 和 3，直到所有的边都被经过

由于每个顶点的度都是偶数，除了和，以上过程总能完成，最终形成一条经过每一条边且仅经过一次的开迹，因此是半欧拉图

定理 6.3.3

设是一个连通图，则是欧拉图当且仅当是若干条边不相重的回路的并

证明： 点击查看证明

证明：

(必要性)

设是一个欧拉图，存在一条经过每一条边且仅经过一次的闭迹

可以将闭迹分解为若干条边不相重的回路的并

具体地，可以从闭迹中选择一个顶点，沿着闭迹行走，直到回到顶点，形成一个回路。然后，从闭迹中去掉回路的边，继续选择一个顶点，重复上述过程，直到所有的边都被包含在若干条回路中

(充分性)

是若干条边不相重的回路的并，设这些回路为

由于这些回路的边不相重，是连通的，因此可以通过以下步骤构造一条经过每一条边且仅经过一次的闭迹：

1. 从任意回路出发，沿着回路行走，直到回到起点，形成一个闭迹
2. 如果已经经过了所有的边，则完成。如果还有未经过的边，选择一个在上的顶点，从出发，沿着未经过的回路行走，直到回到，形成另一个回路
3. 将回路插入到闭迹中，形成一个更长的闭迹
4. 重复步骤 2 和 3，直到所有的边都被经过

因此，是欧拉图

定理 6.3.4

是连通有向图，则是有向欧拉图的充分必要条件是每个顶点的入度等于出度

证明： 点击查看证明

证明：

(必要性)

设是一个有向欧拉图，存在一条经过每一条有向边且仅经过一次的闭迹

在闭迹中，每次经过一个顶点时，都会使用一条有向边进入，另一条有向边离开。因此，顶点的入度必须等于出度

(充分性)

若设是一个连通有向图，且每个顶点的入度等于出度

可以通过以下步骤构造一条经过每一条有向边且仅经过一次的闭迹：

1. 从任意顶点出发，沿着未经过的有向边行走，直到回到起点，形成一个闭迹
2. 若果已经经过了所有的有向边，则完成。如果还有未经过的有向边，选择一个在上的顶点，从出发，沿着未经过的有向边行走，直到回到，形成另一个闭迹，由于每个顶点的入度等于出度，又是连通的，所以这样的总能找到
3. 将闭迹插入到闭迹中，形成一个更长的闭迹
4. 重复步骤 2 和 3，直到所有的有向边都被经过

因此，是有向欧拉图

定理 6.3.5

是连通有向图，则是有向半欧拉图的充分必要条件是恰有一个顶点的出度比入度大 1，恰有一个顶点的入度比出度大 1，且这两个顶点都是奇点，其余顶点的入度等于出度

证明： 点击查看证明

证明：(必要性)

设是一个有向半欧拉图，存在一条经过每一条有向边且仅经过一次的开迹，其起点为，终点为

在开迹中，除了起点和终点外，每次经过一个顶点时，都会使用一条有向边进入，另一条有向边离开。因此，顶点的入度必须等于出度

对于起点，它有一条有向边离开但没有有向边进入，因此其出度比入度大 1。同理，终点也有一条有向边进入但没有有向边离开，因此其入度比出度大 1

(充分性)

若设是一个连通有向图，且恰有一个顶点的出度比入度大 1，恰有一个顶点的入度比出度大 1，且这两个顶点都是奇点，其余顶点的入度等于出度

可以通过以下步骤构造一条经过每一条有向边且仅经过一次的开迹：

1. 从奇度顶点出发，沿着未经过的有向边行走，直到到达奇度顶点，形成一条开迹
2. 若果已经经过了所有的有向边，则完成。如果还有未经过的有向边，选择一个在上的顶点，从出发，沿着未经过的有向边行走，直到回到，形成一个闭迹，由于每个顶点的入度等于出度，又是连通的，所以这样的总能找到
3. 将闭迹插入到开迹中，形成一个更长的开迹
4. 重复步骤 2 和 3，直到所有的有向边都被经过

因此，是有向半欧拉图

欧拉图和一笔画问题密切相关

一笔画问题是指在不重复经过任何边的情况下，能否从一个顶点出发，经过图中的所有边并回到起点。根据欧拉图的定义，如果一个图是欧拉图，那么它就可以通过一笔画完成

定理 6.3.6

若一个图中奇顶点的个数为个，则该图是笔画的，即可以用条不重复经过任何边的路径覆盖图中的所有边

证明： 点击查看证明

证明：

设是一个图，奇顶点的个数为个

将这个奇顶点两两配对，连接每一对奇顶点之间添加一条边，得到一个新图，其中，和是配对的奇顶点

在新图中，每个顶点的度数都是偶数，因此根据定理 6.3.1，是一个欧拉图

存在一条经过每一条边且仅经过一次的闭迹在中

由于包含了新添加的条边，我们可以将闭迹分解为条路径，每条路径从一个奇顶点出发，经过图中的边，最终到达另一个奇顶点

因此，原图可以用条不重复经过任何边的路径覆盖图中的所有边，即是笔画的

定义 6.4 哈密顿图

设是一个无向图，如果中存在一条经过每一个顶点且仅经过一次的闭迹（回路），则称为哈密顿图，这样的闭迹称为哈密顿回路（哈密顿圈）

如果存在一条经过每一个顶点且仅经过一次的开迹，则称为半哈密顿图，这样的开迹称为哈密顿路径（哈密顿路）

到目前为止，还没有一个非平凡的充分必要条件可以用来判定一个图是否为哈密顿图或半哈密顿图，这是图论中的一个重要未解问题

定理 6.4.1（必要条件）

若是一个哈密顿图，则对于的任意非空真子集，都有，其中表示从图中去掉顶点集及其所有关联边后所得到的图的连通分支数

证明： 点击查看证明

证明：

设哈密顿回路经过图中的所有顶点，则对的每一个非空真子集有

因此，

我们举出一个反例来说明该条件不是充分条件

考虑彼得森图

在图中删去任意一个或者两个顶点， 剩下的图都是连通的，删除三个顶点，最多只能得到有两个连通分支的图，删去四个顶点，最多只能得到有三个连通分支的图，删除五个或者五个以上的顶点，余下的顶点数不大于五，因此不能有五个以上的连通分支，因此对于彼得森图的任意非空真子集，都有

下面证明彼得森图不是哈密顿图

证明： 点击查看证明

证明：

将彼得森图的边分为三类：

• 类1：连接外部大五边形的5条边
• 类2：连接内部小五角星的5条边
• 类3：连接内外顶点的5条边

如果这个图是哈密顿图，那么存在一条10条边组成的回路（10个顶点），该回路中的3类边有2条或4条（回到内圈或外圈的起点），否则无法回到起点形成回路

若由两条3类边，则外圈有4条边，内圈有4条边，无法构成回路（其他情况显然不成立）

若由四条3类边，则有一个还未连接的外圈顶点必有2条1类边与相邻外圈顶点相连，同理未连接的内圈顶点也必须有2条2类边与相邻的内圈顶点相连，此时无法构成回路

故彼得森图不是哈密顿图

接下来讨论一些哈密顿图的充分条件

先从给出的结果开始

定理 6.4.2 (充分条件)

设是一个含有个顶点的简单图，如果中每个顶点的度至少为，即则是哈密顿图

证明： 点击查看证明

反证法：

假设不是哈密顿图，且是含有个顶点的简单图，，且每个顶点的度至少为

由于显然不能是完全图

设是的不相邻顶点，根据中每个顶点的度至少为，则有

由于不相邻，通过加边，可以使得变为哈密顿图，并且，由于不是哈密顿图，所以的每个哈密顿回路必然包含边，否则就是哈密顿图

于是中存在起点为，终点为的路径，设为，其中，

记

则，，且

由于,则并且为空

否则如果不为空，设，则中存在回路，与不是哈密顿图矛盾

但是这里有，这与矛盾

故是哈密顿图

和在年基于上面的证明给出了哈密顿图的一个更有力的充分条件

定理 6.4.3 (充分条件)

设是一个含有个顶点的简单图，如果对于中任意不相邻的两个顶点和，都有，则是哈密顿图

证明： 点击查看证明

反证法：

假设不是哈密顿图，且是含有个顶点的简单图，，且对于中任意不相邻的两个顶点和，都有

由于显然不能是完全图，设是的不相邻顶点，通过加边，可以使得变为哈密顿图，并且，由于不是哈密顿图，所以的每个哈密顿回路必然包含边，否则就是哈密顿图

于是中存在起点为，终点为的路径，设为，其中，

必存在点和相邻，且点和相邻，否则，若与相邻，则必与不相邻，且这些点两两不同，则因此，与矛盾

从而存在回路，与不是哈密顿图矛盾

所以是哈密顿图

当然，也可以用 定理 6.4.2 相似的过程来证明该定理，这里采用了不同的方式

显然的，可以从 定理 6.4.3 推出 定理 6.4.2

定义图的闭包：反复链接中度之和至少为的不相邻顶点对，直到不存在这样的顶点对为止，所得到的图称为的闭包，记为

定理 6.4.4（闭包的唯一性）

是唯一的

证明： 点击查看证明

证明：

设和是的两个闭包

假设，则存在一对顶点，使得和在中相邻，而在中不相邻

由于是的闭包，和在中不相邻，说明在中，同理，在中

这与和在中相邻矛盾

因此，是唯一的

定理 6.4.5 (平凡的充分必要条件)

一个简单图是哈密顿图的充分必要条件是它的闭包是哈密顿图

证明： 点击查看证明

证明：(必要性)

设是一个哈密顿图，存在一条经过每一个顶点且仅经过一次的闭迹

由于闭包是通过添加边得到的，因此闭迹仍然存在于中

因此，是一个哈密顿图

(充分性)

设是一个哈密顿图，存在一条经过每一个顶点且仅经过一次的闭迹

由于，闭迹中的边也存在于中

因此，是一个哈密顿图

其实由闭包的构造过程可以知道这个结果是显然的

通过 定理 6.4.5，可以将判定一个图是否为哈密顿图的问题转化为判定其闭包是否为哈密顿图的问题

由此可以得到很多有趣的结果

（未完待续）