离散数学-图论笔记_东北大学离散数学网课笔记

前言

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

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

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

---

一、图论的基础概念

1. 图的定义

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

• 简单图：无环，无平行边。
  • 一般用$<u,v>$表示有向边，$(u,v)$表示无向边。
• 多重图：有平行边。
• 度：$d(v)$，入度：$d^{-}(v)$，出度$d^{+}(v)$，最大度：$\Delta (D)$，最小度：$\delta (D)$
• 握手定理：
  • 无向图中，每条边贡献2度。$$\sum _{i=1}^{n}d(v_i)=2m$$
  • 有向图中，每条边贡献2度，入度=出度。$$\sum _{i=1}^n{d}^{+}(v_i)=\sum _{i=1}^n{d}^{-}(v_i)=m$$
• 推论：任何图中，奇数度顶点的个数是偶数个。即必然成对出现。
• n阶k正则图：满足$\Delta (G)=\delta (G)=k$的无向图，每个顶点都具有相同的度数。
  
  上图来自引用4，分别是1正则、2正则、5阶2正则、4阶3正则、5阶3正则、5阶4正则。

案例：下列哪个哪些序列是一个图的度数序列？
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，如果我们将顶点看作是数据，将边看成是数之间的运算，实际上这是一种系统。如果存在双射函数：$f:V_1\to V_2$，对于$v_i,v_j\in V_1$，$(v_i,v_j)\in E_1$当且仅当$(f(v_i),f(v_j))\in E_2$，并且$(v_i,v_j)和(f(v_i),f(v_j))$的重数（平行边个数）相同，则称G1、G2是同构的。记作$G_1\cong G_2$
  • 同构的必要条件：边数相同；顶点数相同；度数相同的顶点数相同；度数序列相同。

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

• 完全图：

  • 无向完全图：简单图，每对不同顶点之间都有边。如果G有n个结点，记作$K_n$，边数满足$m=\frac{n(n-1)}{2}$，$\Delta =\delta =n-1$
  • 有向完全图：任何两个顶点之间都具有方向相反的边。$m=n(n-1)$，${\Delta }^{+}={\delta }^{+}=n-1$
  • 竞赛图：基图是无向完全图的有向简单图。
    

• 子图：对于两个图，G和G‘

  • 如果G’是G的真子集，那么G‘为子图，G为G’的母图。
  • 如果G’是G的真子集，并且V‘=V，G’叫做生成子图。
  • 如果V’是V的真子集或者E‘是E的真子集，G’叫做真子图。
    

• 补图：G为n阶无向简单图，将G补充为完全图$K_n$的添加边组成的边集的图，叫做G的补图。特别的，如果G的补图和G同构，称G为自补图。
  

• 二部图：如果图G=(V, E)的结点集V可以分划成两个子集合V1和V2，使每条边都与V1的一个结点和V2的一个结点关联，则称G为二部图。

  • 一部结点数为m, 另一部结点数为n的完全二部图$K_{m,n}$ 是指每部中每个结点都和另一部中全部结点邻接的二部图。因此完全二部图$K_{m,n}$有$m\ast n$ 条边。

2. 图的矩阵表示

2.1 邻接矩阵

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

定义：$(A(G_1){)}^2$中的$a_{34}=2$表示从v3到v4长度为2的路有两条。

定理3-1：设A为有向图D的邻接矩阵， V = { v 1 , v 2 , v 3 , . . . } V=\{v_1,v_2,v_3,...\} V={v1​,v2​,v3​,...}为顶点集，则A的l次幂$A_l(l>=1)$中的元素。

即矩阵所有元素之和表示各个长度通路的条数。

2.2 可达矩阵

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

求下图的可达性矩阵

PS：上图和下图来自东北大学离散数学MOOC，采用方法1进行求可达性矩阵，发现乘幂出现周期性，然后析取即可。

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

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

PS：上图来自东北大学离散数学MOOC，这个方阵表示v1和v3相互可达，构成了一个强分图；v2、v4、v5是两两可达的，也构成了一个强分图。

2.3 关联矩阵

