数据结构:图论入门

图论起源于欧拉对哥尼斯堡七桥问题的解决. 他构建的图模型将陆地用点来表示, 桥梁则用线表示, 如此一来, 该问题便转化为在图中能否不重复地遍历每条边的问题.

图论的应用

地图着色

在地图着色问题中, 我们用顶点代表国家, 将相邻国家之间用边相连. 这样, 问题就转化为用最少的颜色给图的顶点着色, 同时要保证相邻顶点的颜色不同. 四色定理表明, 任何地图都可以用四种颜色进行着色.

频率分配

以顶点表示发射机, 将干扰范围内的发射机之间用边相连. 频率分配问题就可以转化为给顶点标记数字, 使得相邻顶点标记的数字差值尽可能大.

燃气供应

利用平面图进行建模, 其中顶点表示路口, 边表示道路, 面表示区域. 通过寻找最小面生成子图, 能够确定铺设燃气管道的最优道路网络, 从而实现成本的最小化.

布局规划

在 VLSI(超大规模集成电路)和建筑布局规划中, 用图来表示模块或房间之间的连接关系. 通过对平面图进行三角剖分, 构建对偶图并绘制矩形图, 从而得到布局方案.

其他应用

图论还广泛应用于万维网社区发现, 生物信息学(如 RNA 结构描述), 软件工程(如控制流图用于软件测试)等诸多领域.

图的基本概念

图的定义

图(Graph)

一个图 $G$ 由两个集合组成, 即顶点集 $V (G)$ 和边集 $E (G)$ , 通常记为 $G = (V, E)$ . 顶点(Vertex, 也称为节点 Node)是图的基本元素, 用于表示研究的对象; 边(Edge)是连接两个顶点的线, 用于表示对象之间的关系. 若图中无自环边( 从 $v$ 到 $v$ ) 且无重边(两个节点之间存在多条边), 则为简单图, 反之则为多重图.

顶点(Vertex)

顶点是图中的基本元素, 即图的节点. 顶点可以有自己的属性, 例如在社交网络的图模型中, 顶点代表用户, 每个顶点可能包含用户的年龄, 性别等属性信息.

边(Edge)

边是连接两个顶点的线. 根据边是否有方向, 图可分为无向图和有向图. 在无向图中, 边没有方向, 若顶点 $u$ 和 $v$ 之间有边, 则表示为 $(u, v)$ , 且 $(u, v)$ 和 $(v, u)$ 表示同一条边; 在有向图中, 边有方向, 从顶点 $u$ 指向顶点 $v$ 的边表示为 $(u, v)$ , 它与从 $v$ 指向 $u$ 的边 $(v, u)$ 是不同的边.

邻接(Adjacency)

在无向图中, 如果两个顶点 $u$ 和 $v$ 之间有一条边 $(u, v)$ , 则称顶点 $u$ 和 $v$ 是邻接的; 在有向图中, 如果存在一条从顶点 $u$ 到顶点 $v$ 的有向边 $(u, v)$ , 则称顶点 $u$ 邻接到顶点 $v$ , 顶点 $v$ 邻接自顶点 $u$ .

度(Degree)

对于无向图中的一个顶点 $v$ , 它的度是与该顶点相关联的边的数量, 记为 $d (v)$ ; 在有向图中, 顶点的度分为入度和出度. 入度(In - degree)是指以该顶点为终点的有向边的数量, 记为 $d^-(v)$ , 出度(Out - degree)是指以该顶点为起点的有向边的数量, 记为 $d^+(v)$ , 顶点 $v$ 的度等于其入度与出度之和, 即 $d(v)=d^-(v) + d^+(v)$ .

路径(Path)

在图中, 从一个顶点 $v_0$ 开始, 依次经过一系列相邻的顶点 $v_1, v_2, \cdots, v_n$ 所形成的顶点序列, 其中 $(v_{i - 1}, v_i) \in E$ (对于无向图)或 $(v_{i - 1}, v_i) \in E$ (对于有向图, $\cdots, n$ ), 这个顶点序列就称为从 $v_0$ 到 $v_n$ 的路径. 路径中边的数量称为路径的长度.

回路(Cycle)

在图中, 起点和终点相同的路径称为回路, 也叫环. 也就是说, 如果路径 $v_0, v_1, \cdots, v_n$ 满足 $v_0 = v_n$ 且 $\geq 1$ , 则它是一个回路.

连通图(Connected Graph)

