离散数学-图论笔记

本文目录

前言
一、图论的基础概念
二、图的连通性
三. 欧拉图
四. 哈密尔顿图
五. 最短通路问题
- 1. 基础概念
- 2. 旅行商问题
六. 平面图问题
七. 图着色问题
八. 树
参考资料

前言

众所周知，离散数学这门课概念繁多，到处都是定义、定理，而很不幸我们学校的老师讲课又只是简单对着PPT念，非常不利于我们学习和复习离散数学这门科目。

为了提高复习效率，方便我今后查阅。我结合东北大学的离散数学网课，配合教材《离散数学.冯伟森著》以及各大网友的博客（主要是各类插图）整理了这篇图论笔记，初衷是方便自己复习使用。所有引用内容在文章末尾都有提及。

本文处于不断迭代完善的过程，后期根据做过的习题和新的理解，不断做补充。本博文的思维导图如下：

一、图论的基础概念

1. 图的定义

一些最基本的定义，就不一个个敲了，只把握符号和重点的定理。

简单图：无环，无平行边。
- 一般用表示有向边，表示无向边。
多重图：有平行边。
度：，入度：，出度，最大度：，最小度：
握手定理：
- 无向图中，每条边贡献2度。
- 有向图中，每条边贡献2度，入度=出度。
推论：任何图中，奇数度顶点的个数是偶数个。即必然成对出现。
n阶k正则图：满足的无向图，每个顶点都具有相同的度数。

案例：下列哪个哪些序列是一个图的度数序列？
A. (1,2,3,4,5)———-B.(2,2,2,2,2)———-C.(1,2,3,2,4)

A：不满足奇数度个数为偶数个。错误。
B：可以简单图化，5阶2正则。
C：可以简单图化。

图的同构
- 定义：存在两个图G1、G2，如果我们将顶点看作是数据，将边看成是数之间的运算，实际上这是一种系统。如果存在双射函数：，对于，当且仅当，并且的重数（平行边个数）相同，则称G1、G2是同构的。记作
- 同构的必要条件：边数相同；顶点数相同；度数相同的顶点数相同；度数序列相同。

下图来自东北大学离散数学MOOC，(1)和(2)有度数不同的顶点，不是同构的；(3)对于左下角和右上角两个顶点的边属于平行边，而(4)这两个顶点所连的边不是平行边，重数不相同，不同构。
图的同构

完全图：
- 无向完全图：简单图，每对不同顶点之间都有边。如果G有n个结点，记作，边数满足，
- 有向完全图：任何两个顶点之间都具有方向相反的边。，
- 竞赛图：基图是无向完全图的有向简单图。
子图：对于两个图，G和G‘
- 如果G’是G的真子集，那么G‘为子图，G为G’的母图。
- 如果G’是G的真子集，并且V‘=V，G’叫做生成子图。
- 如果V’是V的真子集或者E‘是E的真子集，G’叫做真子图。
补图：G为n阶无向简单图，将G补充为完全图的添加边组成的边集的图，叫做G的补图。特别的，如果G的补图和G同构，称G为自补图。
二部图：如果图G=(V, E)的结点集V可以分划成两个子集合V1和V2，使每条边都与V1的一个结点和V2的一个结点关联，则称G为二部图。
- 一部结点数为m, 另一部结点数为n的完全二部图 是指每部中每个结点都和另一部中全部结点邻接的二部图。因此完全二部图有条边。

2. 图的矩阵表示

2.1 邻接矩阵

这里数据结构与算法都讲解过了，只需要注意邻接矩阵乘积表示的含义。

定义：离散数学-图论笔记中的表示从v3到v4长度为2的路有两条。

定理3-1：设A为有向图D的邻接矩阵，离散数学-图论笔记为顶点集，则A的l次幂中的元素。

邻接矩阵

2.2 可达矩阵

定义：如果到是可达的，即至少有一条通路，那么这个元素就是1，否则就是0.
求可达性矩阵：
- 方法1：求出邻接矩阵的所有乘幂，然后进行析取。
- 方法2：按照求传递闭包的Warshall算法。Warshal算法的具体操作见我的上一篇博客。
如果G是强连通的，那么可达性矩阵必然是一个全1矩阵。

求下图的可达性矩阵

可达性矩阵求强分图：如果两个点相互可达，那么矩阵对应分量和转置矩阵的对应分量的元素都是1.将矩阵和转置矩阵进行合取，然后进行初等变换，可以看出一些规律。

我们以上面例题的图为例，

2.3 关联矩阵

