烂完了。

Lecture 1

懂得都懂。

正度 $d^+$: 出度，负度 $d^-$: 入度。

Lecture 2

生成子图/支撑子图：所有点，部分边；
导出子图：部分点。

$\Gamma(v)$ 是邻域，正负和上面相同。

关联矩阵：$(x, y)\in E, w_{x, y} = 1, w_{y, x} = -1$.

简单路径：无重边，初级路径：无重边、无重点。

每点度数至少是 $3$，则存在带弦环。

取极长的一条道路即可。

有向图的连通性：视作无向图的连通性。

没有割点的极大连通子图：块。

Lecture 3

Hamilton

任意两点 $d(u)+d(v)\ge n-1$，则存在 Hamilton 道路。

取极长道路，若长度 $l<n$，$(1, p), (p-1,l)$ 给出了极长道路导出的一个回路，存在性由度数和保证。然后再多接一个点到环上就可以完成拓展。

任意两点 $d(u)+d(v)\ge n$，则存在 Hamilton 回路。

先用上面的，然后最后一步回路的存在性由度数和保证。

若任意一点 $d(u)\ge \frac{n}{2}$，则存在 Hamilton 回路。

例题：$n(>2)$ 个人中任意两个人能认识其他 $n-2$ 个人。在 $i, j$ 不认识的时候，证明其他人必然同时认识 $i, j$，于是存在 Hamilton 道路。

若 $(v_i, v_j)$ 不相邻，但 $d(v_i)+d(v_j)\ge n$，则图中是否加入 $(v_i, v_j)$ 对 Hamilton 回路的存在性等价。

Proof: 如果 $G+(v_i,v_j)$ 中不包含 $(v_i,v_j)$，成立；如果包含，断掉该边后可以再找出一个环，这由度数和保证。

闭合图：不断加入满足上述条件的边。闭合图是唯一的。

简单图存在 Hamilton 回路等价于其闭合图存在 Hamilton 回路。

旅行商问题

旅行商问题：正权完全图上最小权 Hamilton 回路。

分支定界法：边权排序，带剪枝地搜；

便宜法：从任意一个点开始，一开始是自环，找一个和环“最近”的（看边权），如果是 $k$，和 $t$ 最近，$t$ 分别连向 $t_1, t_2$，找使得环长增量较小的一边加进去。可以得到最优解 $2$ 倍内的解。

Lecture 4

Ford: 重复执行以下操作：从 $2\to n$ 枚举，用前驱节点松弛。

不存在负权环的话，至多 $n-1$ 轮就结束了。

关键路径

关键路径：正权 DAG。$\pi(i)$：源点到当前点的最长路径（当前工序最早的启动时间），关键路径就是取到 $\max$ 的路径，不能延误。

$\tau(i)$：最晚完工时间，反过来推就行。$\tau(i, j)$：工序最晚启动时间：

$$ \tau(i,j)=\tau(j)-w(i,j) $$

最大允许延误时间：

$$ \Delta(i, j)=\tau(i, j)-\pi(i) $$

中国邮路

中国邮路：正权联通图中，经过每条边至少一次再返回出发点的最短回路。

G 存在欧拉回路 $\to$ 取欧拉回路；
G 有两个点 $a, b$ 度数为奇数: $a$ 到 $b$ 的最短路 + 某一条 $a$ 到 $b$ 的欧拉道路。

"$L$ 是最佳邮路" 当且仅当 "$L$ 中每条边至多重复一次 + $G$ 的任意回路上重复边的长度之和不超过回路长度的一半"

Proof:

其实就等价于给一些重边，使得新图有欧拉回路。

$\to$

如果超过一次，可以去掉偶数次，仍然保留欧拉回路。
如果某个环上长度和超过了一半，换成环上另外那些边会更优。

$\leftarrow$

设 $L_1, L_2$ 满足条件，证明他们权值相等。

取对称差，这是重复的边的子集，构成若干个环。由第二个条件，可以得到互相 $\le$，从而权值相等。

构造中国邮路：先随便取重复的边集，然后枚举环看要不要 flip。

Lecture 5

支撑树：生成树。

有向联通图关联矩阵的 $\operatorname{rank}=n-1$。

Proof: 考虑需要的最少行使得线性相关。如果 $<n$，把这些行，和在这些行非零的列挪到左上角，可以看出得到两个联通分支，与联通矛盾。

基本关联矩阵：删掉某一行（代表某个节点）的 $\operatorname{rank}=n-1$。

树的基本关联矩阵（方阵）满秩。

$G$ 的基本关联矩阵 $B_k$ 的 $n-1$ 阶子式行列式非零等价于这些列构成一棵生成树。
基本关联矩阵 $B_k$ 的 $m$ 阶子式行列式是 $0,1,-1$。

存在一列全 $0$：$0$;
任意列都有两个非零，线性相关，$0$;
存在一列只有一个非 $0$，按这列展开，归纳。

Matrix-Tree: 生成树个数 $=\det (B_k B_k^T)$ （注意转置在后面）

根树：外向树。

