数据结构之图的定义和术语(未竟)

1、图的定义

图（Graph）是由两个集合构成，一个是非空但有限的顶点集合 \(V\)，另一个是描述顶点之间关系——边的集合 \(E\)（可以是 $ arnothing$）。因此，图可以表示为 \(G = (V, E)\)。每条边是一顶点对 \((v, w)\) 且 \(v, w \in V\)。

通常用 \(|V|\) 表示顶点的数量，用 \(|E|\) 表示边的数量。

2、图的术语

(1)、无向图（Underected Graphs）：无向图中顶点之间的边（Edge）没有方向，即边 \((v, w)\) 等同于 \((w, v)\)。用圆括号“()”表示无向边。边的起点 \(w\) 和终点 \(v\) 次序并不重要。

(2)、有向图（Directed Graphs）：有向图中顶点之间的所有边都有方向，即 \(<v, w>\) 不同于 \(<w, v>\)。用尖括号“<>”表示有向边。有向边也称弧（Are）。弧的“起点（弧头）”和“终点（弧尾）”的次序不能随意颠倒。在不会混淆的场合，有向边和无向边都简称为“边”。

(3)、简单图（Simple Graph）：如果图中出现重边（即边的集合 \(E\) 中有相同的重复元素）或者自回路边（即边的起点和终点是同一个顶点），就叫做非简单图。

(4)、邻接点（Adjacent Vertices）：如果 \((v, w)\) 是无向图中任意一条边，那么称 \(v\) 和 \(w\) 互为邻接点；如果 \(<v, w>\) 是有向图中任意一条边，那么称起点 \(v\) “邻接到”（Adjacent to）终点 \(w\)，也称终点 \(w\) “邻接自”（Adjacent from）起点 \(v\)。比如，考察图二这个有向图 \(G_2\)，顶点 2 邻接到顶点 1，或者说顶点 1 邻接自顶点 2。

(5)、路径（Path）、简单路径（Simple Path）、回路（Cycle，也叫做“环”）、无环图（Acyclic Graph）：图中的一条路径是一顶点序列 \(v_1, v_2, ..., v_N\)，序列中任何相邻的两顶点都能在图中找到对应的边，即 \((v_i, v_{i + 1}) \in E (1 \leqslant i < N)\)。一条路径的长度是这条路径所包含的边数。

一条简单路径是指除了路径的首尾顶点外，其余顶点都是不同的。

有向图中的一条回路是指 \(v_1 = v_N\) 的一条路径。路径长度为 1 的回路是一个自回路（属于非简单图）。简单路径形成的回路称为简单回路（Simple Cycle）。

如果在一个有向图中不存在回路，那么这个有向图称为无环图。

对于无向图，由于顶点是无序的，环路的长度要大于等于 3。

按：本文所有术语和定义皆摘自浙江大学《数据结构 第二版》（陈越、何钦铭），且省略了部分我认为不重要的内容。

(12)、连通图（Connected Graph）、连通分量（Connected Component）：在无向图中，如果从一个顶点 \(v_i\) 到另一个顶点 \(v_j(i \leq j)\) 有路径，则称顶点 \(v_i\) 和 \(v_j\) 是连通的（Connected）。如果图中任意两顶点都是连通的，则称该图是连通图。无向图的极大连通子图称为连通分量。连通分 量的概念包含以下 4 个要点：

• 子图：连通分量应该是原图的子图；
• 连通：连通分量本身应该是连通的；
• 极大顶点数：连通子图含有极大顶点数，即再加入其他顶点将会导致子图不连通；
• 极大边数：具有极大顶点数的连通子图包含依附于这些顶点的所有边。

因此，连通的无向图只有一个连通分量，这个连通分量就是本图。不连通的无向图有多于一个的连通分量。

(13)、强连通图（Strongly Connected Graph）、强连通分量（Strongly Connected Component）；对于有向图来说，若图中任意一对顶点 \(v_i\) 和 \(v_j(i \leq j)\) 均既有从 \(v_i\) 到 \(v_j\) 的路径，也有从 \(v_j\) 到 \(v_i\) 的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量。

强连通分量的概念与连通分量类似，也包含 4 个要点。强连通图本身就是一个强连通分量。不是强连通的有向图有多于一个的强连通分量。