离散数学-图论知识总结（修改版）

文章目录

• 图论
• • 基本概念
  • 矩阵
  • • 邻接矩阵
    • 可达性矩阵
    • 完全关联矩阵
    • 矩阵与图连通性的关系：
  • 特殊图
  • • 无向欧拉图
    • • 定义
      • 判定定理
    • 有向欧拉图
    • • 定义
      • 定理
    • 哈密尔顿图
    • • 定义
      • 必要条件
      • 充分条件
    • 平面图
    • • 定义
      • 欧拉公式
      • 库拉托夫斯基图
      • 对偶图
      • 着色
  • 树
  • • 无向树
    • • • 性质
        • 特点
        • 生成树
    • 有向树
    • • 根树
      • k叉树
      • 最优树
      • 前缀码

图论

基本概念

1. 无序对和无序积：集合A&B={(a,b)|a ∈ \in ∈A,b ∈ \in ∈B},(a,b)=(b,a)
2. 图：一个序偶<V,E>,V是结点集，E：边集，E中每个元素都有V中的结点对与之对应称之边。
3. 图的表示：集合表示，图形表示，邻接矩阵
4. 若两个结点vi,vj是边e的端点，则称vi,vj互为邻接点，具有公共节点的两条边称为邻接边，两个端点相同的边称为环或者自回路。图中不与任何点相邻接的结点叫孤立节点
5. 仅含一个结点的零图叫做平凡图。
6. 图的分类：无向图，有向图，混合图，多重图（有平行边），线图（非多重图），简单图（无环线图），赋值图，如G=<V,E,g>，g是从E到非负实数集合的函数
7. 若V1 ⊆ \subseteq ⊆V,E1 ⊆ \subseteq ⊆E,则G1为G的子图，记为G1 ⊆ \subseteq ⊆G
8. 若 V 1 = V , E 1 ⊆ E V1=V,E1\subseteq E V1=V,E1⊆E,G1是G的生成子图
9. 设 V 2 ⊆ V V2\subseteq V V2⊆V且 V 2 ≠ ∅ V2\neq \empty V2​=∅以V2为结点集，以两个端点均在V2中的边的全体边集的G的子图称为V2的导出子图

10. 完全图：无向简单图：所有节点之间都有边相连，记为Kn

    ​ 有向简单图：任意两个结点都有两条方向相反的有向边相连。

    其矩阵除对角线上的元素为0，其余元素为1

11. 补图：G为简单图<V,E>，G‘为完全图<V1,E1>。G1=<V,E1-E>为G的补图，记为 G ‾ \overline{G} G（从完全图中删除G中的边）两个结点在 G ‾ \overline{G} G中相邻 ↔ \leftrightarrow ↔在G中不相邻
12. 度数：图G=<V,E>中以结点v ∈ \in ∈V为端点的次数之和称为结点v的度数，记为deg(v),环记两次，有向图中以v为始点的次数称为v的出度，记为deg + ^{+} +(v)以结点v为终点的次数称为v的入度，记为deg − ^{-} −(v).deg(v)=入度加出度。deg(v)=1称为悬挂结点，以悬挂结点的边称为悬挂边。
    • 用邻接矩阵计算度数：若G是无向图：deg(vi)= ∑ k = 1 n a i k + a i i , 或 者 = ∑ k = 1 n a k i + a i i \sum_{k=1}^{n}a_{ik}+a_{}ii,或者=\sum_{k=1}^{n}a_{ki}+a_{ii} ∑k=1n​aik​+a​ii,或者=∑k=1n​aki​+aii​。有向图：deg+(vi)= ∑ k − 1 n a i k \sum_{k-1}^{n}a_{ik} ∑k−1n​aik​；deg-(vi)= ∑ k = 1 n a k i \sum_{k=1}^n{a_{ki}} ∑k=1n​aki​

13. 握手定理：度数总和=2|E|。

    推论：度数为奇数的结点个数为偶数。

    有向图出度之和=入度之和=边数

14. 图的同构：设两个图G=<V,E>,G’=<V,E’>,若存在V → \rightarrow →V’，使得对于任意e=(vi,vj) ∈ \in ∈E，当且仅当e’=(g(vi),g(vj)) ∈ \in ∈E’，并且e和e’重数相同，称G与G’同构。
15. 同构的必要条件：结点数目相等，边数相等，度数相同的节点数相同
16. 路：给定图G=<V,E>，设v0,…vn ∈ \in ∈V，e1,e2,…,en ∈ \in ∈E，其中ei是关联结点vi-1和vi的边，交替序列voe1v1e2…envn称为连接v0到vn的路。若路中的所有边全不相同，则称此路为一条迹。若路中所有节点不同，则称此路为通路。
    • v0和vn分别为该路的起点和终点，统称为路的端点。
    • 路中边的条数称为路的长度。
    • 若v0=vn,称为回路。
