首页 > 其他分享 >杂题选讲 #1:二分图边着色

杂题选讲 #1:二分图边着色

时间:2024-06-12 12:43:42浏览次数:24  
标签:二分 图边 le 颜色 chi 选讲 着色 Delta 杂题

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 它才逐渐变得广为人知。该类型的练习题较少,这里有两道可供参考:

参考资料:

标签:二分,图边,le,颜色,chi,选讲,着色,Delta,杂题
From: https://www.cnblogs.com/physics212303/p/18243713

相关文章

  • 「杂题乱刷」AT_abc154_e
    代码恢复训练2024.6.10.(补)链接(luogu)链接(atcoder)数位dp板子题。dfs(last,sum,_1)剩下未搜的数位数,当前非零数位数,目前是否取满。这里采用记搜的写法。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换......
  • 「杂题乱刷」AT_abc132_e
    代码恢复训练2024.6.11.链接(luogu)链接(atcoder)分层图板子。结束。代码:点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打cf不要用umap!!!记住,rating是身外之物。该冲正解时冲正解!Problem:算......
  • 一般图边覆盖计数(从洛谷博客同步)
    今天模拟赛中出现了一个题,需要对一个\(n\)个点,\(m\)条边的图做边覆盖计数,边覆盖是一个边集\(S\subseteqE\)使得任意一个点\(i\)都存在一条边\((u,v)\inE\)满足\(u=i\)或\(v=i\),即覆盖所有的点。\(n\leq40,m\leq60\),1s512M。然后被我使用神秘做法冲过去了(然后莫......
  • 「杂题乱刷」AT_abc357_f
    代码恢复训练2024.6.8.题目链接链接(atcoder)链接(luogu)解题思路数据结构板子题。设\(ans_i=a_i\timesb_i\)(\(a_i\)和\(b_i\)是此时的\(a_i,b_i\))。设\(f1(i,j)\)表示\(a_i+a_{i+1}+a_{i+2}+\dots+a_j\)的值。设\(f2(i,j)\)表示\(b_i+b_{i+......
  • 「杂题乱刷」AT_abc160_e
    代码康复训练2024.6.7无所谓,随便贪。直接取前\(x\)大的红苹果,前\(y\)大的绿苹果和和所有无色苹果合起来取最大的\(x+y\)个苹果的值加起来即可。容易证明一定合法。代码:点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出......
  • 「杂题乱刷」CF1979C
    代码恢复训练2024.6.7.题目链接CF1979C(codeforces)CF1979C(luogu)解题思路我们发现,如果答案序列的和小于等于\(x\)时是合法的,那么容易得出答案序列的和小于等于\(x+1\)时也是合法的。因此我们发现答案序列的和的合法性是具有单调性的。直接二分即可,答案中的每个......
  • 6月杂题
    CF1943D2CountingIsFun(HardVersion)......
  • 「杂题乱刷」AT_abc126_e
    代码康复训练2024.6.6.链接并查集板子。直接看代码。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打cf不要用umap!!!记住,rating是身外之物。该冲正解时冲正解!Problem:算法:思路:*/#include<b......
  • 「杂题乱刷」AT_abc179_e
    代码恢复2024.6.5。链接很简单。直接找循环节就行了。代码:点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打cf不要用umap!!!记住,rating是身外之物。该冲正解时冲正解!Problem:算法:思路:*/#inc......
  • 6月杂题
    1.qoj8003Anti-Plagiarism不难想到dp,即\(dp_{x,a,b}\)表示第一棵树以\(x\)为根的子树能否和第二棵树中以\(a\)为根时\(b\)的子树匹配,其中\(a,b\)相邻。想想怎么转移,就是把子树的dp值算出来,然后对于\(x\),枚举一对\(a,b\),发现这里其实就是二分图匹配:右边的点是......