Havel–Hakimi 算法与 Erdos-Gallai 定理
StarLbright40
·
2023-02-01 22:27:25
·
科技·工程
本文内容由 MO 佬孔明七星在水群时科普并讲解。
他和他的同学分别独自发现一个人名定理，必须狠狠拜谢。
Havel–Hakimi 算法用于判定序列是否可简单图化并给出方案。
简单图化指构造简单无向图，使 n 个点的度数与序列元素一一对应。
算法流程：
将序列从大到小排序，记为 d_{1\cdots n} 。
将 d_1 对应点与 d_2\sim d_{d_1+1} 对应点连边，删去 d_1 。
若 d_1+1>n 或 \exists d_i<0 ，报告无解并退出。
若序列为空，报告有解并将生成的图作为方案。
重复上述流程。
下面证明算法正确性。
假设存在边集 E 使得排序后序列 d_1 对应点 V_1 的连边方案不为如上，则 \exists i,j,i\le d_1+1<j 且 (V_1,V_i)\notin E,(V_1,V_j)\in E 。
设 k 使得 (V_k,V_i)\in E,(V_k,V_j)\notin E ，则可以交换边 (V_1,V_j),(V_i,V_k) 与 (V_1,V_i),(V_j,V_k) 的存在性，则归约到如上方案。
若不存在这样的 k ，即 \forall u,(V_u,V_i)\in E 有 (V_u,V_j)\in E ，又 (V_1,V_i)\notin E,(V_1,V_j)\in E ，则 d_i<d_j ，与题设矛盾。
上面证得若问题存在解则算法必能找到解，其逆否命题即为算法报告无解时问题必无解。
使用归并排序或计数排序，时间复杂度可以做到 \mathcal O(n^2) 。
若仅需判断是否有解或图稀疏，由于每次变化量仅有 1，可以用 FHQ-treap 维护序列模拟该算法达到 \mathcal O(n\log n) 的复杂度（感谢佬zhjxaoini补充）。
Erdos-Gallai 定理仅对该问题做出判定而不构造方案。它断言有序列可简单图化当且仅当序列从大到小排序后满足：
d_n\ge0,\sum\limits_{i=1}^nd_i\equiv0\pmod 2
\forall i\in[1,n],\sum\limits_{j=1}^id_j\le i(i-1)+\sum\limits_{j=i+1}^n\min(i,d_j)
第一条的必要性是显然的，对于第二条的必要性，我们考虑作为解的简单图中度数前 i 大的点，一方面它们的度数和为 \sum\limits_{j=1}^id_j ，另一方面考虑它们度数和的上界，这些点之间两两连边的贡献最大为 i(i-1) ，而对于其他点即 \forall j>i ，每个点能产生的贡献最大为 \min(i,d_j) ，故可推出第二条式子成立，即必要性得证。
接下来证明充分性。记 s=\sum\limits_{i=1}^nd_i ，当 s=0 时显然成立。于是考虑数学归纳法，证明当 s=2k 命题成立时 s=2(k+1) 命题仍成立。
不妨删去序列末尾的 0 ，显然这对证明没有影响。设有满足 s=2(k+1) 的序列 d 满足如上式子，记最小的 p 满足 d_p>d_{p+1} ，若不存在则记 p=n-1 ，并令 d_p\gets d_p-1,d_n\gets d_n-1 ，这可以视作连边 (j,n) ，记得到的新序列为 d' 。显然 d' 仍是有序的且满足第一条，下面证明 d' 满足第二条。
当 i=n 时，式子显然成立。当 p\le i<n 时，式子左端减少 1 ，右端仅在和号中的 j=n 时减少至多 1 ，故仍成立。
当 i<p 时，我们需要再对 d_i 的值进行分类讨论，实际上由于 p 的定义，这个值与所有 d_{1\cdots p} 都相等：
第二条式子通过维护 \min 号取值的分界，即在循环 i 时记录最小的 j 满足 d_j<i ，可以做到判断复杂度 \mathcal O(n) 。由于显然值域与点数同阶，用计数排序即可做到 \mathcal O(n) 判断序列是否可简单图化。依照对充分性的证明也可以实现构造方案，但复杂度达到 \mathcal O(nm) 一般更劣。