Vizing 定理
定义
考虑如下的问题：对一个无向图的边进行着色，要求相邻的边染不同种颜色。问
需要的最少的颜色数是多少。
解决上述问题需要借助 Vizing 定理（又称维金定理）。
在开始之前，我们先进行一些符号的规定。
- \(\Delta(G)\)：无向图 \(G=(V,E)\) 的最大度数，即 \(\Delta(G)=\max_{i\in V}\deg i\)；
- \(\chi(G)\)：若无向图 \(G\) 是 \(k\) - 边可着色的，但不是 \((k-1)\) - 边可着色的，则称 \(\chi(G)\) 为 \(G\) 的边色数，记为 \(\chi(G)\)。
Vizing 定理的内容如下：
- 对于简单无向图 \(G\)，有 \(\Delta(G)\le\chi(G)\le\Delta(G)+1\)；
- 特别地，对于二分图 \(G\)，有 \(\Delta(G)=\chi(G)\)。
我们今天仅讨论后者的情况，即二分图的边着色。
证明
二分图上的 Vizing 定理为什么是正确的？
首先，必要性是显然的——不可能用比某个点的度数还少的颜
色数完成着色。
至于充分性，使用构造性证明。考虑执行如下算法：
对于二分图 \(G=(V,E)\)，按顺序在二分图中加边。
加入一条边 \((u,v)\) 时，尝试寻找对于 \(u\) 和 \(v\) 的编号最小且未使用过的颜色（你可以理解为 \(\mathrm{mex}\)），设为 \(A\) 和 \(B\)。
如果 \(A=B\)，那么直接将这条边染上 \(A\)。
否则令 \(A<B\)，尝试将连接 \(v\) 的颜色为 \(A\) 的边的颜色强制改为 \(B\)。
这样可能还会产生矛盾，假设这条边连接的另一个结点（设为 \(w\)）上产生了矛盾，就把连接 \(w\) 的颜色为 \(B\) 的边的颜色再强制改为 \(A\)……
我们发现这是一个不断寻找增广路并对路径上的边交替染色的过程。
由于二分图不存在奇环，所以结点 \(u\) 不可能在增广路上，否则会与“最小未使用颜色为 \(A\)”矛盾。
时间复杂度 \(O(nm)\)，其中 \(n=|V|\)，\(m=|E|\)。
模板题 CF600F
题意简述
构造出一组二分图边着色方案使得使用的颜色数最少。
数据范围：\(1\le n_1,n_2\le 1000\)，\(1\le m\le 10^5\)
题目信息
来源：Codeforces
难度：\(\color{Red}\texttt{*2800}\)
正解
解法：完完全全的模板。实现时可以将其封装成一个类。
参考代码（C++17）：
Submission #247875843 - Codeforces
[SNOI2024] 拉丁方
题意简述
定义一个 \(n \times n\) 的矩阵 \(A\) 为拉丁方，当且仅当每行每列都是一个 \(1 \sim n\) 的排列。
给定一个矩阵 \(A\) 左上角的一个 \(R \times C\) 的子矩阵，也就是 \(A_{i, j}\)（\(1 \le i \le R\)，\(1 \le j \le C\)）。问能不能将剩下的位置填上数使得它是一个拉丁方。如果可以，构造出任意一组合法方案。
数据范围：多测，\(1\le T\le 5\)，\(1\le R,C\le n\le 500\)，输入的子矩阵不存在一行或者一列有两个相同的数。
题目信息
来源：陕西省 NOI 省队选拔赛 2024 D1T3
难度：\(\color{Darkblue}\texttt{NOI/NOI+/CTSC}\)
特殊性质 B：\(C=n\)。
解法：从特殊性质 B 出发，可以观察到在这种情况下每一列要填哪些值都知道了，但是不知道每个值要填在哪一行。
于是考虑建出二分图，由未使用的值向列连边；因为要求同一行不能有相同的值，所以直接跑二分图边染色。
最终每条边的颜色即为该值在该列的行数。
可以证明这种情况下一定有解：此时对于每种颜色所有边构成了一组完美匹配。
正解
那么如何将上述做法扩展到 \(C\) 任意的情况？
考虑把原矩阵“补”成一个 \(C=n\) 的矩阵（就是把右上角那一块填上）再运用上述算法。仍然使用上面的做法，这次由值向行连边，然后每条边的颜色就是其所在的列。注意如果使用的颜色数 \(p\ne n-C\)（此时有点度数大于 \(n-C\)）那么无解。
温馨提示：这题时限 5s，如果你还卡不过去，那么请把 int 换成 short。
参考代码（C++17）：
提交记录 #335745 - QOJ.ac
练习题 & 总结
Vizing 定理算是一个比较冷门的知识点，直到 SNOI2024 它才逐渐变得广为人知。该类型的练习题较少，这里有两道可供参考：
- UVa10615 Rooks
- AtCoder AGC037D Sorting a Grid
参考资料：
- 图的着色 - OI Wiki
- 本人题解：[SNOI2024] 拉丁方 题解 by \(\color{Red}\mathrm{FFTotoro}\)
