1 图的基本概念
1、<V,E>是一个图
其中V代表顶点E表示边
2、零图：图的边集E为空集
3、平凡图：只有一个结点的零图
4、平行边：
1 在无向图中：有两条或两条以上的边与同一对结点相关联
2 在有向图中：一序偶对应两条以上的有向边(**边的方向也需要一致**)
5、多重图：有平行边的图
6、简单无向图：一个无向图(没有平行边)(没有自回路)
7、简单有向图：一个有向图(没有平行边)(没有自回路)
8、简单图：(没有平行边)(没有自回路)的图
9、子图：顶点和边的集合都是原来图<V,E>的子集
10、真子图：顶点的集合是原来图<V,E>的真子集并且边的集合是原来图<V,E>的子集
11、生成子图：**顶点的集合等于原来图<V,E>**并且边的集合是原来图<V,E>的子集
注意：生成子图中的顶点要和图的数目一样
12、完全图：是简单图并且顶点集合V中任意两个不同的结点之间都有边关联(有向图两点间有两条方向相反的有向边)
13、完全无向图：边数为 n*(n-1)/2
14、完全有向图：边数为 n*(n-1)
15、结点的度：
1 无向图：边的数目
2 有向图：出度加入度
16、度为1的结点是悬挂点,与之关联的边为悬挂边
17、度为奇数的结点为奇结点
18、度为偶数的结点为偶结点
注意：对于一个自回路来说是一个出度加一个入度
19、假设图的结点数目为n,边的数目为m：
1 无向图：度数和 = 边数m*2
2 有向图：总出度 = 总入度 = 边数m
20、假设图中有n个结点:n1个奇结点(那么n1一定是偶数)
解释：2*边数 = 度数和 = 奇结点度数和+偶结点度数和
左边是偶数 = 偶数+ 奇结点度数和
**奇结点度数和为偶数**
偶数个奇数相加才是偶数
2 路和连通图
2.1路与回路
1、路就是顶点和边的交替
2、回路：第一个顶点和最后一个顶点相等的时候(v0=vn)
3、路长：一条路经过的边数
4、简单路：一条从v0到vn的路不经过重复边
5、简单回路：v0 = vn的简单路
6、初级路：一条路中除了：v0=vn这一种情况以外,所有经过的结点都不相同
7、初级回路：v0 = vn的初级路
注意：
初级路：没有重复点
简单路：没有重复边
**不经过重复点,那么一定不经过重复边**
**反之不然**
也就是说：一条路是初级路,就一定是简单路
是简单路不一定是初级路(不经过重复边,不一定不经过重复点)
该图表明：
是简单路(没有经过重复边)但是不是初级路(没有经过重复点)
**b点走了两次,边没有重复走**
2.2 可达性与连通图
8、存在结点u到v的路,那么称u到v是可达的
9、连通图：在无向图中,任意两个结点u到v是可达的
10、割点：某一个结点构成一个点割集,该结点就是割点
11、点割集：删去了该集合中的全部结点之后,就会得到非连通图,而删除该集合中的部分结点之后,得到的还是连通图
同理可得：边割集(删除边)
12、割边：某一个边构成一个边割集,该边就是割边
13、边割集：删去了该集合中的全部边之后,就会得到非连通图,而删除该集合中的部分边之后,得到的还是连通图
14、点连通度k(G)：
对于整个无向图而言,点割集中元素最少的个数
也就是说：为了产生一个不连通图需要删去的点的**最少数目**
注意：
非连通图的点连通度为0
完全图的点连通度为n-1
存在割点的连通图的点连通度为1
15、边连通度λ(G)：
对于整个无向图而言,边割集中元素最少的个数
也就是说：为了产生一个不连通图需要删去的边的**最少数目**
注意：
非连通图的边连通度为0
完全图的边连通度为n-1
存在割边的连通图的边连通度为1
16、点连通度 小于等于 边连通度 小于等于 图的最小度
17、在有向图中,任意一对结点之间至少有一个结点到另一个结点是可达的那么称图G是单向连通的
18、若对于图中任意两结点是相互可达的,那么称图G是强连通的
19、省略去边的方向,将有向图G看做无向图后,图是连通的
(该图为弱连通的)
注意：
1 强连通一定是单侧连通
2 单侧连通一定是弱连通
若图G是强连通的：那么一定在G中存在一条回路,它至少包含每个结点一次
3 图的矩阵表示及其连通性的判断
3.1 邻接矩阵(n阶方阵) A
简单有向图G,由0或1来表示
注意：
1 行看出度
2 列看入度
邻接矩阵A的乘幂A2的含义：
A2中元素aij(2)表示vi到达vj的长度为2的路的数目
3.2 可达矩阵(有没有路可以走) B
简单有向图G,由0或1来表示
并不是说有没有直达可以走
矩阵A表示直达的路
矩阵A2表示长度为2的路
…………
矩阵An表示长度为n的路
B = A+A2+A3+……+An
将B = A+A2+A3+……+An结果中凡是不等于0的元素都改为1(可达矩阵)
矩阵的乘法实际上是与的运算
矩阵的加法实际上是或的运算
3.3 关联矩阵(点和边的关系)
在矩阵中：
行是点 列是边
3.4 图的连通性判断
关于有向图的连通性的判断方法：
1、G是强连通的 的充要条件是 R是全1的矩阵
2、G是单向连通的 的充要条件是 R或RT除主对角线外都是1
3、G是弱连通的 的充要条件是 由邻接矩阵A可以确定的A或AT的可达矩阵是全1矩阵
4、G中有回路 的充要条件是 R的主对角线上最少有一个rii = 1
4 赋权图与最短路
赋权图：是简单图并且每一条边对应一个正数
Dijkstra算法(求最短路)
5 欧拉图与汉密尔顿图
5.1 欧拉图(边遍历)
1、欧拉路：对于连通图G,存在一条路,经过图中每边一次且仅一次
2、欧拉回路：是欧拉路并且是回路
3、欧拉图：具有欧拉回路的图
无向图G具有一条欧拉路：
图G是连通的并且具有两个或零个奇结点
图G是欧拉图的充分必要条件是G是连通的并且没有奇结点
4、单向欧拉路：有向图G,通过图G中每边一次并且仅一次的单向路
有向图G具有单向欧拉路的充要条件是：
1 或者每个结点的出度等于入度
2 或者有两个结点例外：而这两个结点中一个的出度比入度大1,另一个的入度比出度大1
5.2 汉密尔顿图(点遍历)
1、汉密尔顿路：对于无向简单图G,存在一条路,经过图中的每个结点恰好一次
2、汉密尔顿回路：存在一条回路,经过每个结点恰好一次
3、具有汉密尔顿回路的图为汉密尔顿图
4、充分条件：
1 假设G是具有n个结点的无向简单图,如果G中每一对结点度数之和大于等于n-1,那么G中存在一条汉密尔顿路
2 假设G是具有n个结点的无向简单图,如果G中每一对结点度数之和大于等于n,那么G中存在一条汉密尔顿回路
5、当且仅当一个无向简单图的闭包是汉密尔顿图时,这个图是汉密尔顿图文章来源：https://www.toymoban.com/news/detail-478149.html
6 二分图与平面图
6.1 二分图
6.2 平面图
无向图G中存在：任意两条边不相交文章来源地址https://www.toymoban.com/news/detail-478149.html
7 树及其应用
到了这里，关于离散数学 图论的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[离散数学]图论](https://imgs.yssmx.com/Uploads/2024/02/450727-1.png)
