图论

简要

• 简单温习离散数学图论相关内容，图论知识可以用在数据结构 图 和 树(特殊的图) 中
• 在后续的数据结构介绍中，大概率也用不到这么多知识，也存在有些必备知识没有罗列出来的情况，后续在介绍数据章节缺什么就补什么

参考书籍/资料/网站

• Discrete Mathematics (Gary Chartrand, Ping Zhang)
• OI Wiki 图论相关概念

定义

• $G = (V, E)$

  在此仅研究有限图，即 V 和 E 是有限集合

• 顶点(vertex) 集合 $V/V(G) = \{v_{x}, 1 \le x \le n \}$, 非空集合
• 边(edge) $E/E(G) = \{(v_{x}, v_{y}), v_{x} \isin V, v_{y} \isin V \}$
• 图 G 的顶点数 $|V(G)|$ 称为图 G 的 阶(order), 边数 $|E(G)|$ 称为图 G 的 大小(size)

部分图分类

无向图(undirected graph)

• $E$ 中的每个元素 $(v_{x}, v_{y})$ 是无序的，称为 无向边(undirected edge)

有向图(directed graph)

• $E$ 中的每个元素 $(v_{x}, v_{y})$ 是有序的，称为 有向边(directed edge), $v_{x}$ 和 $v_{y}$ 分别称为 起点(initial vertex) 和 终点(terminal vertex)

简单图

没有 自环 和 重边 的图

• 自环(loop): 存在边 $e = (x, x), \quad e \isin E$
• 重边(multiple edge): 满足 $e_{1} = e_{2}, \quad e_{1}, e_{2} \isin E$

子图

$G = (V, E)$, 存在图 $H = (V', E'), V' \sube V, E' \sube E$, 记作 $H \sube G$

• 导出子图/诱导子图(induced subgraph): 满足 $\forall{v_{x},v_{y}} \isin V',$ 若 $(v_{x},v_{y}) \isin E$, 则 $(v_{x},v_{y}) \isin E'$, 即图 $G$ 中，连接两个包含在 $V'$ 的顶点的边 $e$，必然存在于 $E'$ 中
• 生成子图/支撑子图(spanning subgraph): 满足 $V' = V$

完全图

一个图的所有顶点两两相邻

性质

相邻(adjacent)

• 若 $(v_{x},v_{y}) \isin E$, 则顶点 $v_{x}$ 和 $v_{y}$ 相连，$v_{x}$ 和 $v_{y}$ 是 相邻(adjacent) 的
  • 与顶点 $v$ 相邻的顶点集合称为 $v$ 的 邻域(neighborhood)，记作 $N(v)$

  在有向图中，顶点xy相邻，不一定代表x可到达y(或y可到达x)，有向图的相邻概念需要区分方向

• 若 $(w, x), (y, z) \isin E$, 有 $(w, x) \cap (y, z) \ne \empty$, 则边 $(w, x)$ 和 $(y, z)$ 是 相邻 的

度(degree)

度(degree) 表示的是与一个顶点 $v$ 相邻的其它顶点数量(或是与该顶点关联的边的数量)，记作 $d(v) / deg(v) / deg_{G}(v)$

• 若 $d(v) = 0$, $v$ 为 孤立点(isolated vertex)
• 若 $d(v) = 1$, $v$ 为 叶节点(leaf vertex)/悬挂点(pendant vertex)
• 在一个图中，所有顶点度数的最小值称为 最小度(minimum degree), 最大值称为 最大度(maximum degree), 分别记作 $\delta(G) = \min_{v \isin V}d(v)$, $\Delta(G) = \max_{v \isin V}d(v)$

无向图

1. 在无向简单图中, $d(v) = |N(v)|$
2. 在任意无向图 $G = (V, E)$ 中, $\sum_{v \isin V}d(v) = 2|E(G)|$

有向图

1. 以一个顶点作为起点的边的条数称为 出度(outdegree), 记作 $d^{+}(v)$; 以一个顶点作为终点的边的条数称为 入度(indegree), 记作 $d^{-}(v)$, 有 $d^{+}(v) + d^{-}(v) = d(v)$
2. 在任意有向图 $G = (V, E)$ 中, $\sum_{v \isin V}d^{+}(v) = \sum_{v \isin V}d^{-}(v) = |E(G)|$

路径(path)

途径(walk)

连接一连串顶点的边的序列 $w = e_{1}, e_{2}, ..., e_{k}$, 使得存在一个顶点序列 $v_{0}, v_{1}, ..., v_{k}$, 满足 $e_{i} = (v_{i-1}, v_{i}), i \isin [1, k]$ (或 $v_{0} \rightarrow v_{1} \rightarrow v_{2} \rightarrow ...\rightarrow v_{k}$), $k$ 为途径长度

迹(trail)

对于途径 $w$, $e_{1}, e_{2}, ..., e_{k}$ 两两不同

路径(path)/简单路径(simple path)

对于途径 $w$, 连接的点的序列两两不同

回路(circuit)

对于途径 $w$, $v_{0} = v_{k}$

环/圈(cycle)/简单回路/简单环(simple circuit)

对于 回路 $w$, $v_{0} = v_{k}$ 是点序列中唯一重复出现的点对(也就是途径中只有一个圈)

连通(connected)

无向图

• 无向图 $G = (V, E)$ 中，对于 $u, v \isin V$, 若存在途径使得 $v_{0} = u, = v_{k} = v$, 则称 $u, v$ 是连通的(顶点与自身连通，边上的两个顶点连通)
• 若无向图 $G$ 中任意两个顶点均连通，那么 $G$ 是连通图
• 若 $H$ 是 $G$ 的连通子图，且不存在连通图 $F$ 满足 $H \sub F \sube G$, 则称 $H$ 是 $G$ 的一个 连通块/连通分量(connected component) (极大连通子图)

有向图

• 有向图 $G = (V, E)$ 中，对于 $u, v \isin V$, 若存在途径使得 $v_{0} = u, = v_{k} = v$, 则称 $u$ 可达 $v$ (顶点可达自身，边上的起点可达终点，无向图的连通视为双向可达)
• 若有向图中顶点两两互相可达，称该图是 强连通(strongly connected) 的
• 若有向图中的边替换为无向边后是连通图，称该无向图是 弱连通(weakly connected) 的
• 强连通分量(strongly connected component), 弱连通分量(weakly connected component)

割(cut)

• 连通图 $G = (V, E)$, 若从 $G$ 中删除点集 $V'(V' \sube V)$ 后 $G[V \backslash V']$ 不是连通图，称 $V'$ 为 $G$ 的 点割集(vertex cut/separating set), 大小为一的点割集称为 割点(cur vertex)
• 连通图 $G = (V, E)$, 若从 $G$ 中删除边集 $E'(E' \sube E)$ 后 $G' = (V, E \backslash E')$ 不是连通图，称 $E'$ 为 $G$ 的 边割集(vertex edge set), 大小为一的边割集称为 桥(bridge)

遍历

• 深度优先搜索(Depth First Search, DFS): 每次都尝试往更深的结点走
• 广度优先搜索(Breadth First Search, BFS): 每次都尝试访问同一层结点
  • 找到的路径是从起点开始的 最短 合法路径