二分图边着色学习笔记
题解：AT_abc317_g [ABC317G] Rearranging - 洛谷专栏
图 \(G\) 的边染色，是指对于每个边涂一个颜色，要求相邻的边涂不同种颜色，记最小使用颜色数为: \(\chi(G)\)
Vizing定理：
对于简单图 \(G\)， \(\Delta(G)\le \chi(G)\le \Delta(G)+1\)，其中 \(\Delta(G)\) 表示最大度数，当 \(G\) 为二分图时取到 \(\Delta(G)\)。
二分图边着色构造算法
类似匈牙利算法，每次加入一条边 \((u,v)\) 设 \(C(u)\) 表示 \(u\) 节点已经着的色的 \(mex\)。
-
若 \(C(u)=C(v)\) 则直接将 \((u,v)\) 染成 \(C(u)\)
-
否则设 \(C(u)<C(v)\)，找到一条 \(v-u_1-v_1-u_2-v_2-\cdots\) 的链，满足 \(v_i-u_{i+1}\) 的边颜色为 \(C(u)\)，\(u_i-v_i\) 边颜色为 \(C(v)\)。可以证明链上无点 \(u\)。将这些边的颜色交换，颜色为 \(C(v)\) 的变成 \(C(u)\)，颜色为 \(C(u)\) 的变成 \(C(v)\)。最后将 \((u,v)\) 染成 \(C(u)\)。
模板题：CF600F Edge coloring of bipartite graph - 洛谷
应用：排列型匹配
有一个定理：对于任意 m-正则二分图，一定有 \(m\) 边染色，即一定有 \(m\) 组完美匹配。
AT_abc317_g [ABC317G] Rearranging - 洛谷
AT_agc037_d [AGC037D] Sorting a Grid - 洛谷
P9070 [CTS2023] 琪露诺的符卡交换 - 洛谷
最后一个太神，先用这个算法排列成每个人的第 \(i\) 张卡形成排列，在通过交换 \((i,j)\) 与 \((j,i)\) 置换矩阵，实现每个人都拥有排列：