17. 在一个具有n个结点的图中，如果从结点vj到结点vk存在一条路，则从结点vj到结点vk必存在一条不多于n-1条边的路
    • 在无向图中G中，如果从结点vj到结点vk存在一条路，则必存在一条从vj到vk而长度小于n的通路
18. 无向图的连通性
    • 设G=<V,E>是一个图，对vi,vj ∈ \in ∈V,从vi 到vj如存在是一条路则称结点vi和vj 是连通的
    • 设G=<V,E>是一个无向图，若G中任意两个结点之间都是连通的，则称该无向图G是一个无向连通图，否则，则称G是一个非连通图（分离图）
    • 设G=<V,E>是一个无向图，该无向图G中的每个连通的划分块称为G的一个连通分支，用W(G)表示G中的连通分支数。无向图是连通图当且仅当W(G)=1
19. 删除结点和边
    • 删除结点：在图中删除结点v是把v以及与v关联的边都删除
    • 删除边：仅删除该边
20. 割点：设无向图G=<V,E>是连通的，若有结点集V1是V的真子集，使得图G删除了V1的所有结点后，所得的子图是不连通的，而删除了V1的任意子集后，所得的子图还是连通图则称集合V1是图G的点割集。若某一个结点就构成点割集，则称该结点是割点。
    • 一个连通图删除它的一个点割集后，将分成两个或者多于两个连通分支
    • 若G不是完全图，定义k(G)=min{V1|V1是G的点割集}为G的点连通度。连通度是为了产生一个不连通图需要删除点的最少个数。
21. 割边：设无向图G=<V,E>是连通的，若有边集E1是E的真子集，使得图G删除了E1 的所有边后，所得的子图是不连通的，而删除了E1的任意真子集后，所得子图仍是连通图。则称集合E1是图G的边割集。若某一边构成边割集，则称该边是割边（桥）。
    • G的割边也就是G的一条边e使得W(G-r)>W(G)。与点连通度相似，定义非平凡图G的连通度为： λ ( G ) = m i n E 1 ∣ E 1 是 G 的 边 割 集 \lambda(G)=min{E1|E1是G的边割集} λ(G)=minE1∣E1是G的边割集,边连通度 λ ( G ) \lambda(G) λ(G)是为了产生一个不连通图需要删去边的最少数目。
    若存在割点，则存在割边
22. 有向图的连通性：设G=<V,E>是一个有向图。对vi.vj ∈ \in ∈V,从vi到vj如存在一条路，则称结点vi到vj是可达的。
    • 设G=<V,E>是一个有向图，若略去G中所有有向边的方向后得到的无向图是一个无向连通图，则称该有向图G是一个弱连通图。
    • 设G=<V,E>是一个有向图，若G中任意两个结点之间至少单方向是可达的，则称该有向图G是一个单侧有向图。（经过一条经过所有结点至少一次的通路）
    • 设G=<V,E>是一个有向图，若G中任意两个结点之间都是相互可达的，则称该有向图是一个强连通图。
23. 一个有向图G是强连通图当且仅当G中有一个回路，至少包含每一个结点一次

    

矩阵

邻接矩阵

设G=<V,E>是一个简单图，，则n阶方阵A(G)=(aij) n × n _{n\times n} n×n​称为G的邻接矩阵。其中：

令C=A m ^{m} m，此时cij表示从vi到vj长度为m的路的数目。

可达性矩阵

设G=<V,E>是一个简单图，V={v1,v2,v3,…,vn}， B n = ( b i j ) n × n = A + A 2 + A 3 + . . . A n Bn=(bij)_{n\times n}=A+A^{2}+A^{3}+...A^{n} Bn=(bij)n×n​=A+A2+A3+...An，则bij表明了从结点vi到vj长度为1至n的所有路数目之和。如bn=0,则表明从结点vi到vj是不可达的。如bij$\neq$0,则表明从结点vi到vj至少有长度为m(1<=m<=n)的通路.

定义：设G=<V,E>是一个简单图，V={v1,…vn}，定义一个n阶方阵P=(pij) [ n × n ] _[n\times n] [​n×n]其中：

