图的定义和基本术语

1.图的定义

图是由顶点和有穷非空集合和顶点边的集合吗，表示为G=(V,E)。
G表示一个图，V是图G的顶点（数据元素）的集合，E是图G中顶点之间边的集合。在图中，顶点个数不能为零，但可以没有边。

2.图的基本术语

结点：图中的顶点
结点间的关系：图中顶点之间的连线
无向图：顶点之间的连线没有方向，用（v,w）表示
有向图：顶点之间的连线有方向，用 <v,w> 表示。v称为弧尾，w称为弧头。
v的入度：有向图中，以顶点v为弧头弧的数目。
v的出度：有向图中，以顶点v为弧尾弧的数目。
v的度：无向图中有光联的边；有向图中，出度和入度之和。
路径：从一个顶点到另一个顶点之间的路径。
路径长度：无向图，路径上边的数目就是长度；有向图，路径上权重之和就是长度。
简单路径：路径中的结点不重复。
简单回路：简单路径中第一个结点和最后一个结点是相同的一个顶点。
子图：边和顶点都是子集。

3.图的分类

1.从图中的方向性以及边上是否有权划分
有向图：边有方向无权。有向网：边有方向、有权。
无向图：边没有方向无权。无向网：边没有方向，有权
2.从图中的边（弧）数e和顶点数n之间的关系划分
无向完全图：对于n个顶点，任意两个顶点之间都有边，e=n * （n-1）/2
有向完全图：对于n的结点，任意结点都能直接互相到达，e=n * （n-1）
稀疏图：e <= nlogn
稠密图：e >nlogn
3.从连通性上划分
（1）无向图
连通性：若从顶点vi到顶点vj有路径，则称vi和vj连通。
连通图：任意两个结点都是连通。
连通分量：极大连通子图，含有极大顶点数（如果多加1个顶点，子图就不连通了）和依附于这些顶点的所有边。
（2）有向图
强连通性：从顶点vi到顶点vj有路径，则vj到vi也有路径。
强连通图：任意两个顶点都是强连通的。
强连通分量：极大强连通子图
（3）生成树和生成森林
生成树：极小连通子图，包含图中的全部顶点和连接全部顶点的n-1条边。如果多出一条边就出现回路。少一条边就非连通。生成树不唯一
生成森林：非连通图中存在若干个连通分量，每一个连通分量对于一棵生成树，这些连通分量的生成树组成了一个非连通图的生成树。