无向图的完全关联矩阵：设G是一个无向图，如果V是顶点集合，E是边集合，那么一个矩阵为

性质：
- 每列只有两个1，因为一条边关联两个点。
- 每行1的个数对应结点的度数。
- 如果两列相同，说明两条边是平行边。
有向图的完全关联矩阵：略有不同，如果某个顶点是某条边的起点，那么对应元素为1，如果是终点，那么对应元素为-1，其它情况都是0。

二、图的连通性

1. 通路与回路

通路：给定一个图G=<V,E>，G中顶点和边交替的序列是连接到的通路。
回路：如果说，T叫做回路，l是回路长度。
简单通路/回路：所有的边都不相同。
初级通路/回路：所有的顶点都不相同。
复杂通路/回路：有边重复出现。

记忆：简单边，初级点。

1.1 有关通路和回路的定理

定理2-1：在n阶图中，如果从顶点离散数学-图论笔记到顶点之间存在通路，那么从到存在长度小于或等于n-1的通路。

推论：在n阶图中，如果从顶点离散数学-图论笔记到顶点之间存在通路，则到存在长度小于或等于n-1的初级通路。

定理2-2：在一个n阶图中，如果存在离散数学-图论笔记到自身的回路，则一定存在到自身长度小于等于n的回路。

推论：在一个n阶图中，如果存在离散数学-图论笔记到自身的简单回路，则一定存在长度小于或者等于n的初级回路。

2. 无向图的连通性

2.1 连通性和连通分支

连通：如果结点u和v之间存在通路，则称之连通。记作u~v
- 连通关系属于等价关系：自反性、传递性、对称性。
- 等价关系就可以求商集（划分）
连通性：任意两个顶点都连通的无向图，具有连通性。
连通分支：等价类构成的商集，我们称为G的连通分支。其个数，当K=1我们也认为连通。

2.2 距离、删除顶点及删除边

距离：表示u和v之间长度最短的通路。
- 距离的性质：
删除顶点及删除边：
- G-v：从G中删除v顶点以及与其关联的边。
- G-V‘：从G中删除V’中所有顶点。
- G-e：将e边从G中删除。
- G-E‘：将E’中所有边从G中删除

2.3 点割集、边割集

点割集：V‘是无向连通图G的顶点集的真子集，并且图中删去V’以及其关联的边后，连通分支的个数大于G的连通分支个数且具有极小性。即且具有极小性，那么V‘就是点割集。说白了，删掉后连通分支书增加了。
割点：如果点割集中只有一个顶点，那么v叫做割点。
边割集：E‘是图G=<V,E>中E的子集。如果删除E’后满足，并且具有极小性，那么E’就是边割集。
割边（桥）：边割集中只有一条边，这条边就叫做割边。

点割集：删除掉这些点集后，整个图连通分支数增加了。
- {v1,v4}，是点割集，删除v1和v4后，整个图分为v2、v3-v5-v6-v7两个连通分支。
- {v6}，是点割集，且v6是割点，删除v6后，整个图分为两个连通分支。
- {v2,v5}，不是点割集，不满足极小性，{v2}、{v5}单独已经满足点割集定义了。
边割集：
- {e1,e2}，是边割集。
- {e1,e3,e5,e6}，是边割集。
- {e8}，是桥。

结点u是图G的割点当且仅当存在两结点v和w，使v到w的任何道路都经过u。

2.4 点连通度、边连通度

点连通度：G为连通非完全图，那么G的点连通度公式：
- 规定完全图的点连通度为n-1.
- 如果G非连通，，如果，我们称G为k-连通图。
边连通度：G为连通图，那么G的边连通度
- 非连通，，称为r-边连通图。

2.5 无向图连通性的定理

如果G有割点，则，有桥
如果，那么G是1-连通图、2-连通图、…、k-连通图。边同理。
定理2-3：点连通度<=边连通度<=最小度

3. 有向图的连通性

3.1 可达性、距离

可达：单向。具有自反性、传递性。
相互可达：自反、对称、传递。
距离：类似无向图。

3.2 强连通、弱连通、单向连通

弱连通：基图为无向连通图的有向图。
单向连通：任意两个点之间，必然有一个方向是连通的。
强连通：任意两点是相互可达的。
定理2-4：强连通当且仅当有向图D中存在经过每个顶点至少一次的回路。
强分图：有向图G的极大强连通子图称为强分图。每个顶点只位于一个强分图中。

