图论复习总结（有问题可以反映在评论区，有更好的思路也可以写在评论区，大家一起学习）

首先来一波图论相关的所有定义和定理：

---

---

8.1 图的基本概念：

        定义：8-1:图G是一个有序二元组（V , E）其中V是点集，E是边集。

---

        定义：8-2:在图G中，任意两个不同节点都是邻接的，则称G为完全图。

                  （邻接的要求是两个点直接相连）

                  （完全图的每个节点的度都是n-1）

                  （邻接矩阵除了对角线的所有元素均为1）

---

        定义：8-3:图G的补图是由G的所有节点和为了使G成为完全图所需要补充的那些边所构成的图

                   （补图和原图之间：节点一定是相同的，边一定是不同的）

                   （补图的邻接矩阵加上（布尔加）原图的邻接矩阵结果是一个完全图的邻接矩阵）

---

        补充定义（通俗）：

                1.伪图：两个点之间有多条边相连，或者一个点存在与自身相连的环

                2.多重图：两个点之间有多条边相连，但不能有点存在与自身相连的环

                3.边的重数：连接同一对节点的边的数目

                                    （对于上图{V2,V3}的重数为2）

                4.简单图：没有重数大于1的边，且没有自环的图

                                     （我们平时见到的正常的图都是简单图）

---

        定义：8-4:若图G的所有节点的度都是d，则称图G为d次正则图

                        （完全图是n-1次正则图）

                        （正则图的邻接矩阵每一行或每一列的和相等）

---

        定理：8-1（握手定理）:如果图G有m条边，那么图G所有节点的度之和为2m

                      （所有节点的度之和必为偶数）

                      （图的所有节点的度之和就是邻接矩阵中所有1的个数，邻接矩阵一定是对称矩阵）

                      （由此可以推出：一个图中度数是奇数的节点一定有偶数个）

---

        定义：8-6:设G和G′是分别具有结点集V和V′的两个图。若存在一 个双射h:V→V′，使得当且仅当{vi，vj}是G的边时，{h(vi)， h(vj)}是G′的边，则称图G与G′同构

          （这个定义确实无法简化了，但是我提出一种同构图的判断方法，没有科学依据，慎用！（所有标红内容都是我自己瞎编的名词））

          （以教案的图为例）

1.（判断同构图，只有当这个图高度对称的时候才会有迷惑性，所以我们将图中的节点进行分类）

2.（对G4图而言，在同类型点中任意选取一个点（u1）为基准点，其他点被分为两种，一种是和他邻接（u4，u5，u6），另一种是不和他邻接（u2，u3）） 

*对于同类型的解释：G4上面三个点是同类型的 下面三个点是同类型的

*对于同类型的解释：G3里面三个点是同类型的 外面三个点是同类型的

*对于同类型的解释：同类型与否是通过对称性确定的，两个图的类型数要相同

3.（我们暂且将这种对点的划分方法称为图的点的性质划分）

4.（对应到G3中，选取一个点对图进行相同的图的点的性质划分）

5.（（取v1）得到划分出的结果 邻接：（v2，v3，v4） 不邻接：（v5，v6））

6（我们发现，在G4中同类型点是一定不邻接的，而在G3中出现了同类型点邻接的情况，说明两个图一定不同构）

---

        定义：8-7:子图，真子图，生成子图

---

        定义：8-9:开路，回路，真路，环

---

        定义：8-10:图G的分图是图G的所有最大的连通子图

                        （连通图的分图就是自身）

                        （非连通图的分图就是改图中的每一个连通图）

---

        定义：8-11:连接节点V1和V2的最短的路称为短程，节点间短程长度称为节点间的距离，用d（V1，V2）表示

                        （短程是一条路，距离是一个值）

---

        定理：8-2:图G中任意两个节点的短程小于n，且是一条真路

（连通图的情况下条件暗含了任意两个节点都有真路） 

（由此可知，图中任何一个环的长度都不会大于n） 

---

         定义：8-12:

                   割点：删去该点（以及它关联的边）后该图的分图数增加。

                   割边：删去该边后该图的分图数增加。

            （任意两个点之间的路必须经过一个点或一个边，那么这个点或这个边就是割点和割边，反之也成立）

            （割边不会在任何环路中出现）

---

        定理：8-3:在连通图G中边{Vi,Vj}为割边的充要条件是该边不在G的任何环上出现

                （用反证法证明）

---

8.2 图的矩阵表示：       

        定义：8-13:图的邻接矩阵

（只有两个节点{Vi,Vj}直接有边相连时，aij才为1）

---

        定义：8-14:图的连接矩阵

 （只要两个节点{Vi,Vj}是连通的，cij就为1）

---

        补充定义：用邻接矩阵求连接矩阵

---

8.3 欧拉图和哈密尔顿图：          

        定义：8-15:通过图G每条边一次且仅一次的回路称为欧拉回路，存在欧拉回路的图称为欧拉图

        定义：8-16:通过图G每条边一次且仅一次的开路称为欧拉路