• 无向图的完全关联矩阵：设G是一个无向图，如果V是顶点集合，E是边集合，那么一个矩阵为$$\{\begin{array}{l}1-v_i和e_j关联\\ 0-else\end{array}$$

PS：上面的图都来自东北大学离散数学MOOC，帮助读者理解关联矩阵。

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

二、图的连通性

1. 通路与回路

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

记忆：简单边，初级点。

1.1 有关通路和回路的定理

定理2-1：在n阶图中，如果从顶点$v_i$到顶点$v_j$之间存在通路，那么从$v_i$到$v_j$存在长度小于或等于n-1的通路。

推论：在n阶图中，如果从顶点$v_i$到顶点$v_j$之间存在通路，则$v_i$到$v_j$存在长度小于或等于n-1的初级通路。

定理2-2：在一个n阶图中，如果存在$v_i$到自身的回路，则一定存在$v_i$到自身长度小于等于n的回路。

推论：在一个n阶图中，如果存在$v_i$到自身的简单回路，则一定存在长度小于或者等于n的初级回路。

2. 无向图的连通性

2.1 连通性和连通分支

• 连通：如果结点u和v之间存在通路，则称之连通。记作u~v
  • 连通关系属于等价关系：自反性、传递性、对称性。
  • 等价关系就可以求商集（划分）
• 连通性：任意两个顶点都连通的无向图，具有连通性。
• 连通分支：等价类构成的商集 V / R = { v 1 , v 2 , . . . , v k } V/R=\{v_1,v_2,...,v_k\} V/R={v1​,v2​,...,vk​}，我们称$G[V_1]...G[V_k]$为G的连通分支。其个数$p(G)=k(>=1)$，当K=1我们也认为连通。
  
  Ps：上图来自东北大学的MOOC。由p表示连通分支的个数，观察知$p(G1)=3$，$P(G2)=2$，$P(G3)=1$

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

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

2.3 点割集、边割集

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

Ps：上图来自东北大学离散数学MOOC。以上图为例，理解这个概念。

• 点割集：删除掉这些点集后，整个图连通分支数增加了。
  • {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的点连通度$\kappa$公式： κ ( G ) = m i n { V ′ ∣ V ′ 为点割集 } \kappa(G)=min \{V'|V'为点割集\} κ(G)=min{V′∣V′为点割集}
  • 规定完全图$K_n$的点连通度为n-1.
  • 如果G非连通，$\kappa (G)=0$，如果$\kappa (G)=k$，我们称G为k-连通图。
• 边连通度：G为连通图，那么G的边连通度 λ ( G ) = m i n { E ′ ∣ E ′ 为边割集 } \lambda(G)=min\{E'|E'为边割集\} λ(G)=min{E′∣E′为边割集}
  • 非连通，$\lambda (G)=0$，$\lambda (G)=r$称为r-边连通图。

2.5 无向图连通性的定理

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

3. 有向图的连通性

3.1 可达性、距离

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

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

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

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

三. 欧拉图

1. 欧拉图的定义

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

Ps：上图来自东北大学离散数学MOOC。根据定义，欧拉图是有欧拉回路的图，(1)(4)是欧拉图，(2)(5)是半欧拉图，(3)(6)不是欧拉图。

2. 无向欧拉图的判别

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

证明：

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

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

证明：

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

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条边。
• 在新图中构造欧拉回路。

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

两两之间的最短道路为：
$P_{a-c}=3(abc),P_{a-e}=3(abe)，P_{a-h}=5(abcfh)$
$P_{c-e}=2(cbe),P_{e-h}=3(egh),P_{c-h}=2(cfh),$

可见, $P_{a-e}$和$P_{c-h}$满足最小性要求，并且没有公共终点和起点。我们复制这两条路径，得到一个欧拉图。再通过求解欧拉回路的算法，即可得到问题的解。

四. 哈密尔顿图

1. 哈密尔顿图的定义

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

Ps：上图来自东北大学离散数学MOOC。G1是哈密尔顿图，G2是半哈密尔顿图，G3既不是哈密尔顿图也是半哈密尔顿图。

2. 无向哈密尔顿图

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

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

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

解答：设V是割点，$p(G-v)>=2>|v|=1$，根据定理5-1，G不是哈密尔顿图。

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

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

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

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

例如，G为长为n的圈，显然不满足条件，但仍然是哈密尔顿图。可知，$K_n(n>=3)$均为哈密尔顿图。

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阶完全带权图$K_n$，各边的权值非负，求G中的一条最短的哈密尔顿回路。这就是旅行商问题。
• 完全带权图$K_n(N>=3)$中不同的哈密尔顿回路数：
  • $K_n$中有$(n-1)!$条不同的哈密尔顿回路。
  • 可见用穷举法解决旅行商问题是阶乘的复杂度。

案例：求下图所示的K4的最短哈密尔顿回路。
Ps：上图来自东北大学离散数学MOOC。
C1=abcda，W1=10
C2=abdca，W2=11
C3=acbda，W3=9(最短)

六. 平面图问题

1. 基本概念

• 平面图：将G除了顶点外无边相交地画在平面上。这种画法称为图的平面表示，也叫平面嵌入。
  • $K_5$和$K_{3,3}$都不是平面图。
• 如果图是平面图，那么子图是平面图。
• 如果子图是非平面图，那么图是非平面图。
  • 据此，我们可以知道，$K_n(n>=6)$以及$K_{3,n}$都是非平面图。
• 平行边和环不影响平面性。

上图中(a)和(b)经过重新绘制后变成(e)和(f)，它们不包含任何交叉边，是一个平面图。而 c、d分别是$K_{3,3}$和$K_5$，都不是平面图。

• 面：由边划分出来的区域。
• 无限面/外部面：面积无限大的面。
• 有限面/内部面：面积有限的面。
• 边界：回路组。回路组可以是非连通回路之并。
• 次数：边界的长度，记作deg。
  
  Ps：上图来自东北大学离散数学MOOC
• 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个面，可用$R_1,R_2,...,R_k$表示，不需要指出外部面。
  
  Ps：上图来自东北大学离散数学MOOC。
• 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为连通的平面图，且$deg(R_i)>=l,l>=3$，则$m<=\frac{l}{l-2}(n-2)$
  • 证：$$2m=\sum _{i=1}^{r}deg(R_i)>=l\ast r=l(2+m-n)$$解得：$$m<=\frac{l}{l-2}(n-2)$$也可以得到：$$m<=3n-6$$
  • 推论：$K_5$中，m=10，3n-6=3*5-6=9，不满足，所以不是平面图。$K_{3,3}同理，m=9,3n-6=12$不满足关系，所以不是平面图。
• 定理7-5：在具有k(k>=2)个连通分支的平面图中，$m<=\frac{l}{l-2}(n-k-1)$
• 定理7-6：设G是n(n>=3)阶m边的简单平面图，则$m<=3n-6$

案例：证明若G为简单平面图，则$\delta (G)<=5$

证明：当n<=6，结论为真。当n>=7时，如果$\delta >=6$，根据握手定理，2m>=6n，得到m>=3n，与定理7-6矛盾。

3. 平面图的判定

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

PS：上图来自引用3，他们删去或者反复插入2度顶点后显然同构，所以这些图同胚。

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

应用库拉托夫斯基定理，通过同胚操作，可证明上图均为非平面图。

七. 图着色问题

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

1. 对偶图

• 对偶图的定义：设G是某平面图的某个平面嵌入，构造G的对偶图G*如下：
  • 在G的面$R_i$中放置G*的顶点$v_i^{\ast }$
  • 若G中的边e在面$R_i$与$R_j$的公共边界上，做$G^{\ast }$的边$e^{\ast }$与e相交，即$e^{\ast }=(v_i^{\ast },v_j^{\ast }$)，且$e^{\ast }$不与其它任何边相交。
  • 若e只是面$R_i$的一个面边界，则$e^{\ast }$是$R_i$中$G^{\ast }$的顶点$v_i$端点的环，即$e^{\ast }=(v_i^{\ast }+v_j^{\ast })$

PS：上图来自东北大学离散数学MOOC，我们首先对每个面R1、R2、R3分别放置一个顶点，$v_1^{\ast }$、$v_2^{\ast }$、$v_3^{\ast }$。对于v1-v2我们防止一条交叉边，同理对于v1-v4、v2-v3、v3-v4我们都放置一条边。值得注意的是，v2-v5这条边只是R3一个面的边界，我们所做的交叉只关联R3中的顶点$v_3^{\ast }$，构成一个环。

• 定理8-1：设置$G^{\ast }$是连通平面图G的对偶图，$n^{\ast }、m^{\ast }、r^{\ast }$和n、m、r分别是$G^{\ast }$和G的顶点数、边数和面数。那么$$n^{\ast }=r，m^{\ast }=m，r^{\ast }=n$$，设G*的顶点$v_i\ast$位于G的面R_i中，则$d(v^{\ast })=deg(R_i)$

2. 自对偶图

• 定义：设G是平面图G是对偶图，如果说G和G是同构的，就称G*为G的自对偶图。
  

• 轮图：在n-1阶圈内放置一个顶点，连接这个顶点与这个圈轮上的所有顶点，所得的n阶简单图称作n阶轮图，记做Wn。

• n阶轮图都是自对偶图。
  
  Ps：上图来自东北大学离散数学MOOC，上述轮图都是自对偶图。

3. 点着色

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

PS：上图来自东北大学离散数学MOOC，我们可以分别求其色数。色数分别是2、3、4、5.

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。

一道小例题：

设阶数n，边=n-1，4度顶点个数n-7。根据握手定理：2m = 2(n-1) = 4(n-7) + 5 + 2 + 3 ==》n=8，从而可以画出非同构的无向树。

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

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的一棵生成树，设$e_1^{{}^{\prime }},e_2^{{}^{\prime }},...e_{m-n+1}^{{}^{\prime }}$为T的弦。设$C_r$为T添加弦$e_r^{{}^{\prime }}$产生的只含弦$e_r^{{}^{\prime }}$其它边都是树枝的圈，那么$C_r$称为G的对应树T的弦$e_r^{{}^{\prime }}$的基本回路或基本圈，并称$C_1,C_2,...,C_{m-n+1}$为G对应T的基本回路系统，称m-n+1为G的圈秩，记作$\xi (G)$
• 如何求基本回路：设弦e=(u,v)，先求T中u到v的路径${\Gamma }_{uv}$，再并弦e，即得到e的基本回路。
• 基本割集系统：设T是n阶连通图G的一颗生成树，$e_1...e_{n-1}$是T的树枝，$S_i$是G的只含树枝的割集，则称$S_i$为G的对应于生成树T由树枝$e_i$生成的基本割集，称 { S 1 . . . S n − 1 } \{S_1 ... S_{n-1}\} {S1​...Sn−1​}为G对应T的基本割集系统，n-1是G的割集秩。
• 如何求基本割集：设e是T的树枝，T-e为两棵小树T1、T2，令 S e = { e ∣ ∈ E ( G ) 且 e 的两个端点分别属于 T 1 和 T 2 } S_e=\{e | \in E(G) 且e的两个端点分别属于T_1和T_2 \} Se​={e∣∈E(G)且e的两个端点分别属于T1​和T2​}，则$S_e$为e对应的基本割集。

案例：下图中实现边构成生成树，求基本回路系统和基本割集系统。

Ps：上图来自东北大学离散数学MOOC。
首先求基本回路系统，这是针对弦而言的。对于弦e的基本回路为$C_e$=ebc，弦f的基本回路为$C_f$=fabc，弦g的基本回路$C_g$=gabcd，基本回路系统为三条回路构成的集合。其次，求基本割集系统，这是针对树枝而言的， S a = { a , f , g } , S c = c , e , f , g , S b = b , e , f , g , S d = d , g , S 基 = S a , S b , S c , S d S_a=\{a,f,g\},S_c={c,e,f,g},S_b={b,e,f,g},S_d={d,g},S_基={S_a,S_b,S_c,S_d} Sa​={a,f,g},Sc​=c,e,f,g,Sb​=b,e,f,g,Sd​=d,g,S基​=Sa​,Sb​,Sc​,Sd​

2.4 最小生成树

这部分内容见数据结构与算法，主要考察Kruskal算法。

3. 根树

这块内容在数据结构与算法这门课中有涉及，而且主要在那门课进行考察，这门课重复考察没有意义。

---

参考资料

1. shuaihui-关于自补图的认识和构造（无证明）
2. 东北大学离散数学MOOC
3. 湫沨-离散数学笔记（10.4）平面图
4. 未知作者的离散数学PPT