无向图

  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。