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):
练习题 & 总结
Vizing 定理算是一个比较冷门的知识点,直到 SNOI2024 它才逐渐变得广为人知。该类型的练习题较少,这里有两道可供参考:
参考资料:
标签:二分,图边,le,颜色,chi,选讲,着色,Delta,杂题 From: https://www.cnblogs.com/physics212303/p/18243713