拓展：操作系统中，在某些情况下，可以使用图论的概念来建模和分析操作系统中的死锁。死锁问题可以被转化为资源分配图，其中进程和资源可以用图的节点表示，边表示资源的请求和释放关系。如果这个资源分配图中存在一个环路，那么可能存在死锁。

三. 欧拉图

1. 欧拉图的定义

欧拉通路：经过图中每一个边仅一次就走完所有结点的通路。（简单通路）
欧拉回路：经过图中每一个边仅一次就走完所有顶点的回路。
欧拉图：有欧拉回路的图。
半欧拉图：有欧拉通路但无欧拉回路的图。
说明：
- 规定平凡图是欧拉图。
- 环不影响图的连通性。

欧拉图实例

2. 无向欧拉图的判别

定理4-1：无向图是欧拉图当且仅当G连通并且无奇度数顶点。

证明：

如果说G是平凡图，显然成立。
必要性：设C是G的一条欧拉回路，G是连通的，那么任意一个顶点a必然是贡献了2度，所以a必然是偶数度结点。
充分性：通过构造的方式。设G是连通图，每个顶点都有偶数度，构造从任意顶点a开始的简单回路，简历尽量长的简单通路，这样的通路必然结束。（必须回到a），因为图中的边数是有限的。（具体请看课本，描述得有点复杂）

定理4-2：无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点。分别是起点和终点。

证明：

充分性：如果u,v是两个奇度顶点，令G‘=G∪(u,v)，那么G’连通且不存在奇度顶点，由定理4-1知道G‘为欧拉图，因此存在欧拉回路C，那么C-(u,v)就是欧拉通路。
必要性：比较显然。

3. 有向欧拉图的判别

定理4-3：有向图D是欧拉图当且仅当D是强连通的且每隔顶点的入度=出度
定理4-4：有向图是半欧拉图当且仅当D是单向连通的，并且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，其余顶点的出度和入度相等。
定理4-5：G是非平凡欧拉图当且仅当G是连通的且为若干个边不重的圈之并。

4. 构造欧拉回路

判断图G是否有回路E，如果有，选择顶点v，以v为起点找简单回路。
如果找到了，打印E边，算法停止。
如果找不到，在G-E中找一个简单回路E2，让E1和E2至少有一个公共点。
以某个公共点为起、尾点，对E1∪E2中边重排序得到简单回路，继续判断是否包含所有边。

构造欧拉回路

5. 中国邮递员问题

问题提出：在一个带权无向连通图中，构造一条回路包含所有的边的回路（边可能重复），并且使得边的权重之和最小。这个问题从邮递员问题延伸来，如何让邮递员以最短的距离走过所有的边？
算法：
- 如果图中没有奇数度结点，那么欧拉回路就是问题的解。
- 如果图中含有奇数度结点，为v1, v2,…, v2k，计算每对结点间最短道路（距离）。
- 在这些道路中选择k条道路，满足：
  - 彼此无公共的起点和终点。
  - 加和最小。
- 在G中复制这K条边。
在新图中构造欧拉回路。

例子：下图中有四个奇数度结点，求解中国邮递员问题。

可见, 离散数学-图论笔记和满足最小性要求，并且没有公共终点和起点。我们复制这两条路径，得到一个欧拉图。再通过求解欧拉回路的算法，即可得到问题的解。

四. 哈密尔顿图

1. 哈密尔顿图的定义

哈密尔顿通路：经过图中所有顶点一次仅一次的回路。（根据”简单边，初级点“，哈密尔顿通路是初级通路）
哈密尔顿回路：经过图中所有顶点一次仅一次的回路。
哈密尔顿图：具有哈密尔顿回路的图。
半哈密尔顿图：具有哈密尔顿通路但无哈密尔顿回路的图。
注意:
- 平凡图是哈密顿图。
- 环与平行边不应西昂哈密尔顿性。

哈密尔顿图

2. 无向哈密尔顿图

定理5-1：设无向图G=<V,E>是哈密尔顿图，对于任意结点V的真子集V’，均有p(G-V’)<=V’
- 证明：设C为G中一条哈密尔顿回路，，这很显然，因为哈密尔顿回路是经过所有顶点的回路。
- 又因为哈密尔顿图是G的子图，所以有
- 由传递性，可以得到答案。
推论：设无向图G=<V,E>是半哈密尔顿图，对于任意的V的真子集V1，并且V1不是空集，都有
- 证明：令是的哈密尔顿通路，令G’=G∪(u,v)，则G’为哈密尔顿图，于是

定理5-1是判断哈密尔顿图的必要条件。必要条件用来判断不是，充分性用来判断是。因此常用定理5-1判断某些图不是哈密尔顿图。

