图的基本概念

一个图 G 它可以由顶点集（图 G 中顶点的有限非空集） V 和边集（图 G 中顶点之间的关系集合） E 所组成。图中顶点个数也可以称为图的阶；任何一条边的两头必须连接某一个顶点。图不可以是空，即顶点集 V 一定是非空集，但边集 E 可以是空集。

简单图：在这个图里不存在重复的边，并且也不存在顶点到自身的边。

多重图

一个图里存在重复的两条边或者自身连向自身的边。

顶点的度

在无向图中，指依附于这个顶点的边到底有多少条，记为 TD(V)，V指的是某一特定的点。

在有向图中，入度是以顶点为终点的有向边的数目，记为 ID(V)；出度是以顶点为起点的有向边的数目，记为 OD(V)；顶点 v 的度等于入度和出度之和 TD(V) = ID(V) + OD(V).

路径-----顶点 vp 到顶点 vq 之间的一条路径是指顶点序列

回路-----第一个顶点和最后一个顶点相同的路径称为回路或环

简单路径-----在路径序列中，顶点不重复出现的路径称为简单路径

简单回路-----除了第一个顶点和最后一个顶点之外，其余的顶点都不重复出现的回路

路径长度-----两个顶点之间的路径，这个路径上总共有多少条边

点到点的距离-----两个顶点之间最短路径的长度作为顶点到顶点之间的距离;如果两个顶点之间根本就不存在路径的话，那么我们需要把它们之间的距离记为∞(无穷)。

无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的;有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的.

注意:

1. 对于 n 个顶点的无向图 G, 若 G 是连通图,则最少有 n -1 条边; 若 G 是非连通图,则最少有条边.

2. 对于 n 个顶点的有向图 G, 若 G 是强连通图,则最少有 n 条边（形成回路）

子图与生成子图

子图：一个图里边有一些顶点集和边集，取出几个顶点，然后再取出整个边集当中的某一个子集，用这样的方式构建的这个图就是原图的一个子图。注意并不是从原图当中任意选择几个顶点，任意选择几条边都能构成子图的，因为子图首先它必须是一个图。

生成子图：子图里边包含了原图当中的所有顶点，那么这个子图就可以称为原图的一个生成子图。

对于有向图的子图和生成图的概念一样。

连通分量（无向图）与强连通分量（有向图）

连通分量：无向图中的极大连通子图（子图必须连通，且包含尽可能多的顶点和边）

强连通分量：

如图在图 G 中A,B,E,C,D是强连通的，将这个部分择出来就是一个极大的强连通分量。而顶点 F 和 A,B,C,D,E不是强连通的(从其他顶点到 F 的路径存在，而 F 到其他顶点的路径不存在)，所以 F 和 A,B,C,D,E是不强连通的。

生成树和生成森林

生成树：对于一个连通的无向图，它的生成树指的是这个图里边的全部顶点的一个极小的连通的子图。也就是说这个子图它要包含原图里边的全部顶点，要包含全部顶点，同时要保证这个子图连通，而且要极小(指在这个子图里边的边要尽可能的少,但要保持连通)。若图中顶点数为 n ，则他生成树含有 n-1 条边。若砍去一条边，则会变成非连通图；若加上一条边则会形成一个回路。

生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林。

边的权，带权图/网，带权路径长度

边的权------为图中的每条边标上具有特殊含义的数值，这个数值则为边的权。

带权图/网------边上带有权值的图称为带权图（或网）

带权路径长度------指这条路径上所有的边的权值之和称为带权路径长度

特殊形态的图

无向完全图------其中的任何两个顶点之间都存在边

有向完全图------其中的任意两个顶点之间都存在着方向相反的两条弧
稀疏图------边很少的图

稠密图------边很多的图

树------图里边不存在回路，并且这个图中各个节点是相互连通的，它是一个连通图。那么这种形状的图其实就是一个树

对于 n 个顶点的数一定有 n 减一条边，如果说 n 个顶点的图它的边大于 n-1 条，那么这个图一定是有回路的

对于无向图来说，森林里边各个子图是极小的，同时各个子图又是连通的。

有向树：只有一个顶点的入度是0，然后其他所有顶点的入度都是1

注意：树是一个连通图，各个顶点之间是连通的，但是有向树，它并不是一个强连通图。