离散数学 —— 图论
相关概念
设 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-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。
无向图的连通性