在无向图中, 如果对于图中的任意两个顶点 $u$ 和 $v$ , 都存在一条从 $u$ 到 $v$ 的路径, 则称该图是连通图; 在有向图中, 如果对于图中的任意两个顶点 $u$ 和 $v$ , 都存在从 $u$ 到 $v$ 的路径以及从 $v$ 到 $u$ 的路径, 则称该有向图是强连通图. 如果一个有向图不是强连通图, 但忽略边的方向后得到的无向图是连通图, 则称该有向图是弱连通图.

子图(Subgraph)

给定一个图 $G = (V, E)$ , 如果存在另一个图 $G^{'} = (V^{'}, E^{'})$ , 其中 $V'\subseteq V$ ( $V^{'}$ 是 $V$ 的子集)且 $E'\subseteq E$ ( $E^{'}$ 是 $E$ 的子集), 并且 $E^{'}$ 中的边所关联的顶点都在 $V^{'}$ 中, 则称 $G^{'}$ 是 $G$ 的子图.

树(Tree)

无向连通且无回路的图称为树. 树中度数为 1 的顶点称为叶子节点, 其他顶点称为内部节点. 在树中, 任意两个顶点之间恰好存在一条路径. 有根树是一种特殊的树, 它有一个被指定为根的顶点, 从根到其他顶点有唯一的路径.

图的分类

正则图

所有顶点度相等的图是正则图, 当度为 $k$ 时, 称为 $k -$ 正则图. 例如, 零图是 $0 -$ 正则图, 简单循环是 $2 -$ 正则图, 彼得森图是 $3 -$ 正则图, 还有 $5 -$ 正则的甜甜圈图和 $d -$ 维超立方体等.

子图

图 $G = (V, E)$ 的子图 $G^{'} = (V^{'}, E^{'})$ 满足 $\subseteq V$ 且 $\subseteq E$ . 可以通过删除顶点或边得到子图, 如 $G - e$ , $G - v$ . 还有顶点集或边集诱导的子图, 如 $G [W]$ , $G [F]$ .

特殊图类

包括空图(边集为空, 记为 $N_{n}$ ), 完全图(任意两顶点相邻, $K_{n}$ 有 $n (n - 1) /2$ 条边), 独立集和二分图(顶点集可分成两个独立子集, 完全二分图 $K_{m,n}$ 有 $m \times n$ 条边), 路径图( $P_{n}$ 除端点外顶点度为 2 ), 循环图( $C_{n}$ 所有顶点度为 2 ), 轮图( $W_{n}$ 由 $C_{n - 1}$ 加新顶点连接所有 $C_{n - 1}$ 顶点得到).

图的操作

图的运算

集合运算: 图 $G_{1}$ 和 $G_{2}$ 的并集 $G_{1} \cup G_{2}$ 顶点集为 $V_{1} \cup V_{2}$ , 边集为 $E_{1} \cup E_{2}$ ; 交集 $G_{1} \cap G_{2}$ 顶点集为 $V_{1} \cap V_{2}$ , 边集为 $E_{1} \cap E_{2}$ .
其他运算: 图 $G$ 的补图 $\bar{G}$ 与 $G$ 顶点集相同, 两顶点在 $\bar{G}$ 中有边当且仅当在 $G$ 中无边; 细分是删边并通过新顶点添加路径; 收缩边是删边并合并两顶点.

图同构

图 $G_{1}$ 和 $G_{2}$ 间存在一一对应关系, 使对应顶点间边数相等, 则两图同构, 记为 $G_{1} \cong G_{2}$ . 同构关系是等价关系, 判断图同构目前尚无多项式时间算法.

度序列

图的度序列是顶点度的非增排列, 满足度和公式(和为偶数)的序列可能是图的度序列, 简单图的度序列叫图序列, 可通过递归算法判断.

数据结构与图的表示

邻接矩阵

邻接矩阵是 $n \times n$ 矩阵, 元素为两顶点间边数, 简单图邻接矩阵元素为 0 或 1 , 主对角线为 0 , 空间复杂度 $O(n^{2})$ ; 关联矩阵是 $n \times m$ 矩阵, 元素表示顶点与边是否关联, 空间复杂度 $n \times m$ ; 邻接表是数组, 每个顶点对应一个包含其邻居记录的列表, 空间复杂度 $O (n + m)$ .

邻接表

用数组存储顶点的邻接顶点列表, 空间复杂度 $O (n + m)$ , 适用于边数较少的图.