图

无向图

1. 回路或环：第一个顶点和最后一个顶点相同的路径。
2. 简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路
3. 连通：顶点v至v’ 之间有路径存在
4. 连通图：无向图图 G 的任意两点之间都是连通的，则称G是连通图。
5. 连通分量：极大连通子图，子图中包含的顶点个数极大
6. 所有顶点度的和必须为偶数

有向图：

1. 回路或环：第一个顶点和最后一个顶点相同的路径。
2. 简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。
3. 连通：顶点v至v’之间有路径存在
4. 强连通图：有向图G的任意两点之间都是连通的，则称G是强连通图。各个顶点间均可达。
5. 强连通分量：极大连通子图
6. 有向图顶点的度是顶点的入度与出度之和。邻接矩阵中第V行中的1的个数是V的出度
7. 生成树：极小连通子图。包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环。
8. 完全图：有 n(n-1)/2 条边的无向图。其中n是结点个数。必定是连通图。
9. 有向完全图：有n(n-1)条边的有向图。其中n是结点个数。每两个顶点之间都有两条方向相反的边连接的图。
10. 一个无向图 G=(V,E) 是连通的，那么边的数目大于等于顶点的数目减一：|E|>=|V|-1，而反之不成立。如果 G=(V,E) 是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：|E|>=|V|，而反之不成立。没有回路的无向图是连通的当且仅当它是树，即等价于：|E|=|V|-1。