计算机应用数学学习笔记
\(\newcommand{\bR}{\mathbb{R}}\) \(\newcommand{\OV}{\overline}\)
上半期太摸了，没记。
图和树
★ 割集 (cut set) ：\(C = \{(u, v) \in E \colon u \in S, v \in V \setminus S\}\) 。
★ 引理 1 ：任意割集的最小边一定在最小生成树内。
★ 引理 2 ：任意环上的最大边一定不在最小生成树内。
P / NP
★ P: 可以被多项式时间解决的问题。
★ NP: 可以在多项式时间检查一组解的问题。
★ 定理 1 ：P 属于 NP 。
★ NP-Complete: 所有 NP 问题可以规约到的问题，NP 问题中最难的一部分。
★ 定理 2 ：如果任何一个 NP-Complete 问题多项式可解，则 P 等于 NP 。
欧拉定理
★ 平面图 (planar graph) ：能画在平面上的简单连通图。
★ 欧拉定理 (Euler's Formula)：平面图上 \(n + f = m + 2\) 。其中 \(n, m, f\) 分别是点数、边数、面数。
★ 推论 1：\(n\) 个点的树边数为 \(n - 1\) 。
因为 \(f = 1\) 。
★ 推论 2：\(n (n \ge 3)\) 个点的平面图边数不超过 \(3n - 6\) 。
每一个面至少邻接三条边，一条边与至多两个面接触。 故 \(3f \le 2m\) ，代入欧拉定理得 \(m \le 3n - 6\) 。
★ 极大平面图 (maximal planar graph) ：任意加上一条边都不再是平面图的平面图。 一个平面图是极大的当且仅当每个面邻接恰好 3 条边，每条边恰好邻接两个面。
★ 推论 3：\(n (n \ge 3)\) 个点的极大平面图边数恰为 \(3n - 6\) 。
★ 推论 4：\(n (n \ge 4)\) 个点的极大平面图，每个点的度数不少于 \(3\) 。
★ 推论 5：\(n (n \ge 4)\) 个点的平面图至少有 \(4\) 个点的度数不超过 \(5\) 。
不妨假设平面图极大。若不成立则 \(2m \ge 3 \times 3 + (n - 3) \times 6 = 6n - 9 > 2m\) ，矛盾。
★ 推论 6：三维空间的封闭凸多边形满足：顶点数 + 面数 = 边数 + 2。
平面图染色
★ 对偶图 (dual graph) ：平面图的对偶图是将面看作点，两个邻接的面看作有一条连边。 对偶图满足 \(n' = f\), \(m' = m\), \(f' = n\), 仍然是平面图。
★ 染色 (coloring) ：给每个节点一个颜色标记，使得任意一条边的两个端点颜色不同 （面的染色问题可以转为对偶图的染色问题）。
★ \(k\) 染色 (\(k\)-colorable) ：能够用 \(k\) 种不同的颜色进行染色。
★ 色数 (chromatic number) ：最小的 \(k\) 使得图能 \(k\) 染色。
★ 引理 1 ：如果图的最大度为 \(d\) ，能 \(d + 1\) 染色。
数学归纳法，每次加一个点都可以分配合法的颜色。
★ 引理 2 ：平面图能 \(6\) 染色。
不妨假设 \(n \ge 4\) 且极大。数学归纳法，选取一个度数不超过 \(5\) 的点 \(u\) ， 在去掉 \(u\) 点的子图染色后容易确定 \(u\) 的颜色。
★ 引理 3 ：平面图能 \(5\) 染色。
不妨假设 \(n \ge 4\) 且极大。数学归纳法，选取一个度数不超过 \(5\) 的点 \(u\) 。 \(u\) 的度数不超过 \(4\) 的情况是简单的，考虑度数为 \(5\) 。
将 \(u\) 相连的 \(5\) 个点在平面上的位置顺时针排为 \(a_1, a_2, a_3, a_4, a_5\) 。 我们一定可以在其中选出两个不相连的点（否则这个完全子图不是平面图）， 设为 \(x, y\) 。
在去掉 \(u\) 点的子图 \(G'\) 中，可以将 \(x\) 和 \(y\) 合并为一个点 （因为 \(x\) 和 \(y\) 邻接于同一个面且两者之间没有连边）， 得到图 \(G''\) 。
将 \(G''\) 染色，然后放在 \(G'\) 中得到一个染色方案满足 \(x\) 和 \(y\) 的颜色相同！于是可以给 \(u\) 一个合法的颜色。
★ 四色定理：平面图一定可以被染 \(4\) 个颜色。
有标号树
★ 有标号树 (labeled tree) ：每个点有一个唯一的标号 (\(0\) 到 \(n-1\)) 的树。 两个有标号树是相同的当且仅当它们的边集相同。
★ 扩展 Prufer 编码 (extended Prufer code) ： 以 \(0\)
作为根将树看作有根树，每次选取编号最小的叶子，列出该叶子和其父亲然后删掉该边。
如上图编码后（每列代表一条边，第一行和第二行分别是叶子和父亲）为
1
21 4 3 5 6 7 8 9 2
6 3 0 6 2 9 9 2 0
★ 引理 1 ：扩展 Prufer 编码中，第一行第 \(k\) 列的数， 就是第二行的第 \(k\) 到 \(n-1\) 列，以及第一行的第 \(1\) 到 \(k-1\) 列中， 未出现过的最小正整数 (mex) 。
每个点的父亲唯一，所以不能在第一行的前面 (\(1\) 到 \(k-1\)) 出现过。
在树上已经删掉前面的边后，我们要找的这个标号是一个最小的叶子， 叶子不是任何点的父亲，所以不能在第二行的后面 (\(k\) 到 \(n-1\)) 出现过。
同时不是任何点的父亲的点一定是叶子，因此这些未出现过的数都是叶子， 我们要找的标号必然是其中最小的一个。
★ 引理 2 ：扩展 Prufer 编码中，第二行可以决定第一行。
直接得自引理 1 。
★ 引理 3 ：扩展 Prufer 编码中，第二行最后一列一定是 \(0\) 。
显然。
★ Prufer 编码：扩展 Prufer 编码中第二行的前 \(n-2\) 列。
★ 引理 4 ：每个长为 \(n-2\) 的取值 \(0\) 到 \(n-1\) 的序列都是某个有标号树的 Prufer 编码。
展开为扩展 Prufer 编码后可以得到一个边集，需要证明该边集构成一棵树。
首先第一行一定是 \(1\) 到 \(n-1\) 的排列（展开的过程中不会出现重复的数）。 通过重标号，不妨假设第一行恰为 \(1\) 到 \(n-1\) 。
此时可以发现每一列都是第一行小于第二行（特别地假设 \(0\) 最大）， 否则如果第二行第 \(k\) 列为 \(x < k\) ，那么在扩展第 \(x\) 列的时候就会出现矛盾。
所以该边集同时给出了一个拓扑序，于是一定是一棵树。
★ 定理 5 ：\(n\) 个点的有标号树的数量是 \(n^{n-2}\) 。
树和 Prufer 编码是一一对应的，从引理 4 可以看到，后者的数量恰为 \(n^{n-2}\) 。
无标号树
★ 无标号树 (unlabeled tree) ：两个无标号树是相同的当且仅当能够通过标号使得它们成为相同的有标号树。 记 \(n\) 个点的无标号树的数量为 \(T_n\) 。
★ 引理 1 ：\(T_n \ge \dfrac{n^{n-2}}{n!}\) 。
标号的方式有 \(n!\) 种，有标号树的数量是 \(n^{n-2}\) 。
无标号树也可以编码，任选一个点为根，遍历（深搜）整棵树，每次远离根记一个 \(1\) ，靠近根记一个 \(0\) ， 得到的长为 \(2(n-2)\) 的 01 序列就是一个编码（但不是每个 01 序列都是合法的编码）。
★ 引理 2 ：\(T_n \le 2^{2(n-1)}\) 。
即 01 序列的数量。
★ 定理 3 ：若 \(n > 30\) 则 \(2^n \le T_n \le 4^n\) 。
放大引理 1 和引理 2 的界。
生成树
★ 拉普拉斯矩阵：度数矩阵减去邻接矩阵。记为 \(L = D - A\) 。
★ 关联矩阵：大小为 \(|V| \times |E|\) ，每一条边 \((u, v) \in E\) 代表一个列向量，第 \(u\) 行为 \(1\) 第 \(v\) 行为 \(-1\) 。记为 \(M\) 。
★ 引理 1 ：\(M \cdot M^T = L\) 。
★ 引理 2 ：\(M\) 根据选出若干列组成矩阵 \(M_0\) ，若其对应边集是生成树则 \(|M_0| = \pm 1\) 否则 \(|M_0| = 0\) 。
★ 矩阵树定理：有标号无向图的生成树数量等于拉普拉斯矩阵去掉第 \(i\) 行第 \(i\) 列的行列式。记为 \(t(G) = |L^{(i)}|\) 。
★ 引理 3 ：\(L\) 的特征多项式的一次项系数为 \(-|V| t(G)\) 。
★ 定理 4 ：\(t(G) = \lambda_2 \lambda_3 \cdots \lambda_{|V|} / |V|\) ，其中 \(0 \le \lambda_i \le \lambda_{i+1}\) 是 \(L\) 的特征值。
★ 定理 5 ：电路图中 \(a\) 到 \(b\) 的电阻为 \(\dfrac{t(G + (a, b)) - t(G)}{t(G)}\) 。
旅行商问题
假定图 \(G\) 的边权满足三角形不等式，即 \(w(i, j) + w(j, k) \ge w(i, k)\) 。
★ Tree Shortcut Algorithm: 找到一颗最小生成树，写出欧拉序，只保留每个点第一次出现的位置，得到一个旅行路径。
★ 定理 1 ：该算法得到的旅行路径的代价不超过最小代价的两倍。
线性规划
★ 标准线性规划：给定 \(A \in M_{m\times n}, b \in \bR^m, c \in \bR^n\) ， 求 \(x \in \bR^n\) 在满足 \(A x \le b\) 和 \(x \ge 0\) 的前提下最大化 \(c^T x\) 。
★ 松弛线性规划：给定 \(A \in M_{m\times n}, b \in \bR^m, c \in \bR^n\) ， 求 \(x \in \bR^n\) 在满足 \(A x = b\) 和 \(x \ge 0\) 的前提下最大化 \(c^T x\) 。
★ 标准线性规划的对偶： 求 \(y \in \bR^m\) 在满足 \(A^T y \ge c\) 和 \(y \ge 0\) 的前提下最小化 \(b^T x\) 。
★ 松弛线性规划的单纯形法：
- 选定 \(m\) 个基础变量，其余的 \(n - m\) 个为自由变量，假定自由变量全零即可得到一个解，称为基础解 (basic solution) 。
- 若基础变量解出来全部非负，则得到了基础可行解 (basic feasible solution) 。
- 解出基础变量关于自由变量的线性函数，然后代入目标函数。
- 如果目标函数的系数全部非负就找到了最优解，否则交换一个自由变量和一个基础变量。
如何判断松弛线性规划是否可解？ 可以构造另一个松弛线性规划：在 \(A x + I z = b\) 和 \(x, z \ge 0\) 的前提下最小化 \((1, \ldots, 1) z\) 。 那么原问题可解当且仅当新问题中的最优解恰为 \(0\) 。并且新问题有平凡解 \(x = 0, z = b\) 。
★ 分离定理：对于凸集合和以外的点 \(x_0\) ，存在向量 \(w\) 使得 \(w \cdot x_0 \le w \cdot x\) 对于任意凸集内的点 \(x\) 成立。
★ Farkas 引理：以下两个线性系统有且仅有一个成立： \[ Ax \le 0, c^T x > 0 \] 和 \[ A^T y = c, y \ge 0 \]
博弈
零和游戏：双方的收益和恒为 0 。
纳什均衡 (Nash equilibrium) ：如果任一方在知道对方的策略下无法通过改变策略增加期望收益，则双方的策略是纳什均衡的。
香农信道容量
★ 正交表示：对于无向图 \(G = (V, E)\) ，可以为每个点 \(i\) 分配一个 \(\mathbb{R}^d\) 内的单位向量 \(u_i\)，使得 \((i, j) \in E \iff u_i \cdot u_j \ne 0\) 。 更一般地，这个向量可以是一般的内积空间里的元素。
★ 引理 1 ：一定存在分配方式使得正交表示中 \(d \le n\) 。
★ 引理 2 ：若 \(I \subseteq V\) 是独立集，\(e \in \mathbb{R}^d\) 是任意单位向量，则 \[ \sum_{i \in I} (u_i \cdot e)^2 \le 1 \]
独立集中的 \(u_i\) 是两两正交的（反之亦然），\(u_i \cdot e\) 是正交基上的投影。
★ 引理 3: 最大独立集的大小 \(\alpha(G) \le \max (u_i \cdot e)^{-2}\) 。
引理 2 进一步得到 \(|I| \min\limits_{i \in I} (u_i \cdot e)^2 \le 1\) ， 两边取逆取 \(I\) 为最大独立集再放大取点范围即可。
★ Lovasz theta 函数： \(\vartheta(G) = \inf\limits_{u,e} \max\limits_i (u_i \cdot e)^{-2}\) 。
★ 强乘积 (strong product): 两个图 \(G = (V, E)\) 和 \(H = (V', E')\) 的强乘积记为 \(G \boxtimes H\) ， 点集为 \(V \times V'\) ，其中 \((i, i')\) 到 \((j, j')\) 有边当且仅当 其中一个维度有边另一个不变，或者两个维度同时有边。
★ 引理 4 ：\(\vartheta(G \boxtimes H) = \vartheta(G) \vartheta(H)\) 。
\(G \boxtimes H\) 的正交表示可以选张量 \(u_i \otimes v_j\) ， 其内积为 \((a \otimes b) \cdot (c \otimes d) = (a \cdot c) (b \cdot d)\) 。 然后列出定义即可证明。
★ 补图：\(G = (V, E)\) 的补图记为 \(\OV{G}\) ，点集不变边集取补。
★ 定理 5 ：\(\alpha(G) \le \vartheta(G) \le c(\OV{G})\) ，其中 \(c\) 表示色数。
第一个不等号即引理 3 。
★ 信道容量：传送 \(k\) 个符号的信息的信道容量为 \(k\) 个 \(G\) 的强乘积的最大独立集大小。记为 \(\alpha(G^{(k)})\) 。
★ 香农信道容量：\(\Theta(G) = \max_k \alpha(G^{(k)})^{1/k} = \lim_{k \to \infty} \alpha(G^{(k)})^{1/k}\) 。
★ 定理 6 ：\(\alpha(G^{(k)}) \ge \alpha(G)^k\) 。
匹配
★ 定理 1 ： 如果二分图每个点都有相同的度数，那么存在完美匹配。
★ 霍尔定理 (Hall's Theorem) ： 一个二分图有完美匹配当且仅当两端点数相同 \(|A| = |B|\) ， 并且对于 \(A\) 的任意子集 \(S \subseteq A\) ， 其邻接点集 \(T \subseteq B\) 满足 \(|T| \ge |S|\) 。
必要性显然，证充分性，对点数归纳。
任取相连的 \(a \in A, b \in B\) 。 如果 \(A \setminus \{a\}\) 和 \(B \setminus \{b\}\) 之间满足条件则根据归纳假设证毕。 否则存在 \(S \subseteq A \setminus \{a\}\) ，其邻接点集为 \(T\) ， 然而 \(T\) 去掉 \(b\) 后比 \(S\) 小，也就是说 \(b \in T\) 且 \(|T| = |S|\) 。
注意到 \(S\) 到 \(T\) ，以及 \(B \setminus T\) 到 \(A \setminus S\) 都是满足条件，从而根据归纳假设有完美匹配的。
★ 定理 2 ：若 \(M, M^*\) 是极大匹配和最大匹配则 \(|M| \ge |M^*| / 2\) 。
★ 定理 3 ：二分图中若 \(M_1, M_2\) 是两个匹配则 \(M_1 \oplus M_2\) 由孤立点、交错环、交错路构成。 若 \(|M_1| > |M_2|\) 则一定有交错路。
Pfaffian ：对于偶数阶方阵 \(A\) ，定义 \(P(A) = \sum_{M} w(M)\) ，其中 \(M\) 是完全图的完美匹配，\(w(M)\) 定义为 \(sign(M) A_{M(2i), M(2i+1)}\) 。
★ 定理 4 ：如果 \(A^T = -A\) 则 \(|A| = P(A)^2\) 。
Pfaffian Orientation ：对于无向图 \(G\) 找到带符号邻接矩阵（边定向）使得 \(w(M)\) 对于 \(G\) 内的完美匹配都相等。于是完美匹配的数量为 \(\sqrt{|A|}\) 。
★ 定理 5 ：存在 Pfaffian Orientation 当且仅当对于任意偶环 \(C\) ，如果 \(G - C\) 存在完美匹配则 \(C\) 中同一方向的边数为奇数。
★ 引理 6 ：平面图中如果定向使得每个内部的面都恰有奇数条顺时针边，则该定向即 Pfaffian Orientation 。
★ 定理 7 ：平面图一定存在 Pfaffian Orientation 。
对任一生成树任意定向后根据引理 6 确定其他边的方向即可。