6.1 图的基本概念

有向图与无向图、完全图、子图、连通与强连通、生成树、度与边数的关系等核心概念。

图的定义

基本概念

有向图与无向图

• 有向图：$E$ 是有向边（也称弧）的有限集合。弧是顶点的有序对，记为 $\langle v, w \rangle$，其中 $v$ 称为弧尾，$w$ 称为弧头，称为”从 $v$ 到 $w$ 的弧”或”$v$ 邻接到 $w$”。
• 无向图：$E$ 是无向边（简称边）的有限集合。边是顶点的无序对，记为 $(v, w)$ 或 $(w, v)$，称 $v$ 和 $w$ 互为邻接点。

简单图、多重图与完全图

• 简单图：不存在重复边，不存在顶点到自身的边。数据结构中仅讨论简单图。
• 多重图：若某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联。
• 完全图（简单完全图）：
  • 无向完全图：任意两个顶点之间都存在边，含有 $n(n-1)/2$ 条边；
  • 有向完全图：任意两个顶点之间都存在方向相反的两条弧，含有 $n(n-1)$ 条弧。

子图

设有两个图 $G = (V, E)$ 和 $G' = (V', E')$，若 $V'$ 是 $V$ 的子集，且 $E'$ 是 $E$ 的子集，则称 $G'$ 是 $G$ 的子图。若有满足 $V(G') = V(G)$ 的子图 $G'$，则称其为 $G$ 的生成子图。

连通、连通图和连通分量

在无向图中，若从顶点 $v$ 到顶点 $w$ 有路径存在，则称 $v$ 和 $w$ 是连通的。若图 $G$ 中任意两个顶点都是连通的，则称图 $G$ 为连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量。

强连通图、强连通分量

在有向图中，如果有一对顶点 $v$ 和 $w$，从 $v$ 到 $w$ 和从 $w$ 到 $v$ 之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。

$n$ 个顶点的强连通图最少需要 $n$ 条边（构成一个环路）。

下面的实验可以帮助你验证这些结论：在无向图和有向图之间切换，添加或删除边，观察连通分量（强连通分量）、度和环的变化。

生成树、生成森林

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 $n$，则它的生成树含有 $n - 1$ 条边。对生成树而言，若砍去它的一条边，则会变成非连通图；若加上一条边，则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。

顶点的度、入度和出度

• 无向图中，顶点 $v$ 的度是指依附于顶点 $v$ 的边的条数，记为 $\mathrm{TD}(v)$。无向图的全部顶点的度之和等于边数的 2 倍：$\sum \mathrm{TD}(v_i) = 2e$。
• 有向图中，顶点 $v$ 的度分为入度 $\mathrm{ID}(v)$（以 $v$ 为终点的弧的数目）和出度 $\mathrm{OD}(v)$（以 $v$ 为起点的弧的数目），$\mathrm{TD}(v) = \mathrm{ID}(v) + \mathrm{OD}(v)$。有向图的全部顶点的入度之和与出度之和相等，并且等于边数。

其他术语

即时练习