Теорема Эрдёша—Галлаи даёт необходимое и достаточное условие для того, чтобы последовательность неотрицательных целых чисел была последовательностью степеней простого графа.
Другими словами, она говорит нам, может ли данная последовательность встречаться как список степеней вершин в некотором графе без петель и кратных рёбер.
Пусть
— невозрастающая последовательность целых чисел.
Тогда эта последовательность является графической, то есть является последовательностью степеней некоторого простого графа, тогда и только тогда, когда:
Эта теорема даёт прямой способ проверить, является ли последовательность степеней корректной.
Первое условие естественно: в любом графе сумма всех степеней должна быть чётной, потому что каждое ребро добавляет 2 к общей степени.
Второе условие гарантирует, что наибольшие степени действительно могут быть реализованы без нарушения правил простого графа.
Чтобы проверить последовательность с помощью теоремы Эрдёша—Галлаи, можно сделать следующее:
Прямая реализация работает за время .
Можно сделать лучше, поддерживая левую и правую части неравенства при переходе от к .
Это можно реализовать с помощью массива подсчёта.
bool erdos_gallai(vector<int> d) {
int n = (int)d.size() - 1; // assume 1-indexed
vector<int> cnt(n + 1, 0);
for (int i = 1; i <= n; i++) {
cnt[d[i]]++;
}
sort(d.begin() + 1, d.end(), greater<int>());
long long sum = 0;
for (int i = 1; i <= n; i++) {
sum += d[i];
}
if (sum % 2 != 0) {
return false;
}
long long left = 0, right = 0;
int less = 0;
for (int k = 1; k <= n; k++) {
left += d[k];
less += cnt[k];
right += 1LL * k * cnt[k];
right += 1LL * k * (n - k - less);
if (left > 1LL * k * (k - 1) + right) {
return false;
}
right -= 1LL * k * (n - k - less);
if (d[k] <= k) {
right--;
less--;
}
}
return true;
}