Ruibin_Ningh
其实也叫哈韦尔-哈基米算法 )奇怪的翻译
引入
考虑一个这样的问题:
存在一个非负整数序列 $S = (d_1, d_2, \dots, d_n)$ ，其中 $d$ 代表度数，如何判断它是否是某个简单无向图的度序列？
预备定义
可图化
我们称非负整数序列 $S = (d_1, d_2, \dots, d_n)$ 是可图化的，如果存在一个简单无向图 $G$ 及其顶点标号 $v_1, v_2, \dots, v_n$，使得每个顶点的度数满足：
$$\deg(v_i) = d_i, \quad \forall i \in \{1, 2, \dots, n\}$$
（$\forall$ 是对于任意）
Havel-Hakimi 定理
美好的假设
我们对序列 $S$ 进行排序，使 $d_1 \ge \cdots \ge d_n$
存在一个简单无向图 $G$，其度序列正好是 $S$。令度最大的顶点记为 $v_1$，则$$\deg(v_1) = d_1$$
想象一个理想条件下，我们总让 $v_1$ 优先连接到“最需要边”的顶点：也就是度数最大的那些顶点。于是 $v_1$ 与 $v_2, v_3, \dots, v_{d_1+1}$ 相连。
配合公式如下：
$$N(v_1) = \{v_2, v_3, \dots, v_{d_1+1}\}$$
这里 $N(v_1)$ 表示 $v_1$ 的邻点集合
那么处理起来就很方便了
对于这个排序后的序列 $S = (d_1, d_2, \dots, d_n)$，令：$k = d_1$
我们对 $S$ 做如下操作：
去掉第一项 $d_1$，并将紧随其后的 $k$ 项各减去 $1$。
也就是定义新序列：
$$S_1 = (d_2-1, d_3-1, \dots, d_{k+1}-1, d_{k+2}, \dots, d_n)$$
随后再将 $S_1$ 重新排序为非增序（仍记为 $S_1$），为什么是非增序而不是降序呢？
这里需要区分，降序是严格递减，非增序允许相等的情况，即有重复的数字
若在上述减 $1$ 的过程中出现负数（等价于存在 $i \in \{2, \dots, k+1\}$ 使得 $d_i = 0$），则 $S$ 不可能是简单图的度序列，否则我们得到一个长度为 $n-1$ 的非负整数序列 $S_1$
好了，这个很美好的设想听起来不错，但是我们还不能保证：
如果 $S$ 的确可图化，那么一定存在一个实现图 $G$，使得最大度顶点 $v_1$ 的邻点恰好是 $v_2, \dots, v_{k+1}$
换句话说，我们还缺少一个论证：为什么可以“总让 $v_1$ 优先连接到度数最大的那些顶点”而不丢失一般性？
这正是 Havel–Hakimi 的关键所在，核心就是“交换”二字
交换论证
我们原先的理想情况是选择一个使得
$$\sum_{u \in N(v_1)} \deg(u)$$
最大的实现，如果现实情况就是理想情况，那么得证
若不然，假设存在两个顶点 $x, y$ 满足
$x \in N(v_1)$ （$x$ 是 $v_1$ 的邻居）
$y \notin N(v_1)$ （$y$ 不是 $v_1$ 的邻居）
且 $\deg(y) > \deg(x)$
因为 $\deg(y) > \deg(x) \ge 0$，所以 $\deg(y) \ge 1$，即 $y$ 至少与某个顶点相邻
若对所有 $z \in N(y)$ 都有 $xz \in E(G)$，则 $N(y) \subseteq N(x)$，从而 $\deg(y) \le \deg(x)$，矛盾
因此存在 $z \in N(y)$ 满足 $xz \notin E(G)$
接下来比较关键了，我们构造一个新图 $G'$，并进行以下操作：
删去边 $v_1x$ 与 $yz$，并加入边 $v_1y$ 与 $xz$
绝妙地是，这个图仍然是简单图，各点的度数不变，所以这个图依然是合法的，即符合序列 $S$ ，对于每一个不符合理想情况的点，我们都可以进行这种操作构造一个新图，直到接近并成为理想情况
一些繁琐的证明就不再论述了，比如证明不会陷入循环，为什么一定能终止并到达“理想情况”
总之，对于任意序列 $S$ ，如果它可图化，一定能使得最大度顶点 $v_1$ 的邻点恰好是 $v_2, \dots, v_{k+1}$
逻辑梳理
这就是哈基米定理，这是它的正式定义
给定一个非负整数组成的非增序列 $S = (d_1, d_2, \dots, d_n)$，即满足 $d_1 \ge d_2 \ge \dots \ge d_n$。序列 $S$ 是可图化的（Graphic），当且仅当新序列：$$S' = (d_2-1, d_3-1, \dots, d_{d_1+1}-1, d_{d_1+2}, \dots, d_n)$$在经过重新排序使其满足非增性后，也是可图化的。
到这里我们梳理一下程序执行逻辑
什么，想要代码，那是不可能的
练习
P3104 [USACO14MAR] Counting Friends G - 洛谷
为什么就一题呢，因为我就因为这一题写的博客...