利用布尔矩阵运算直接求可达性矩阵：

P= A ∨ A ( 2 ) ∨ A ( 3 ) ∨ . . . ∨ A n A\lor A^{(2)}\lor A^{(3)}\lor ...\lor A^{n} A∨A(2)∨A(3)∨...∨An

A m = A ∧ A ∧ A . . . ∧ A A^{m}=A\land A\land A...\land A Am=A∧A∧A...∧A

完全关联矩阵

定义：给定无向图C，令v1,v2,…,vp和e1,e2,…,eq分别记为G的结点和边，则矩阵M(G)=(mij)，其中：

如：

定义：给定简单有向图G=<V,E>，V={v1.v2,…,vp},E={e1,e2,…,eq},p*q阶矩阵M(G)=（mij），其中：

如：

矩阵与图连通性的关系：

• 无向简单图G是连通图当且仅当它的可达性矩阵P所有元素均为1
• 有向简单图G是强连通图当且仅当它的可达性矩阵P的所有元素均为1
• 有向简单图G是单侧连通图当且仅当它的可达性矩阵P及其转置矩阵经布尔求（并）和运算后所得矩阵中除对角线以外其余元素均为1
• 有向简单图G是弱连通图当且仅当它的邻接矩阵A及其转置矩阵经布尔求和(并)运算后作为新的邻接矩阵而求出的可达性矩阵中所有元素均为1

特殊图

无向欧拉图

定义

给定G是一个无孤立节点的无向图，若存在一条路（回路），经过图中每边一次且仅一次，则此路（回路）为该图的一条欧拉路（回路）。具有欧拉回路的图叫做欧拉图。

判定定理

无向图G=<V,E>具有一条欧拉路当且仅当G是连通的，且仅有0个或者两个奇度数结点。

无向图G=<V,E>是欧拉图当且仅当G是连通的且G的所有结点的度数都是偶数

有向欧拉图

定义

给定G是一个无孤立节点的有向图，若存在一条单向路（回路）经过图中每边一次且仅一次，则称此单向路（回路）为该图的一条单向欧拉路（回路）。具有单向欧拉回路的图叫做欧拉图。

定理

有向图G=<V,E>具有一条单向欧拉路当且仅当G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大一，另一个结点的出度比入度大1

有向图G=<V,E>是欧拉图当且仅当G是连通的，且所有结点的入度等于出度

哈密尔顿图

定义

给定G是一个无孤立节点的无向图，若存在一条路（回路），经过图中每个结点一次且仅一次，则此路（回路）为该图的一条哈密尔顿路（回路）。具有哈密尔顿回龙路的图称为哈密尔顿图。

必要条件

若图G=<V,E>具有哈密尔顿回路，则对于结点集V（度数高）的每一个非空子集S均有W(G-S) ≤ \leq ≤|S|成立，其中W(G-S)是G-S的连通分支数。

充分条件

设G具有n个结点的简单图，如果G中每一对不相邻结点的度数之和大于等于n-1,则在G中存在一条哈密尔顿路。

设图G是具有n个结点的简单图，如果G中每一对结点的度数大于等于n，则在G中存在一条哈密尔顿回路。

设G是n结点简单无向图，n>=3，任意结点v,deg(v)>=n/2,则是哈密而顿图

闭包：给定图G=<V,E>有n个结点，若将图G中的度数之和至少是n的非邻接结点连接起来得G‘，对图G’重复上述步骤，直到不再有这样的结点为止，所得的图称为原图G的闭包。记作C(G).

当且仅当一个简单图的闭包是哈密尔顿图时，这个简单图是哈密尔顿图

平面图

定义

设G是一个无向图，若经过某种改画，能把G中所有结点和边都画在一个平面上，使得任何两边除公共结点之外没有其他交叉点，则称G为平面图，若G无论如何改画，它们的边之间总有交叉现象出现，则G是非平面图。结点数小于等于4的都是平面图。

由边所包围的区域称为G的一个面，包围这个面所构成的回路称为这个面的边界，面的边界长度叫做次数。

结点数<4都是平面图

一个有限平面图面的次数之和等于其边数的两倍。

欧拉公式

定理：设G=<V,E>是一个连通的平面图

• 若它有v个结点，e条边，r个面，则有：v-e+r=2
• 若G中无环，且每一个面至少由三条边围成，则有：e<=3v-6
• 若G中无环，且每一个面至少由k条边围成，则有：(k-2)e<=kv-2k

