Havel-Hakimi & Erdős-Gallai 定理

· · 算法·理论

用于判定无向图的度数序列是否可简单图化。简单图化的意思是,存在一个 n 个点的简单无向图,使得节点 i 的度数为 d_i。

Havel-Hakimi 定理

考虑度数序列 d_1,d_2,\cdots,d_n。将其降序排序后删去 d_1,并令 d_i \gets d_i-1。如果新序列可简单图化,则原序列也可简单图化。

Erdős-Gallai 定理

考虑降序排序的度数序列 d_1,d_2,\cdots,d_n,其可简单图化当且仅当满足以下两个条件:

CF1091E New Year and the Acquaintance Estimation

给出一个长为 n 的序列 d_1 \sim d_{n}。求所有可能的 d_{n+1},使得 d_1 \sim d_{n+1} 可以构成无向图的度数序列。

:::::success[题解]

枚举 d_{n+1} 并利用 Erdős-Gallai 判定,可以做到 O(n^2) 的复杂度。具体地,我们顺次扫描 k,并维护指针 p 表示 d_p \ge k 且最大的 p。则 \sum \limits_{i=k+1}^n \min(d_i,k) 可以分成两个部分单独计算。

实际上,定理的成立性关于 d_{n+1} 单调。具体地,当 \sum \limits_{i=1}^k d_i 超过右式时,可以调大 d_{n+1} 使得右式增大,也可以调小 d_{n+1} 使得左式减小。

如果固定调整方向,就可以用二分求出答案的上下界。

根据定理成立的第一个条件,我们可以得到 d_{n+1} 的奇偶性。找到上下界后直接输出一段连续区间即可。

复杂度 O(n\log^2 n),精细实现可以做到 O(n \log n)。

:::::info[代码]

const int N = 5e5 + 5;
int n, a[N], b[N];
i64 s[N];

int check(int x) {
    copy(a + 1, a + n + 1, b + 1), b[n + 1] = x;
    sort(b + 1, b + n + 2, greater<int>());
    for (int i = 1; i <= n + 1; i++) s[i] = s[i - 1] + b[i];
    int p = n + 1;
    for (int k = 1; k <= n + 1; k++) {
        while (p > 0 && b[p] < k) p--;
        i64 v = 1LL * k * (k - 1) + 1LL * k * (max(k, p) - k) + s[n + 1] - s[max(k, p)];
        if (s[k] > v) return x >= b[k] ? 1 : -1;
    } return 0;
}

void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int p = accumulate(a + 1, a + n + 1, 0LL) & 1;
    int lo = 0, hi = -1;
    for (int l = 0, r = (n - p) / 2; l <= r; ) {
        int mid = (l + r) >> 1;
        if (check(2 * mid + p) >= 0) lo = mid, r = mid - 1;
        else l = mid + 1;
    }
    for (int l = 0, r = (n - p) / 2; l <= r; ) {
        int mid = (l + r) >> 1;
        if (check(2 * mid + p) <= 0) hi = mid, l = mid + 1;
        else r = mid - 1;
    }
    if (lo > hi) cout << -1;
    else for (int i = lo; i <= hi; i++) cout << 2 * i + p << ' ';
} 

:::::