数据结构之图的概念

图的基本概念

图 $ G $ 由顶点集 $ V $ 和边集 $ E $ 组成，记为 $ G = (V, E) $。

顶点集 $ V $: 图 $ G $ 中顶点的有限非空集。记作 $ V = { v_1, v_2, , v_n } $，其中 $ |V| $ 表示图 $ G $ 中顶点的个数。
边集 $ E $: 图 $ G $ 中顶点之间的关系（边）集合。记作 $ E $，并用 $ |E| $ 表示图 $ G $ 中边的条数。边可以表示为顶点的有序对。例如，若 $ E = { (u, v) | u V, v V } $。

定义: 若 $ E $ 是有向边（也称为弧）的有限集合，则图 $ G $ 为有向图。弧是顶点的有序对，记为 $ v, w $，其中 $ v $ 和 $ w $ 是顶点。
术语:
- $ v $ 称为弧尾（起点）。
- $ w $ 称为弧头（终点）。
- $ v, w $ 称为从 $ v $ 到 $ w $ 的弧，表示 $ v $ 邻接到 $ w $。

有向图 $ G $ 可表示为：

$ G = (V, E) $

其中，

定义: 若 $ E $ 是无向边（简称边）的有限集合，则图 $ G $ 为无向图。边是顶点的无序对，记为 $ (v, w) $ 或 $ (w, v) $。在无向图中，顶点 $ v $ 和 $ w $ 互为邻接点。
术语: 边 $ (v, w) $ 依附于 $ v $ 和 $ w $，或称边 $ (v, w) $ 和 $ v, w $ 相关联。

无向图 $ G $ 可表示为：

$ G = (V, E) $

其中：

简单图: 一个图 $ G $ 如果满足以下条件，则称为简单图：
1. 不存在重复边。
2. 不存在顶点到自身的边。
示例: 图 6.1 中的 $ G_1 $ 和 $ G_2 $ 均为简单图。
多重图: 若图 $ G $ 中某两个顶点之间的边数大于1条，且允许顶点通过一条边与自身关联，则称为多重图。多重图和简单图的定义是相对的。在数据结构中，仅讨论简单图。

无向完全图: 对于无向图，边的取值范围为 $ 0 $ 到 $ $。有 $ $ 条边的无向图称为完全图。在完全图中，任意两个顶点之间都存在边。
有向完全图: 对于有向图，边的取值范围为 $ 0 $ 到 $ n(n-1) $。有 $ n(n-1) $ 条弧的有向图称为有向完全图。在有向完全图中，任意两个顶点之间都存在方向相反的两条弧。

示例: 图 6.1 中 $ G_1 $ 为无向完全图，而 $ G_2 $ 为有向完全图。

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

并非 $ V $ 和 $ E $ 的任何子集都能构成 $ G $ 的子图，因为这样的子集可能不是图，即子集中的某些边关联的顶点可能不在这个 $ V $ 的子集中。

假设一个图有 $ n $ 个顶点，如果边数小于 $ n-1 $，那么此图必为非连通图。

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

假设一个有向图有 $ n $ 个顶点，如果是强连通图，那么最少需要有 $ n $ 条边（每个顶点至少需要有一条边来保证连通性）。

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

顶点的度: 在无向图中，顶点 $ v $ 的度是指依附于顶点 $ v $ 的边的条数，记为 $ TD(v) $。对于具有 $ n $ 个顶点和 $ e $ 条边的无向图，所有顶点的度之和等于边数的 2 倍，即：

$ _{v V} TD(v) = 2e $
入度和出度: 在有向图中，顶点 $ v $ 的度分为入度和出度：
- 入度: 以顶点 $ v $ 为终点的有向边的数目，记为 $ ID(v) $。
- 出度: 以顶点 $ v $ 为起点的有向边的数目，记为 $ OD(v) $。
在有向图中，顶点的度可以表示为：

$ TD(v) = ID(v) + OD(v) $

对于具有 $ n $ 个顶点和 $ e $ 条边的有向图，所有顶点的入度之和与出度之和相等，并且等于边数：

$ {v V} ID(v) = {v V} OD(v) = e $