例题1：证明G是n阶无向连通简单图，若G中有割点或桥，则G不是哈密尔顿图。

解答：设V是割点，离散数学-图论笔记，根据定理5-1，G不是哈密尔顿图。

定理5-2：设G是无向简单图，若对任意不相邻的顶点和，均有，则G中存在哈密尔顿通路。
推论：设G为n(n>=3)阶无向简单图，若对于G中任意两个不相邻的顶点都有$d(v_i)+d(v_j)>=n，则G中存在哈密尔顿回路，从而为哈密尔顿图。

定理5-2是半哈密顿图的充分条件，但不是必要条件。

例如，长度为n-1的路径构成的图不满足这个条件，但它显然是半哈密尔顿图。

定理5-2的推论同样不是哈密尔顿图的必要条件

例如，G为长为n的圈，显然不满足条件，但仍然是哈密尔顿图。可知，离散数学-图论笔记均为哈密尔顿图。

3. 有向哈密尔顿图

定理5-3：若D为n(n>=2)的竞赛图，则D中具有哈密尔顿通路。

竞赛图的基图是无向连通图，

4. 判定哈密尔顿回路

至今是个世界难题，可行的办法：

观察法
满足充分条件
通过必要条件排除不含有H回路的图。

5. 图的闭包

定义：如果n(>2)阶简单连通图G=(V, E)存在非邻接结点u和v，使d(u)+d(v)  n，则构造新图G+ uv，并在新图上重复上述步骤，直到不存在这种点为止，所得之图称为G的闭包，并记为cl(G)。
定理：简单连通图是哈密尔顿图的充要条件是其闭包为哈密尔顿图。

五. 最短通路问题

1. 基础概念

带权图
带权图中一条通路的长度：通路上各边的权值总和。
最短通路算法：Dijkstra

这块内容见《数据结构与算法》啦~~
这里不多赘述。

2. 旅行商问题

旅行商问题的定义：设G<V,E,W>为一个n阶完全带权图，各边的权值非负，求G中的一条最短的哈密尔顿回路。这就是旅行商问题。
完全带权图中不同的哈密尔顿回路数：
- 中有条不同的哈密尔顿回路。
- 可见用穷举法解决旅行商问题是阶乘的复杂度。

案例：求下图所示的K4的最短哈密尔顿回路。

六. 平面图问题

1. 基本概念

平面图：将G除了顶点外无边相交地画在平面上。这种画法称为图的平面表示，也叫平面嵌入。
- 和都不是平面图。
如果图是平面图，那么子图是平面图。
如果子图是非平面图，那么图是非平面图。
- 据此，我们可以知道，以及都是非平面图。
平行边和环不影响平面性。

面：由边划分出来的区域。
无限面/外部面：面积无限大的面。
有限面/内部面：面积有限的面。
边界：回路组。回路组可以是非连通回路之并。
次数：边界的长度，记作deg。
r1区域，边界为ABCDFDA，deg(r1)=6
r2区域，边界为ABCA，deg(r2)=3
r3区域，边界为ACDA，deg(r3)=3
r0区域，边界为ADA，deg(r4)=2

定理：平面图各个面的deg之和=边数的二倍

以上图为例，次数之和=14，边数=7，满足。

如果平面图G有K个面，可用表示，不需要指出外部面。
deg(R1)=1
deg(R2)=3
deg(R3)=2
deg(R0)=8，这体现了回路组可以是非连通回路之并。分别是abcdeafg

2. 欧拉公式

定理7-2：设G是n阶m边r面的连通平面图，n-m+r=2。
证明：
- m=0，平凡图，成立。
- 设m=k(k>=1)为真，m=k+1时，分情况讨论。
  - 如果是G无回路，G为树，如果要将k+1变到k，我们删除一条边，即删除一个叶子结点， n-1-(m-1)+r=n-m+r=2，等式依旧成立。
  - 如果G有圈，圈上删除一条边，这条边是两个面的公共边，删除后r-1，所以n-(m-1)+r-1=2仍然不变。
定理7-3：设G是具有k个连通分支的平面图，则n-m+r=k+1

理解：外部公共面会被加k次，所以需要减去k-1。

即当G是连通的时候，等式右边是r；当G是不连通的时候，等式右边是k+1

定理7-4：设G为连通的平面图，且，则
- 证：解得：也可以得到：
- 推论：中，m=10，3n-6=3*5-6=9，不满足，所以不是平面图。不满足关系，所以不是平面图。
定理7-5：在具有k(k>=2)个连通分支的平面图中，
定理7-6：设G是n(n>=3)阶m边的简单平面图，则

