一、图的定义和基本术语：
  • 图


(1)无向图和有向图

  • 无向图：每条边都是无方向的。

  • 有向图：每条边都是有方向的。

(2)完全图


  • 完全图：任意两个点都有一条边相连。

(3)权与网：图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网。
(4)邻接(关联/依附)：有边/弧相连的两个定点之间的关系。存在(vi，vj)，称vi和vj互为邻接点。
(5) 顶点的度：与该顶点相关联的边的数目。记为TD(v)。

在有向图中, 顶点的度等于该顶点的入度与出度之和。
顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v)
顶点 v 的出度是以 v 为始点的有向边的条数, 记作OD(v)

当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时，是一颗有向的树。
(6)路径和回路

  • 路径：接续的边构成的顶点序列。
  • 路径长度：路径上边或弧的数目/权值之和。
  • 回路(环)：第一个顶点和最后一个顶点相同的路径。
  • 简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。
  • 简单回路(简单环)：除路径起点和终点相同外，其余顶点均不相同的路径。

(7)连通图

  • 连通图（强连通图）
    在无（有）向图G=( V, {E} )中，若对任何两个顶点 v、u 都存在从v 到 u 的路径，则称G是连通图（强连通图）。
    (8)子图：

例:(b)、© 是 (a) 的子图
(9)连通分量(强连通分量)：

无向图G 的极大连通子图称为G的连通分量。
极大连通子图意思是：该子图是 G 连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通。

可以理解为：有向图的连通分量就是强连通分量。
(10)极小连通子图：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通。
(11)生成树/森林：

  • 生成树：包含无向图G 所有顶点的极小连通子图。
  • 生成森林：对非连通图，由各个连通分量的生成树的集合。