库拉托夫斯基图

插入和删除一个新的度数为2的结点，使一条边分成两条边，或者对于关联于一个度数为2的结点的两条边，去掉这个结点，是两条边变成一条边，这些都不影响图的平面性。

定义：给定两个图G1和G2，若它们是同构的，或通过反复插入或去除度数为2 的结点后，使得G1和G2同构，则称该图是在2度结点内同构（同胚）

定理：一个图是平面图，当且仅当它不包含与k33或K5在2度结点内同构的子图。K33和K5常称为库拉托夫斯基图

对偶图

定义：给定平面图G=<V,E>，它有面F1,F2,…,Fn，若有图G*=<V*,E*>满足下述条件：

• 对于图G的任一个面Fi，内部有且仅有一个结点vi* ∈ \in ∈V*
• 对于图G的面Fi,Fj的公共边ek,存在且仅存在一条边ek* ∈ \in ∈E*,使ek*=(vi*,bj*),且ek*和ek相交。
• 当且仅当ek只是一个面Fi的边界时，vi*存在一个环ek*和ek相交，则图G*是图G的对偶图。

从这个定义看出，G*是G的对偶图，则G也是G*的对偶图。一个连通平面图的对偶图也必是平面图。

如果图G的对偶图G*同构于G，则称G是自对偶的。

定理：G为偶图的充要条件为所有回路长度均为偶数

着色

图G的正常着色（或简称为着色）是指对它的每一个结点指定一种颜色，使得没有两个相邻的结点有同一种颜色。如果图G在着色时有n种颜色，称G为n-色的。对于图G着色时，需最少的颜色数称为着色数，记为x(G).

韦尔奇鲍威尔法：

1. 将图G的结点按照度数的递减顺序进行排列。
2. 用第一种颜色对第一点进行着色，并且按排列次序，对于前面着色点不邻接的每一点着相同色
3. 用第二种颜色对尚未着色的点进行重复步骤2，用第三种颜色继续这种做法，直到所有的点全部上色

对于n个结点的完全图Kn,有x(Kn)=n

设G是至少有三个结点的连通平面图，则G中必有一个结点u，使得deg(u)<=5

任意平面图G至多是5-色的

树

无向树

设T是一个连通且无回路的无向图，则称T为无向树，简称树。树的度数为1的结点称为树叶，度数大于1的结点称为分枝点（内点）。

不含任何回路的简单无向图为森林

森林中的每一个连通的分支都是一棵树

性质

定理：设G=<V,E>是一个简单无向图，则以下关于树的定义都是等价的：

• G是连通的且不含回路的
• G中无回路，且m=n-1，其中，m是边数，n是结点数
• G是连通的，且m=n-1
• G无回路，但在G中的任何二结点之间增加一条新边，就得到唯一的一条回路
• G是连通的，但删除G中任意一条边后，就不连通
• G中每一对结点之间有唯一的一条路

任意非平凡的数T至少有两片树叶

特点

树是边数最多的无向图

树是边数最少的连通图

m<n-1，G不连通

m>n-1,必有回路

生成树

1. 定义：设G=<V,E>是一个连通的无向图，若G的某个生成子图是一棵树，则称该树为G的生成树，记为T G _{G} G​。生成树T G _{G} G​中的边称为树枝；在G中而不在 T G T_{G} TG​中的边称位弦， T G T_{G} TG​的所有弦的集合称为生成树的补
2. 定理：

• 任意一个连通图G至少存在一颗生成树。一个无向连通图G，如果G是一棵树则它的生成树是唯一的，即是G本身；如果不是，那么它的生成树就不是唯一的
• 一条回路和任意一棵生成树的补至少有一条公共边。
• 一个边割集和任何生成树至少有一条公共边

1. 求生成树的方法
   1. 破圈法：每次去掉回路中的一条边，其去掉的边的总数是m-(n-1)
   2. 避圈法：每次选取G中的一条边，该边不能与已经选取的边构成回路，此时选取的边的总数是n-1
2. 最小生成树：假设图G具有n个结点的连通图，对应于G的每一条边e，指定一个正数C(e)，把C(e)称作边e权，G的生成树也具有一个树权，它是T的所有边权的和。在带全的图G的所有生成树中，树权最小的那颗生成树称作最小生成树

