一、图论
图论是数学的一个分支，它以图为研究对象。图论中的图是若干给定的点（顶点）以及连接两点的线（边）构成的图像，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
图几乎可以用来表现所有类型的结构或系统，从交通网络到通信网络，从下棋游戏到最优流程，从任务分配到人际交互网络，图都有广阔的用武之地。
表示出最基础的图：（这些与点的大小，边的粗细都无关，只表示点与点之间通过边的关系）
二、图的基础
1.顶点（vertex）
在图的应用中，每个顶点代表的含义均不相同，而是相互通过边相联系，因此将图中的每个顶点进行标号进行区分。
①.度数（degree）
与该顶点相关联的总变数，一个图G的总度数 d(V) 等于总边数的两倍，当图的边有方向时（有向图），一个顶点的度可分为出度（out-degree）和入度（in-degree）,出度是以该顶点为起点的边数，入度则是以该顶点为终点的边数。
②阶数（order）
图中含有顶点的个数，即含有 n 个顶点，为 n 阶图
2. 边（edge）
顶点与顶点之间通过边联系，构成一个完整的图。
①权重（weight）
边的权重（权值），即每条边都有与之对应的值。
例如将两个顶点看成两个地点，边看成两个地点之间的距离。
三、图的分类
综合以上，图可以分为以下几种
1.有向图/无向图
最基本的图通常被定义为“无向图”，与之对应的则被称为“有向图”。两者唯一的区别在于，有向图中的边是有方向性的。
无向边：无固定方向的边，既可 x 到 y，又可以 y 到 x
有向边：固定方向的边，即只能 x 到 y ，不能 y 到 x
2.有权图/无权图
有权图： 权值就是一条边的长度或代价。
无权图： 不是边的权值为0，而是全都为1。
3.特殊的图——环
在图论中，环是一条只有第一个和最后一个顶点重复的非空路径。一个没有环的图被称作无环图，一个没有有向环的有向图被称做有向无环图。一个无环的连通图被称作树。
4.连通图/连通分量
在图G中，任意两个顶点之间都存在路径，则称G为连通图
上图虽然不是一个连通图（例 点8 与 点4 不连通），但它有两个连通子图，1234，56789，
把一个图的最大连通子图称为它的连通分量。5,6,7,8,9顶点构成的子图就是该图的最大连通子图，也就是连通分量。
连通分量特点：①子图
②子图是连通的
③子图含有最大的顶点数
对于连通图而言，最大连通分量就是其本身
版权声明：本文为博主作者：一只蒟蒻ovo原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/Zhang_Qin123/article/details/136319824