$\hat{B_k}$ 是把 $B_k$ 中所有 $1$ 改成 $0$ 后的矩阵，那么根树/外向树个数 $=\det(\hat{B_k} B_k^T)$。

${B_k}^T$ 的部分负责树，$\hat{B_k}$ 的部分负责外向树。

Lecture 6

回路矩阵

完全回路矩阵 $C_e$：全部初级回路，$C_{i,j}$ 表示第 $i$ 个环里 $e_j$ 是否在、是否同向（给一个定向）

基本回路：选定生成树后，每条余树边给出一个基本回路。基本回路的方向规定为余树边的方向。

基本回路矩阵 $C_f$ 是 $(m-n+1)\times m$ 的矩阵，且 $\operatorname{rank}(C_f) = m - n + 1$。

Sylvester: $A\in M_{n,s}, B\in M_{s,m}, AB=0$，则 $\operatorname{rank}(A)+\operatorname{rank}(B)\le s$。

$$ BC_e^T = BC_f^T =0 $$

可以设 $C_f = (I, C_{f_{12}})$，$C_{f_{12}}$ 表示树边的情况。此时如果 $B_k=(B_1, B_2)$，则有：

$$ C_{f_{12}} = -B_1^T B_2^{-T} $$

回路矩阵：线性无关的 $m-n+1$ 个回路组成的矩阵 $C$。于是有 $C=PC_f$，其中 $P$ 可逆。

回路矩阵 $C$ 的一个 $m-n+1$ 阶子式行列式非零，当且仅当这些列对应 $G$ 的一棵余树（剩下部分是树）

割集矩阵

割集：极小的，使得连通块变多的边的子集。可以给割集中每条边定义方向，从而可以定义完全割集矩阵 $S_e$。

基本割集：确定生成树后任选一条树边，加上必须的那些非树边。

基本割集矩阵 $S_f$：$\operatorname{rank}(S_f)=n-1$。

$S_e C_e^T=0$

因为割集和回路重复的边数是偶数。

割集矩阵：线性无关的 $n-1$ 个割集组成的矩阵 $S$。于是 $S=PS_f$，其中 $P$ 可逆。

Huffman 树

最优长度二进制编码。

最短树

你是否想搜：最小生成树

Kruskal

按边权从小到大能加就加。

线性建堆的话，复杂度是 $\mathcal{O}(m+p\log m)$，其中 $p$ 是迭代次数。

Prim

不断扩展距离已扩展节点最近的节点。

Lecture 7

欧拉定理：对平面联通图 $G$，$n-m+d=2$，$n,m,d$ 分别是点、边、面（区域）

Proof: 从生成树不断加边。

还有：$n-m+d=k+1$，$k$ 是连通块个数。

若平面图没有割边，切每个域边界数至少为 $t$，则 $m\le \dfrac{t(n-2)}{t-2}$

Proof: $t\times d\le 2m$，则 $2-n+m=d\le \frac{2m}{t}$

极大平面图：$m=3n-6, d=2n-4$。

平面图不含 $K_3$，则 $m\le 2n-4$。
简单平面图 $G$ 中有度数 $< 6$ 的节点。（所以直接得到 $K_7$ 不是平面图）
$G$ 是平面图，当且仅当缩掉二度点后没有 $K_5,K_{3,3}$ 子图。

对偶图 $G^*$ 是连通图。

若 $G$ 是平面联通图，则 $(G^*)^*=G$。
$G$ 的初级回路对应 $G^*$ 的一个割集。
$G$ 有对偶图，当且仅当 $G$ 是平面图。
平面图可面 $5-$ 染色。

Proof: 转成对偶图的点 $5-$ 染色。使用平面图存在 $d(v)\le 5$，删掉该点做归纳。利用五个点中平面图上相邻的两个，构造一个闭环，然后说明可以翻转一些点的颜色。

若平面图有 Hamilton 回路，则四色猜想成立。
若 $3-$ 正则平面图的平面都可 $4-$ 染色，那么任意图都可以。

这就是经典三度化。

Lecture 8

最大匹配

匈牙利。

完全/完美匹配

完全匹配：匹配数为 $|X|$.

完美匹配：匹配数为 $|X| = |Y|$.

Hall 定理：$(X,Y,E)$，存在 $X$ 到 $Y$ 的完全匹配，等价于任意 $X$ 的子集 $A$ 有 $|\Gamma(A)|\ge |A|$。

$\leftarrow$，考虑未匹配点 $x_0$ 能涉及到的所有右部点，然后构造集合，根据这些右部点和他们匹配的左部点的唯一性得到矛盾。

取：

$$ \delta(G)=\max (|A| - |\Gamma(A)|) $$

$A$ 是 $X$ 的子集。于是 $X$ 到 $Y$ 的最大匹配是 $|X| - \delta(G)$.

最大匹配 = 最小覆盖。

最佳匹配

KM。

Lecture 9

网络流图：有向联通图（无自环），一个源一个汇

割切：点集 $S$，$s\in S, t\notin S$，那么所有有向边 $(i, j), i\in S, j\notin S$，是一个割切 $(S, \bar{S})$。

最大流 = 最小割切的容量。

【学习笔记】离散数学（2）速通