3. 克鲁斯科尔算法：

   设图G有n个结点

   1. 选择权最小的边e1，置边数i=1
   2. i=n-1结束否则转3
   3. 设定已选定e1,…ei在G中选取不同于ei的边e i + 1 _{i+1} i+1​，使无回路且满足此条件的权最小的边
   4. i=i+1，转2

有向树

设G=<V,E>是一个简单有向图，若略去图G中所有边的方向后，得到的无向图是一棵树，则称这个有向图是一棵有向树

根树

1. 一棵非平凡的有向树，如果恰好有一个结点的入度为0，其余所有结点的入度均为1，则称此有向树为根树。入度为0的结点称为树根，出度为0的结点称为树叶，出度不为0的结点称为内点，又将内点同树根统称为分枝点
2. 根树包括一个或多个结点，这些节点的某一个称为根，其他所有结点被分成有限个子根树
3. 在根树T中，任意一个结点v及其所有后代导出的子图T1称为T的以v为树根的子树
4. 在根树中，任意一个结点v的层次即是从根到该结点的单向通路的长度，而同级的结点具有相同的通路长度
5. 在根树中，若vi到vj可达，则称vi是vj的祖先，vj是vi的后代。若<vi,vj>是根树的有向边，则称vi是vj的父亲，vj是vi的儿子；如果两个结点是同一结点的儿子结点，则称这两个结点是兄弟

k叉树

1. 若在根树T=<V,E>=(n,m)中，对任意结点vi ∈ \in ∈V,都满足
   • deg+(vi)<k，则称此根树是k叉树
   • deg+(vi)=k或deg+(vi)=0，则此根树为完全k叉树
   • 在完全k叉树中若所有树叶层次相同，称为正则k叉树
   • 在上述1,2,3中，当k=2时，此时分别称它们为二叉树，完全二叉树，正则二叉树
2. 在二叉树中，每个结点v至多有两个儿子，分别称为左儿子结点和右儿子结点，二叉树的每个结点v至多有两棵子树，分别称为v的左子树和右子树
3. 在完全k叉树中，若树叶数为t，分枝点数为j，则(k-1) j =t-1

4. 将k叉树转换为二叉树的步骤：

   从根节点逐级开始，按从左到右的顺序进行：

   • 除了最左边的分枝点外，删除所有从每一个结点长出的分支，在同一层级中，兄弟结点用从左到右的有向边连接
   • 若一个结点是某一节点的最左边的儿子结点，则在二叉树中作为某一个结点的左儿子。
   • 若一个结点与前一个结点是兄弟结点，则在二叉树中作为前一个结点的右儿子。

1. 森林转换成二叉树：
   • 先把森林中的每一个树转换成一棵二叉树
   • 除第一棵二叉树外，依次将剩下的每颗二叉树作为左边二叉树的根的右子树，直到所有的二叉树都练成一棵二叉树为止

最优树

1. 在根树中，一个结点的通路长度，就是从树根到此结点的通路的边数。分枝点的通路长度称作内部通路长度，树叶的通路长度称作外部通路长度
2. 给定一组权w1,w2,…,wt,不妨设w1<=w2<=…<=wt。设有一棵二叉树，共有t片树叶，分别带权w1,w2,…,wt，该二叉树称作带权二叉树
3. 在带权二叉树中，若带权为wi的树叶其通路长度为L(wi)，把 w ( T ) = ∑ i = 1 t w i L ( w i ) w(T)=\sum_{i=1}^{t}w_{i}L(w_{i}) w(T)=∑i=1t​wi​L(wi​)称为该带权二叉树的权，在所有带这些权的二叉树中，使w（T）最小的那棵树，称作最优二叉树
4. 设T为带权的最优二叉树，(w1<=w2<=…wt)
   • 带权为w1,w2的树叶是兄弟
   • 以树叶w1,w2为儿子的分枝点，其通路长度最长
5. 设T带权的最优树，若将带权w1,w2的树叶为儿子的分枝点改为带权w1+w2的树叶，得到一棵树T‘，则T’也是最优树(w1<=w2<=…<=wt)

前缀码

给定一个序列集合，若没有一个序列是另一个序列的前缀，该序列集合称位前缀码

定理：任何一棵二叉树的树叶可对应一个前缀码

任何一个前缀码都对应一棵二叉树

用二元树产生二元前缀码：

给一个二元树，t片叶，v是分枝点

若v有两个儿子，左0，右1.若只有一个，也可标0，也可标1

设w为T的一片叶，从根到w上各边标号组成的符号放在w处。