（欧拉回路不一定是环路，因为欧拉回路允许经过一个节点多次，不是一条真路）

---

        定理：8-5:一个连通图G为欧拉图的充要条件是G的每一个节点的度都是偶数。

        定理：8-6:一个连通图G有Vi到Vj的欧拉路的充要条件是Vi和Vj是G中仅有的具有奇数度的节点。

（有欧拉路的图有且仅有两个奇数度的节点，且欧拉路的起点和终点一定是这两个节点）

---

        定义：8-17:通过图G的每一个节点一次且仅一次的环称为哈密尔顿环。具有哈密尔顿环的图称为哈密尔顿图。通过图G的每一个节点一次且仅一次的开路称为哈密尔顿路

（哈密尔顿环不一定要经过所有边，有些边可以不用，但一定要经过有所的节点）

---

        定理：8-7:若图G=(V，E)是哈密尔顿图，则对于V的任意一个非空子集S，有W(G–S)≤#S

（这里W(G–S)表示从G中删除S(删除S中的各结点及相关联 的边)后所剩图的分图数。#S表示S中的结点数。）

（总结一下：有割点的图一定不是哈密尔顿图，哈密尔顿图的任何一个节点都不是割点）

（如果一个图存在删去的节点数小于产生的分图数的情况，那么这个图一定不是哈密尔顿图）

---

        定理：8-8:设G是具有n个(n≥3)个结点的图，若有结点u和v不相邻接，且deg(u)+deg(v) ≥n，则当且仅当G +{u,v}是哈密顿图时，图G是哈密顿图。

---

        定义：8-18:设G是具有n个结点的图，若对deg(u)+deg(v) ≥n的每 一对结点u和v，均有u与v相邻接，则称图G是闭图。

---

        定义：8-19:设G1=(V，E1)和G2=(V，E2)是两个具有相同结 点集V的图，则称H1=(V，E1∪E2)和H2=(V，E1∩E2)分别 为G1和G2的并和交，并分别记做G1∪G2和G1∩G2。

（把点和边都看作集合来理解）

---

        定理：8-9:如果G1和G2是具有相同节点集V的两个闭图，则G=G1∩G2也是闭图

（∪不成立）

---

        定义8-20:图G的闭包是一个与G有相同的结点集的闭集，记做Gc 使G ⊆ Gc,且异于Gc的任何图H，若G ⊆ H ⊆ Gc，则H不是闭图。

        定理8-10:图G的闭包是唯一的。

（闭包的定理类似于关系中的闭包，Gc是包含G的最小的闭图）

---

        补充定义：闭包算法

（循环操作，直到所有deg(u)+deg(v) ≥n 的n和v都被连接起来为止） 

---

哈密尔顿图的判定方法：

定理：8-11:当且仅当图G的闭包是哈密尔顿图时，图G时哈密尔顿图

推论1：若图G的闭包是n个节点的完全图，且n>=3，则G是哈密尔顿图

推论2：若图G是有n个节点的图，且n>=3，且任何一个节点的度都>=n/2，则图G是哈密尔顿图

推论3：设图G=(V，E)，#V≥3，若V中任意两个不相邻的结点u和v，均有deg(u)+deg(v)≥n，则G是哈密尔顿图。

---

8.4 树：

        定义：8-21:不包含环的连通图称为树，不包含环的图（可以是非连通图）称为森林，树中度为1的节点称为树叶，度大于1的节点称为分支节点。

---

        定理8-11:设T是一棵树，当且仅当T中任意两个不同的结点Vi，Vj 间有唯一的一条真路。若vi和vj不相邻接，那么当给T添加一条边{ vI，vj }后形成的图恰有一个环。

（树加任何一条边就成环，树是一个连通图没有环且边最多的情况）

---

        定理8-12:若T是一棵树（n个节点，m条边），则m=n-1

（树的任何一条边都是割边，任何一个非叶子节点都是割点）

（对于一个k棵树的森林，m=n-k）

（G无环路，且m=n-1，则G一定是一棵树）

（G无环路，且m=n-k，则G一定是k棵树的森林）

---

        定理8-13:具有两个或更多节点的树至少有两片树叶

（具有足够数量节点的K棵树所构成的森林，至少有2K片树叶）

---

小总结：判断一个图是树的方法：

        1.每个节点间由唯一的真路连接的图是树（每条边都是割边的图）

        2.符合边数是节点数-1的连通图是树

                （如果去掉连通图这个条件：不是树）

        3.符合边数是节点数-1且无环的图是树

                （m=n-1、连通图、无环这三个条件知二得三）

---

        定义：8-22:若图G的生成子图T是一棵树，则称T为G的生成树。G中属于T的边称为T的枝，G中属于E，不属于T（被砍掉的边）的边称为T的弦，或G的环秩

（一个图的生成树不一定唯一）（只有当原图是一个大环的时候唯一）

---

