离散数学 —— 图论
相关概念
- 无序积
设 $A, B$ 为任意集合, 称集合 $A\ \&\ B = \{(a, b)|a ∈ A, b ∈ B\} $为 $A$ 与 $B$ 的无序积, $(a, b)$ 称
为无序对
- 笛卡尔积
设 $A, B$ 为任意集合, 称集合 $A \times B=\{(a,b)|a∈A∧b∈B\} $为 $A$ 与 $B$ 的笛卡尔积, $<a, b>$ 为有序对
图的定义
一个图 (Graph) 是一个序偶 $< V, E >$，记为 $G =< V, E >$，其中：
$V = {v_1, v_2, · · · , v_n}$ 是有限非空集合，$v_i$ 称为结点 (node)，$V$ 称为结点集。
$E$ 是有限集合，称为边集。$E$ 中的每个元素都有 $V$ 中的结点对与之对应，称之为边 (edge)。
说人话呢就是，一个图由一系列结点和结点对应的边构成，其中“边”描述了结点间的相互关系。
若边 $e$ 与无序结点对 $(u, v)$ 相对应, 则称 $e$ 为无向边(undirected edge), 记为 $e =
(u, v) = (v, u)$, 这时称 $u, v$ 是边 $e$ 的两个端点.
若边 $e$ 与有序结点对 $< u, v >$ 相对应，则称 $e$ 为有向边(directed edge)(或弧), 记为
$e =< u, v >$ , 这时称 $u$ 为 $e$ 的始点 (或弧尾), $v$ 为 $e$ 的终点 (或弧头), 统称为 $e$ 的端点.
子图
设有图 $G =< V, E >$ 和图 $G_1 =< V_1, E_1 >$.
- 若 $V_1 \subseteq V, E_1 \subseteq E$，则称 $G_1$ 是 $G$ 的子图(subgraph)，记为 $G_1 \subseteq G$.
- 若 $G_1 \subseteq G$，且 $G_1 \neq G$(即 $V_1 \subset V$ 或 $E_1 \subset E$)，则称 $G_1$ 是 $G$ 的真子图(proper subgraph)，记为 $G_1 \subset G$.
- 若 $V_1 = V, E_1 \subseteq E$，则称 $G_1$ 是 $G$ 的生成子图(spanning subgraph).
可见生成图包含所有的结点
- 设 $V_2 \subseteq V$ 且 $V_2 \neq \emptyset$，以 $V_2$ 为结点集，以两个端点均在 $V_2$ 中的边的全体为边集的 $G$ 的子图，称为 $V_2$ 导出的 $G$ 的子图，简称 $V_2$ 的导出子图(induced subgraph).
多重图、线图和简单图
平行边
- 在有向图中，两结点间 (包括结点自身间) 若有同始点和同终点的几条边，则这几条边称为平行边；
- 在无向图中，两结点间 (包括结点自身间) 若有几条边，则这几条边称为平行边。两结点 a、b 间相互平行的边的条数称为边 (a, b) 或 的重数。
含有平行边的图称为多重图(multi graph)；非多重图称为线图(line graph)；无环的线图称为简单图(simple graph)。
完全图和补图
设 $G =< V, E >$ 为一个具有 $n$ 个结点的无向简单图，如果 $G$ 中任意两个结点间都有边相连，则称 $G$ 为无向完全图，简称 $G$ 为完全图，记为 $K_n$。
设 $G =< V, E >$ 为一个具有 $n$ 个结点的有向简单图，如果 $G$ 中任意两个结点间都有两条方向相反的有向边相连，则称 $G$ 为有向完全图，在不发生误解的情况下，也记为 $K_n$。
完全图的性质
- 完全图的邻接矩阵除主对角线上的元素为 0 外，其余元素均为 1;
- 无向完全图 $K_n$ 的边数为 $C^2_n =\frac{n(n − 1)}{2}$;
- 有向完全图 $K_n$ 的边数为 $P^2_n = n(n − 1)$.
补图
设 $G =< V, E >$ 为简单图，$G =< V, E_1 >$ 为完全图，则称$G_1 =< V, E_1 − E >$为 $G$的补图(complement of graph)，记为$\bar{G}$。
补图的性质
- 补图 $\bar{G}$ 就是从完全图中删除图 $G$ 中的边;
- 图 $G$ 和它的补图 $\bar{G}$ 有相同的结点，两个结点在 $\bar{G}$ 里相邻，当且仅当它们在 $G$ 里不相邻.
若设简单图 $G$ 的邻接矩阵 $A = (a_{ij})n\times n$，则它的补图 $G$ 的邻接矩阵 $A = (a_{ij})n\times n$为：
$$ \bar{a_{ij}} = \left \{ \begin{aligned} 1 − a_{ij} &, i\neq j \\ 0 \ &, i = j \end{aligned} \right. ,(i, j = 1, 2, 3, · · · , n) $$
补图描述了结点间互斥的关系
度数、边数与结点数
度的定义
图 $G =< V, E >$ 中以结点 $v \in V$ 为端点的次数之和称为结点 $v$ 的度数或度，记为$deg(v)$。显然，有环时则需计算两次。
有向图 $G =< V, E >$ 中以结点 $v$ 为始点的次数称为 $v$ 的出度，记为 $deg^+(v)$ ; 以结点 $v$ 为终点的次数称为 $v$ 的入度，记为 $deg^−(v)$。显然，$deg(v) = deg^+(v) + deg^−(v)$。
在计算无向图的度时，入度和出度的符号是一样的。
度数为 1 的结点称为悬挂结点，以悬挂结点为端点的边称为悬挂边。
握手定理（选择题计算）
无向图所有结点的度数之和等于边的两倍
- 推论：度数为奇数的结点个数为偶数
- 有向图各结点的出度和等于入度和等于边数
图的表示法
- 邻接矩阵法
设图 $G =< V,E >$，其中 $V = {v_1,v_2,··· ,v_n}$, 并假定结点已经有了从 $v_1$ 到 $v_n$ 的次序, 则 $n$ 阶 方阵 $A_G = (a_{ij})_{n\times n}$ 称为 $G$ 的邻接矩阵 (adjacency matrix)，其中
$$ a_{ij} = \left \{ \begin{aligned} 1 &, <v_i,v_j> \in E\ \ or\ \ (v_i,v_j) \in E , \\ 0 &, others \end{aligned} \right. $$
不加约定的，邻接矩阵只能表示“线图”。
图的连通
通路和回路定义
给定图 $G =< V,E >$ 中结点和边相继交错出现的序列
$$ \Gamma = v_0e_1v_1e_2v_2···e_kv_k $$
- 若 $\Gamma$ 中边 $e_i$ 的两端点是 $v_{i−1}$ 和 $v_i$（有向图时 $v_{i−1}$ 与 $v_i$ 分别是 $e_i$ 的始点和终点）， $i = 1,2,··· ,k$则称 $\Gamma$ 为结点 $v_0$ 到结点 $v_k$ 的通路。$v_0$ 和 $v_k$ 分别称为此通路的始点和终点，统称为通路的端点。通路中边的数目 $k$ 称为此通路的长度。当 $v_0 = v_k$ 时，此通路称为回路。
- 若通路中的所有边互不相同，则称此通路为简单通路, 否则称为复杂通路；若回路中的所有边互不相同，则称此回路为简单回路, 否则称为复杂回路。
- 若通路中的所有结点互不相同，所有边也互不相同，则称此通路为基本通路或者初级通路; 若回路中除 $v_0 = v_k$ 外的所有结点互不相同, 所有边也互不相同，则称此回路为基本回路或者初级回路。
通路数量的计算 (下文的基础)
设 $G =< V,E >$ 为线图，$V = {v_1,v_2,··· ,v_n}$，$A = (a_{ij})_{n\times n}$ 为 $G$ 的邻接矩阵， $A^m = (a^{(m)}_{ij} )_{n\times n}$，给定一个通路长度为 $m$ ，（其中，$A^m$ 为矩阵 $A$ 的 $m$次幂（矩阵乘法））则:
- $a^{(m)}_{ij}$ 为从结点 $v_i$ 到结点 $v_j$ 长度为 $m$ 的通路数目;
- $a^{(m)}_{ii}$ 为结点 $v_i$ 到自身的长度为 $m$ 的回路数目;
- $ \sum_{i=1}^n\sum_{j=1}^na^{(m)}_{ij}$ 是 $G$ 中长度为 $m$ 的通路（含回路）总数.
- $\sum_{i=1}^n a^{(m)}_{ii}$ 是 $G$ 中长度为 $m$ 的回路总数.
计算长度不大于 $m$ 的通路数
设矩阵 $B_m = (b_{ij})_{n\times n} = A+A_2 +···+A_m(m\geq 1)$, 则 $b_{ij}$ 表示结点 $v_i$ 到 $v_j$ 长度不大于 $m$ 的通路数目，而 $\sum^n_{i=1}\sum^n_{j=1}b_{ij}$ 则可表示图中长度不大于 $m$ 的通路总数， $\sum^n_{i=1}bii$ 则可表示图中所有长度不大于 $m$ 的回路总数。
连通性的计算与判断
可达关系判定-引理
- 在一个具有 $n$ 个结点的图中，如果从结点 $v_i$ 到结点 $v_j(v_i \neq v_j)$ 存在一条通路，则从 $v_i$ 到 $v_j$ 存在一条长度不大于 $n−1$ 的通路/基本通路.
- 在一个具有 $n$ 个结点的图中，如果存在经过结点 $v_i$ 回路，则存在一条经过 $v_i$ 的长度不大于 $n$ 的回路/基本回路。
说人话就是，在一个图中，最多存在 $n-1$ 个通路或者 $n$ 个回路
可达性关系判定
设 $G =< V,E >$ 为线图，$V = {v_1,v_2,··· ,v_n}，A = (a_{ij})_{n\times n}$ 为 $G$ 的邻接矩阵，
$$ A^m = (a^{(m)}_{ij} )_{n\times n}, m = 1,2,··· ,n \\ B^n = (b^{(n)}_{ij} )_{n\times n} = A+A_2+A_3+···+A_n $$
则有当 $v_i \neq v_j$ 时，如果 $b^{(n)} > 0$ ，则从 $v_i$ 到 $v_j$可达，否则不可达.
可达性矩阵及其简化求法
设 $G =< V,E >$ 是一个线图，其中 $V = {v_1,v_2,··· ,v_n}$，并假定结点已经有了从 $v_1$ 到 $v_n$ 的次序，称 $n$ 阶方阵 $P = (p_{ij})_{n\times n}$ 为图 $G$ 的 可达性矩阵(accessibility matrix)，其中
$$ p_{ij} = \left \{ \begin{aligned} 1 &, v_i to v_j accessable \\ 0 &, Others \end{aligned} \right. $$
由于计算可达性矩阵时需要进行多次乘加法运算，但是可达性矩阵最终是个布尔矩阵，因此可以考虑使用布尔运算进行简化：
设 $G =< V,E >$ 为线图，$A, P$ 分别是 $G$ 的邻接矩阵和可达性矩阵，则有 $P = A\land A^2 \land A^3 \land ···\land A^n$, 这里，$A^i$ 表示做矩阵布尔乘法的 $i$ 次幂.
节点间距离与计算
如果 $v_i$ 到 $v_j$ 可达，则称长度最短的通路为从 $v_i$ 到 $v_j$ 的短程线，从 $v_i$ 到 $v_j$ 的短程线的长度称为从 $v_i$ 到 $v_j$ 的距离(distance)，记为 $d(v_i,v_j)$。如果 $v_i$ 到 $v_j$ 不可达，则通常记为 $d(v_i,v_j) = \infty$
性质
- $d(v_i,v_j) \geq 0 $
- $d(v_i,v_i) = 0$
- $d(v_i,v_k) +d(v_k,vj) \geq d(v_i,v_j)$
- 无向图满足 $d(v_i,v_j) = d(v_j,v_i)$，而有向图不行
- 计算
设 $G =< V,E >$ 为线图，$V = {v_1,v_2,··· ,v_n}, A = (a_{ij})_{n\times n}$ 为 $G$ 的邻接矩阵， $A^m = (a^{(m)}_{ij} )_{n\times n}, m = 1,2,··· ,n$
$$ d(v_i, v_j) = \left \{ \begin{aligned} \infty &, \ a^{(m)}_{ij} = 0 \\ k &, \ k = min\{m|\ a^{(m)}_{ij} \neq 0\} ,(m = 1,2,3,··· ,n) \end{aligned} \right. $$
显然，这里也可以使用邻接矩阵的布尔积幂来判定
总结
以上内容说人话呢就是，利用“通路数量的计算”方法，如果要判断两节点间“可达性”，则只需要铁憨憨地将“路径长度”从 $0$ 算到 $n-1$ (回路的话是 $n$)，只要能算出来至少一条路径，就说明它可达；而计算"距离"则只需要严格的从 $0$ 开始算到 $n-1$ 即可，第一次算出的非0结果即为最短距离
有向图的连通性
若无向图 $G$ 中的任何两个结点都是可达的，则称 $G$ 是连通图，否则称 $G$ 是非连通图或分离图。
性质
- 无向完全图 $K_n(n \geq 1)$ 都是连通图;
- 多于一个结点的零图都是非连通图;
- 非平凡无向线图 $G$ 是连通图当且仅当它的可达性矩阵 $P$ 的所有元素均为 $1$。
