二分图边染色

xlpg0713 · 2024-10-09 15:14:19 · 个人记录

无向图的边染色

对无向图 G 边着色，使得相邻的边颜色不同。

若无向图是 k 边可着色的，但不是 k-1 边可着色的，称 k 为 G 的边色数，记为 \chi'(G)。

Vizing 定理

对于任意简单图 G，有 \Delta(G)\le\chi'(G)\le\Delta(G)+1。

求解简单图的边染色是 NP-hard 的。一般只考虑二分图的边染色。感兴趣的可以尝试证明上述定理。

二分图的边染色

对于二分图 G，一定有 \Delta(G)=\chi'(G)。

在此给出的是构造性证明，考虑在动态加边的过程中维护边染色。

加入边 (x,y) 时，找到 x,y 联通的边集中颜色的 \operatorname{mex} 为 a_x,a_y。注意到一定有 a_x,a_y\le\Delta(G)。

若 a_x=a_y，将 (x,y) 的颜色设为 a_x。

否则，不妨假设 a_x<a_y，x 属于左部点，从 y 开始找到一条颜色为 a_x,a_y 交替的增广路。

注意到如果 x 在找到的增广路中，那么 x 与右部点有一条颜色为 a_x 的边，这与 a_x 的定义相悖。

故我们一定可以找到这样的一条增广路使之不包含 x，于是我们可以将增广路上的 a_x 和 a_y 互换，然后将 (x,y) 的边色设为 a_x。

证毕。

求解二分图的边染色可以按上面的方式进行，注意到增广路的长度为 O(n)，一共有 m 条边，故求解二分图边染色的复杂度为 O(nm)。

例题

[CF600F] Edge coloring of bipartite graph

真.模板题。提供一份参考实现。

#include<iostream>
const int N = 2e3+10, M = 1e5+10;
int a, b, m, rs, c1, c2, c[N][N], u[M], v[M], d[N];
int main(){
    std::cin >> a >> b >> m; for(int i = 1; i <= m; i++)
        std::cin >> u[i] >> v[i], v[i] += a, ++d[u[i]], ++d[v[i]];
    for(int i = 1; i <= a+b; i++) rs = std::max(rs, d[i]);
    for(int i = 1; c1=1, c2=1, i<=m; i++){
        while(c[u[i]][c1]) c1++; while(c[v[i]][c2]) c2++;
        c[u[i]][c1] = v[i], c[v[i]][c2] = u[i]; if(c1==c2) continue;
        for(int t=c2,w=v[i]; w; w=c[w][t],t^=c1^c2) std::swap(c[w][c1], c[w][c2]);
    }
    std::cout << rs << '\n';
    for(int i = 1; i <= m; i++) for(int j = 1; j <= rs; j++)
        if(c[u[i]][j] == v[i]) std::cout << j << ' ';
}

[AGC037D] Sorting a Grid

给定一个 n\times m 的矩阵 A , 保证 A 内的元素为 1 到 n\times m 的排列.

将 A 每一行的元素任意排列得到 B。

将 B 每一列的元素任意排列得到 C。

将 C 每一行的元素任意排列得到 D。

要求 D_{i,j}=(i-1)\times m+j , 请输出一组合法的 B, C。

注意到 C 的一行是 D 的一行的排列，B 的一列是 C 的一列的排列。所以 B 的一列不会同时出现 D 中一行的元素。

因此第一次操作只需要给每个元素定一个列，使得每列不会出现同行的元素。易于发现这样一定合法。

建出左右都有 n 个点的二分图，若某个在第 x 行的元素应当在第 y 行，由左部点的 x 连向右部点的 y。

对该图做二分图边染色，颜色相同的边在 B 的同一列中。

复杂度与二分图边染色一致。

P9070 [CTS2023] 琪露诺的符卡交换

给定 n\times n 的矩阵，满足 [1,n] 中每个元素恰好出现 n 次，用若干次不相交的对换使得每行是一个 [1,n] 的排列。