构造生成树的方法：

1.破环法：

2.避环法

---

        定义：8-23:图G所有生成树中权最小的生成树称为G的最小生成树

---

最小生成树的构造方法：

1.破环法：类似生成树，挑一些比较大的边破。 根据实际情况动态规划

2.避环法：挑一些较小的边加。 根据实际情况动态规划

---

8.5 二部图：

        定义（通俗化）：8-24:若一个图的节点可以划分为两组，每一组节点内部没有边相连，只有两组节点之间有边相连，那么这样的图就可以称为二部图。若一组节点（V1）中的任何一个节点都与另一组节点（V2）中的每一个节点有边相连，则称这样的二部图为完全二部图

---

         定理：8-14:图G为二部图的充要条件是G的所有回路均为偶数长

（存在奇数长度回路的图一定不是二部图，所以完全图一定不是二部图）

---

         定义（通俗）：8-25:V1到V2的匹配是指在V2中找出#V1个节点，与V1中的每一个节点一一连接

（要注意是V1到V2的匹配还是V2到V1的匹配）

---

        定理：8-15:对于一个二部图G，至少存在一个V1到V2的匹配的充要条件是，V1中的每K（K=1，2，3，……，#V1）个节点，都至少与V2中K个节点相连

        定理：8-16:对于一个二部图G，至少存在一个V1到V2的匹配的充分条件是，V2中的节点所拥有的最大的度，小于等于V1中的节点所拥有的最小的度

（要分清楚充分条件和充要条件）

（这个图虽然不满足定理8-16，但是它依然存在V1到V2的匹配）

---

 8.6:平面图：

        定义：8-26:一个图G能画在平面上，它的边除在端点处外互不交叉，则称G为平面图。画出的没有交叉的图解称为G的一个平面嵌入。

---

        定义：8-27:设G是一个连通平面图，G的边将G所在的平面划分成若干个区域，每一个区域称为G的一个面。其中面积无限的区域称为无限面。面积有限的区域称为有限面。包围每个面的所有边构成的回路称为面的边界

---

         定理：8-17（欧拉公式）:设G是一个连通平面图，有n个节点，m条边，k个面，则满足n-m+k=2

（可以推出：m<=3n-6）

（对于每个面至少由四条边围成时：m<=2n-4）

---

        定义：8-28:如果两个图G1和G2是同构的，或者通过反复插入或 删除度为2的结点，它们能变成同构的图，则称G1和G2在度为2的结点内同构

---

        定理：8-18(库拉托斯基定理):一个图是平面图的充要条件是它不包含在度为2的结点内与K5同构的子图，也不包含在度为2的结点内与K3,3同构的子图。

---

8.7:有向图：

        定义：8-29:有向图G是一个有序二元组(V，E)，其中结点集V是一有限非空集合，边集E是V中不同元素的有序对偶的集合

（有向图的边用一个箭头表示）

（有向图的邻接矩阵非对称，且所有非0元素的个数之和为边的条数）

---

        说明：在有向图中，路、开路、回路、真路、环的定义与无向图类似，只是需要考虑边的方向。 

---

        定义：8-30:在有向图G中存在一条从V1到V2的有向路，则称V1到V2是可达的，d（V1,V2）表示V1到V2有向路的条数。

---

        定理：8-19:有向图所有节点入度之和等于所有节点的出度之和

（入度：指向该节点的边，deg-（Vi））

（出度：由该节点发出的边，deg+（Vi））

（deg（Vi）= deg-（Vi）+ deg+（Vi）一个节点的度等于入度加出度）

---

        连通性：

（n个节点的强连通图至少要有n条边：每个节点的入度与出度都是1时最小） 

---

        定理：8-20:一个连通(弱连通)有向图具有欧拉回路的充要条件是G的每一个结点的入度和出度相等。具有欧拉路的充要条件是除两个结点外，每个结点的入度等于出度。对于这两个结点，一个结点的出度比入度多1，另一个结点的出度比入度少1

---

8.8：有向树：

        定义：8-31：一个不包含环的有向图G，若它只有一个结点V0的 入度为0，而其它所有结点的入度都等于1，则称G是有向树， V0称为树的根

---

        常见名词：

---

        定义：8-32:m元树，满m元树，完全m元树

（这是百度百科对满二元树的定义，与教材不同，应当以教材为准，具体可以问问老师 ）

---

周游二元树：

二叉树的三种遍历_猫萌萌的博客-CSDN博客_二叉树的三种遍历

这个文章讲述的三种周游方法：

        前序遍历：先根周游

        中序遍历：中根周游

        后序遍历：后根周游 

---

        定理：8-21:若T是一棵完全m元树，树叶节点数为n0，分支节点数为t，则有：(m-1)t=n0-1

---

        定理：8-22:若T是一棵二元树，树叶节点数为n0，出度为2的节点数为n2，则n0=n2+1

---

        定理：8-23:若T是一棵完全m元树，则T有奇数个节点

---