图的基本概念

图（Graph）由顶点集 $V$ 和边集 $E$ 组成，记为 $G=(V,E)$。其中 $V$ 是非空有限集，$E$ 是 $V$ 上关系的有限集。

基本术语

• 无向图：边 $(u,v)$ 无方向，$(u,v)=(v,u)$
• 有向图：弧 $<u,v>$ 有方向，从 $u$ 到 $v$，$u$ 为弧尾，$v$ 为弧头
• 简单图：无自环、无重边的图
• 多重图：允许重边和自环的图
• 完全图：任意两点之间都有边/弧相连
  • 无向完全图：$n$ 个顶点，$n(n-1)/2$ 条边
  • 有向完全图：$n$ 个顶点，$n(n-1)$ 条弧
• 稀疏图 / 稠密图：边数远小于 / 接近完全图的边数
• 网：带权图，边/弧上带有数值（权/权重）
• 子图：$V' \subseteq V$ 且 $E' \subseteq E$

连通性

• 连通：无向图中从 $u$ 到 $v$ 有路径
• 连通图：无向图中任意两点连通
• 连通分量：无向图的极大连通子图
• 强连通：有向图中 $u \to v$ 且 $v \to u$
• 强连通图：有向图中任意两点强连通
• 强连通分量：有向图的极大强连通子图
• 生成树：包含图中所有顶点的极小连通子图（$n-1$ 条边）

度

• 无向图：顶点的度 = 与该顶点关联的边数
  • 所有顶点度之和 $= 2\times$ 边数（握手定理）
• 有向图：入度 $ID(v)$ + 出度 $OD(v)$
  • 所有顶点入度之和 = 所有顶点出度之和 = 弧数