定义

图是一种多对多的逻辑结构，图不能为空，且每个边端点都必须有顶点。（线性表和树都可以为空）
图G由顶点集V和边集E组成，记为G=（V,E)

分类

无向图

边没有方向

有向图

边有方向

简单图

1，无重复边
2.不存在结点到自身的边

重复图

1，存在重复边
2.存在结点到自身的边

完全图

无向完全图

任意两个顶点都存在边
n个顶点有 $\ \frac{n(n-1))}{2}$ 2n(n−1))​ 条边（每个顶点可连接（n-1）条边，重复了两次）

有向完全图

任意两个顶点都存在方向相反的弧

一些概念

子图

设有两个图G=(V,E),G=(V’,E’),若V’时V的子集，E’是E的子集，则G;是G的子图。
且V(G)=V(G’），则G’是G的生成子图。

连通

连通是相对于无向图来说的
如图：
若从e到f有路径存在，则称e和f是连通

强连通

强连通是相对于有向图来说的
如图
若从e到f和f到e均有路径存在，则称e和f是强连通

连通图

任意两个结点都是连通的
n个顶点的连通图最少多少边呢？

n-1个

连通分量（极大连通子图）

连通分量即是极大连通子图
定义：

即连通子图要极可能包含最多的边和端点
如：

红线框内的连通子图即为最左边图的极大连通子图

强连通图

任意两个结点都是强连通的
n个顶点的强连通图最少多少边呢？

n个

极大强连通子图

和极大连通子图差不多，不过是定义在有向图中
如：

红线框内即为最右边图的极大强连通子图

极大（强）连通子图规律

由以上可以看出，当原图是（强）连通图时，（强）连通分量（最大（强）连通子图）就是原图。

极小连通子图

满足条件连通子图且包含的边最小如：

右边为左边当端点为4时的极小连通子图。同理还有顶点为1，2，3，5时的极小连通子图

生成树

连通图包含全部顶点的一个极小连通子图，在上图中就是顶点为5的极小连通子图。注意生成树只能从连通图中生成。

生成森林

非连通图所有连通分量的的生成树组成森林。即从非连通图中只能生成生成森林。

顶点的度

以该顶点为一个端点的边的数目。
注意在有向图中度又分为出度和入度，即出去的箭头和指向其自身的箭头。

网

将图的每个边加入权重。

有向树

一个顶点入度为0，其余顶点入度均为1的有向图
**
**

路径

一个顶点到另一个顶点的顶点序列。序列中顶点不重复的路径成为简单路径。

路径长度

路径上边的数目，若该路径最短则称其为距离。

回路

第一个顶点和最后一个顶点相同的路径