案例：证明若G为简单平面图，则

证明：当n<=6，结论为真。当n>=7时，如果离散数学-图论笔记，根据握手定理，2m>=6n，得到m>=3n，与定理7-6矛盾。

3. 平面图的判定

同胚：如果G1和G2是同构图，或者经过反复插入或删除2度顶点后得到的两个图同构，则称G1和G2同胚。

定理7-7【库拉托夫斯基（Kuratowski）定理】：G是平面图当且仅当G中不含与或同胚的子图。

库拉托夫斯基定理

七. 图着色问题

对于图的着色问题，可以转化为对其对偶图的着色问题。

1. 对偶图

对偶图的定义：设G是某平面图的某个平面嵌入，构造G的对偶图G*如下：
- 在G的面中放置G*的顶点
- 若G中的边e在面与的公共边界上，做的边与e相交，即)，且不与其它任何边相交。
- 若e只是面的一个面边界，则是中的顶点端点的环，即

对偶图

定理8-1：设置是连通平面图G的对偶图，和n、m、r分别是和G的顶点数、边数和面数。那么，设G*的顶点位于G的面R_i中，则

2. 自对偶图

定义：设G是平面图G是对偶图，如果说G和G是同构的，就称G*为G的自对偶图。
轮图：在n-1阶圈内放置一个顶点，连接这个顶点与这个圈轮上的所有顶点，所得的n阶简单图称作n阶轮图，记做Wn。
n阶轮图都是自对偶图。

3. 点着色

点着色：给G的每个顶点都涂上颜色，保证相邻的顶点的颜色都是不同的。
k着色：能够用k种颜色对G进行点着色。
色数：，表示图G是k可着色的，但不是k-1可着色的。

4. 着色方法

Welch Powell着色方法：
- 对G按照顶点的度数进行递减排序，排序不唯一。
- 用第一种颜色对第一个结点进行着色，并按照排序将与第一个点不相邻的结点度都着上相同的颜色。
- 用另一种颜色对尚未着色的点进行排序，重复上述过程。

图着色

八. 树

1. 无向树及其性质

这块内容可以参考数据结构的内容。

无向树：连通无回路的无向图。
森林：每个连通分支都是树的无向图。
叶子结点：度数为1的结点。
分支结点：度数>=2的结点。

1.1 无向树的等价定义

定理9-1：设置G=<V,E>是n阶m边的无向图，以下命题是等价的。
- G是树；
- G中任意两个顶点存在唯一的路径。
- G中无回路，且m=n-1
- G是连通的，且m=n-1
- G是连通的且G中任何边都是桥。
- G中无回路，但在任何两个不同的顶点之间加一条边，在所得图中得到唯一的一个含新边的回路。

1.2 结合握手定理

定理9-2：设T是n阶非平凡的无向树，则T中至少含有两片树叶。
- 证明：设T有x片树叶，握手定理：2m = 2(n-1) = 度数之和 >=x + 2(n-x)，解x>=2。

一道小例题：

这块的题用树的性质 + 握手定理基本能解决。

2. 生成树

2.1 生成树的定义

G的生成树：T是G的子图并且是树。
生成树T的树枝：T中的边。
生成树T的弦：不在T中的边。
生成树T的余树T补：全体弦组成的集合的导出子图。（T补并不是一棵树）

2.2 生成树存在的条件

定理10-1：无向图具有生成树当且仅当G连通。
推论1：G是n阶m边的无向连通图，那m>=n-1
推论2：T补的边数为m-n+1

例题：G有6个结点，10条边的连通图，删去多少条边，才得到一颗生成树？

10-6+1 = 5，即删除T补。

2.3 基本回路系统

定义：设T是n阶m条边的无向连通图G的一棵生成树，设为T的弦。设为T添加弦产生的只含弦其它边都是树枝的圈，那么称为G的对应树T的弦的基本回路或基本圈，并称为G对应T的基本回路系统，称m-n+1为G的圈秩，记作
如何求基本回路：设弦e=(u,v)，先求T中u到v的路径，再并弦e，即得到e的基本回路。
基本割集系统：设T是n阶连通图G的一颗生成树，是T的树枝，是G的只含树枝的割集，则称为G的对应于生成树T由树枝生成的基本割集，称为G对应T的基本割集系统，n-1是G的割集秩。
如何求基本割集：设e是T的树枝，T-e为两棵小树T1、T2，令，则为e对应的基本割集。