Vizing 定理
定义
考虑如下的问题：对一个无向图的边进行着色，要求相邻的边染不同种颜色。问
需要的最少的颜色数是多少。
解决上述问题需要借助 Vizing 定理（又称维金定理）。
在开始之前，我们先进行一些符号的规定。
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}