Gale-Ryser 定理

给定两个非负整数数列 \(p_1 \ge p_2 \ge \dots \ge p_n\) 以及 \(q_1 \ge q_2 \ge \dots \ge q_m\) 满足 \(\sum_{i = 1}^n p_i = \sum_{i = 1}^m q_i\)，存在一个简单二分图使得左部点的度数分别为 \(p_1, p_2, \dots, p_n\)、右部点的度数分别为 \(q_1, q_2, \dots, q_m\) 的充要条件为 \(\forall k \in [1, n], \sum_{i = 1}^k p_i \le \sum_{i = 1}^m \min\{q_i, k\}\)。

必要性

记该二分图的左部点为 \(x_1, x_2, \dots, x_n\)、右部点为 \(y_1, y_2, \dots, y_m\)，不妨设 \(\forall i \in [1, n], deg(x_i) = p_i, \forall i \in [1, m], deg(y_i) = q_i\)。

对于左部的任意 \(k\) 个点，考察它们的度数之和。对于每一个右部点 \(y_i\)，它最多和左部的 \(k\) 个点中的 \(\min\{q_i, k\}\) 个有边相连。因此左部任意的 \(k\) 个点度数之和 \(\le \sum_{i = 1}^m \min\{q_i, k\}\)。

所以 \(\forall k \in [1, n], \sum_{i = 1}^k p_i \le \sum_{i = 1}^m \min\{q_i, k\}\)。

充分性

考虑归纳构造出该二分图。

若我们已经构造出一个简单二分图满足 \(deg(x_k) < p_k, \forall i \in [1, k - 1], deg(x_i) = p_i, \forall i \in [k + 1, n], deg(x_i) = 0, \forall i \in [1, m], deg(y_i) \le q_i\)，考虑如何添加或修改若干条边使得 \(deg(x_k) \leftarrow deg(x_k) + 1\)，且除了 \(deg(x_k) < p_k\) 以外的所有条件仍然满足。

我们必然能找到一个 \(y_a\) 使得 \(deg(y_a) < \min\{q_a, k\}\)，否则 \(\sum_{i = 1}^k p_i > deg(x_k) + \sum_{i = 1}^{k - 1} p_i = \sum_{i = 1}^m deg(y_i) = \sum_{i = 1}^m \min\{q_i, k\}\)，矛盾。

如果还没有边 \((x_k, y_a)\)，则加入该边。

否则根据抽屉原理，必然存在 \(b \in [1, k - 1]\) 使得没有边 \((x_b, y_a)\)。又因为 \(deg(x_b) = p_b \ge p_k > deg(x_k)\)，所以一定存在 \(y_c\) 使得有边 \((x_b, y_c)\)、没有边 \((x_k, y_c)\)。删去边 \((x_b, y_c)\)，加入边 \((x_b, y_a), (x_k, y_c)\)。

不难发现上述操作是使得 \(deg(x_k) \leftarrow deg(x_k) + 1\) 的一个合法构造。

初始 \(k = 1\)，当 \(deg(x_k) < p_k\) 时不断调用上述构造，然后令 \(k \leftarrow k + 1\)。此时若 \(k = n + 1\) 则我们已经构造出一个满足条件的二分图。

容易发现上述充分性的构造实际上是在模拟网络流的增广路算法。