图的一些基本概念

图的概念比较杂乱，国内各种书籍对一些概念也是各执己见，比如圈和环.......这里旨在按照一个规则了解一些概念，对于与其他书籍材料的不同，还要看情况再定

我们讨论的图大多为简单图->没有环和重边

环：一个顶点到他自身的边

圈：v1=vn的一条路径。对于有向图，路径长度为1的即为一个环（非简单图）。对于无向图，路径长度为1的还是环，不是圈。且对于没有重边的无向图，u，v，u不算做圈，因为

（u，v），（v，u）是同一条边，这样的圈讨论是无意义的，所以无向图的圈，长度至少为3。

DAG：有向无圈图

连通图：在无向图中，每一个顶点到其他每个顶点均存在路径

强连通图：在有向图中，每一个顶点到其他每个顶点均存在路径

弱连通图：有向图不是强连通图，但去掉方向后，对于这个无向图，是连通的

连通分量：无向图的极大连通子图，应满足：子图，连通，极大边数，极大顶点数。因此对于无向图，连通图只有一个连通分量，即他本身，非连通图存在大于一个的连通分量

强连通分量：有向图的极大强连通子图，满足：子图，强连通，极大边数，极大顶点数。强连通图也只有一个强连通分量，即他本身，非强连通图存在大于一个的强连通分量

生成树：

对于无向图，要是连通的，生成树为包含全部顶点的一个极小连通子图

对于有向图，生成树为一棵有向树，有一个顶点的入度为0，其他为1