图的基本概念

图的定义

对于图（Graph）这类数据结构，用两个集合V和E来表示其组成，其形式上可记为
G=（V，E）
其中：


V是顶点（Vertex）的非空有限集合（一组顶点）
E是边（Edge）的有限集合（一组边）
用于表示任意两个顶点之间的关系集合

无向图

在一个图中，如果任意两个顶点构成的无序偶对

是无序的，即顶点之间的连线是无方向的，则称该图为无向图

在无向图中，若任意两个顶点之间都存在一条直线连接，则称该图为完全无向图
n个顶点的完全无向图有条边**

有向图

在一个图中，如果任意两个顶点构成的偶对是有序的，即顶点之间的连线是有方向的，则称该图为有向图

在有向图中，若任意两个顶点之间都存在方向互为相反的两条直线连接，则称该图为完全有向图**
n个顶点的完全有向图有条边

完全有向图/无向图的共同点，任意两个点都有一条边相连

综上：
无向图**：每条边都是无方向的
有向图**：每条边都是有方向的**

顶点，边和弧

无序对
表示在无向图的顶点Vi和顶点Vj之间有一条直线或者弧线连接，
称这条连线为边（或弧）
有序对
表示在有向图的顶点Vi和顶点Vj之间有一条直线或者弧线连接，
称这条连线为有向边（或弧）
顶点vi称为弧的起点，vj称为弧的终点

邻接点

在无向图中，若存在边，即无向图，若
则称顶点vi和 vj互为邻接点 ,即相互邻接
称边 依附于顶点vi和顶点 vj或称边 与顶点vi和顶点vj相关联
在有向图中 ，若存在边，即有向图，如果弧
则称顶点vi邻接到vj，或者vj邻接自vi
称弧依附于顶点vi和顶点 vj
或称弧与顶点vi和顶点 vj相关联

顶点的度，出度和入度

在无向图中 ，顶点v的度表示和v相关连的边的数目 ，记为
在有向图中 ，以顶点v为弧尾（终点）的弧的数目称为该顶点的入度，记为
以顶点v为弧头（起点）的弧的数目称为该顶点的出度，记为
有向图的度为
对于具有n个顶点，e条边的图（无论是有向图还是无向图），每个顶点Vi的度与顶点个数n以及边的数目e满足如下关系：

问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？
答：是树！而且是一棵有向树

边的权和网

有时图的边或者弧往往与一定意义的数值有关，即与边或者弧相关的数，称为权
将带权的图称为网

路径和路径长度

路径**：接续的边构成的顶点序列，路径是有方向的
路径长度**：路径上边或弧的数目/权值之和。

简单路径，回路和简单回路

回路**(环)**：第一个顶点和最后一个顶点相同的路径。
简单路径**：除路径起点和终点可以相同外，其余顶点均不相同的路径。
简单回路(简单环)：除路径起点和终点相同外，其余顶点均不相同的路径。
**

子图

设有两个图，，若，，则称 G1是G的子图。
例:(b)、(c) 是 (a) 的子图

连通，连通图和连通分量

连通图：在无向图中，若对任何两个顶点v、u 都存在从v 到 u 的路径，则称G是连通图。

连通分量：无向图中的极大连通子图称为该无向图的连通分量
连通分量包含下列意义：
子图：连通分量应该是原图的子图
连通：连通分量本身是连通的
极大顶点数：连通子图含有极大顶点数，再加入其它顶点会导致子图不连通
极大边数：具有极大顶点数的连通子图包含依附于这些顶点的所有的边
连通的无向图只有一个连通分量，这个连通分量就是无向图本身
不连通的无向图有多于一个的连通分量
极大连通子图意思是：该子图是G连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通。

强连通图：在有向图，中，若对任何两个顶点v、u 都存在从v 到 u 的路径，则称G是强连通图。

强连通分量：有向图中的极大强连通子图
不是强连通的有向图有多于一个的强连通分量
极大强连通子图**：该子图是G的强连通子图，将G的任何不在该子图中的顶点加入，子图不再是强连通的。

极小连通子图**：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。

稀疏图和稠密图

稀疏图：有很少边或弧的图。
稠密图：有较多边或弧的图。
设图，如果边的数量为,顶点数量为,图的稠密度定义为平均顶点度
完全图平均顶点度

生成树

包含无向图G所有顶点的极小连通子图。
即G的包含**全部n个顶点**的一个极小连通子图
必定包含且仅包含G的n-1条边
生成树有可能不唯一,有n-1条边并不一定是生成树
如果一个图有n个顶点和小于n-1条边，则是非连通图
如果多于n-1条边，则必定构成一个环

生成森林

对非连通图，由各个连通分量的生成树的集合。