注意到“不相交的”没有用，如果某一状态经过置换 f,g 的先后作用后合法，那么经过 g\circ f 作用后也合法。

考察如果矩阵的每一列都是一个排列，那么转置一定合法。考察其共轭类 p^{-1}\circ t\circ p。任意选取 p 不可取，不妨限定 p 为每行置换的合成，行之间不影响。

发现这样等价于让原矩阵在 p 作用后每列是一个排列。

于是建图，左部点 n 个表示行，右部点 n 个表示元素，每行向其元素连边。需要边元素划分成若干匹配。

然后你发现每个点的度数都是 n，所以直接做一遍二分图染色，同种颜色的边在一个匹配里。

P10062 [SNOI2024] 拉丁方

给定 n\times n 矩阵左上角一个 r\times c 的子矩形，元素在 [1,n] 中。补全其使得每一行每一列都是一个排列。保证给出的子矩形合法。

考虑 r=n，此时每行元素确定，同时要求每列元素为一个排列。可以套用上一道题的做法。考察每个点的度数不难发现他一定合法。

现在考虑 r\ne n，先填矩阵左下角的部分将其补全为 r=n，方法一样。我们总能发现这样的方法构造出的一定合法。

CF212A Privatization

给定二分图 G，将边染为 [1,k] 中的一种颜色，最小化经过一个点的边不同颜色数量的极差的和。

答案的一个显然下界为 \sum\limits_{v}[k\nmid deg_v]。这等价于可以将一个点相邻的边集拆成若干个大小为 k 的集合和一个小于 t 的集合，集合内部的边颜色不同。

将一个点拆为 \lceil\frac{deg_x}{k}\rceil 个点，给每个点分配不超过 k 条边，即度数小于等于 k，故一定能找到一个合法的染色方案。

CF1240F Football

有 n 支球队，k 个球场，m 场比赛。第 i 场由 a_i 和 b_i 两支球队踢。你可以任意指定一场球赛在那个球场踢。

如果第 i 支球队踢了 j 场比赛，可以获得 w_i\times j 的收益。在满足：一支球队在不同场馆参加球赛次数的极差不超过 2 为前提，最大化收益之和。

注意到在上一道题构造的方案中，每个点的答案不超过 1，于是我们把每个点拆成左右部的两个点，对于一条边 u,v，我们钦定其由左部点的 u 连向右部点的 v，然后跑一遍上面那个题，把左右部点合并。

uoj444 二分图

给定二分图的左右部点集，动态加边删边维护 CF212A 那道题的方案。

不难发现问题在于处理删边，发现删除最后一条和这个点相连的边一定合法，于是我们每次删边将当前边的边集与相连通的最后一条边互换即可。

CF547D Mike and Fish

给定 n 个整点。你要给每个点染成红色或蓝色。要求同一水平线或垂直线上两种颜色的数量最多相差 1。

把点视作边，一个点 (x,y) 是左部点的 x 向右部点的 y 连边，那么就是 CF212A 的 k=2。

考虑如果能找到一个欧拉回路，对回路上的边黑白染色不会让极差增大。所以如果每个点的度数都是偶数，可以很容易的构造。

现在考虑有的点度数为奇数，建立虚点向所有度数为奇数的点连边。注意到无向图的度数和为偶数，所以只有偶数个度数为奇数的点，虚点的度数也为偶数，跑一边欧拉回路构造即可。

CF1499G Graph Coloring

在 CF547D 的条件下动态加边维护染色方案。

我们维护颜色交替出现的，极长的路径/欧拉回路的集合。

考虑对于一条路径，如果加一条边后可以成为环，因为这是个二分图，所以一定是偶环。

“经过一个点的边颜色极差不超过 2”，这等价于每个点至多可以作为一条非回路的路径的端点。所以如果出现这样的情况就需要合并两条路径。

加入一条边 (x,y)：