Рассматриваем простые неориентированные графы (без петель и кратных рёбер). Пусть дана не возрастающая последовательность неотрицательных целых чисел $d=(d_1\ge d_2\ge \dots \ge d_n)$. Вопрос: когда существует граф с этой степенной последовательностью?
Критерии (кратко)
- Необходимое условие: сумма степеней чётна: ${\sum }_{i=1}^n{d}_i$ — должно быть чётным, и каждый $d_i\le n-1$.
- Теорема Эрдёша—Галлая (эквивалентный жёсткий критерий): последовательность $d$ графическая тогда и только тогда, когда ${\sum }_{i=1}^n{d}_i$ чётно и для всех $k=1,2,\dots ,n$ выполнено
$$\sum _{i=1}^k{d}_i\le k(k-1)+\sum _{i=k+1}^n\min (d_i,k).$$ - Критерий Хавела—Хакими (процедурный): последовательность графическая тогда и только тогда, когда итеративная редукция заканчивается нулевой последовательностью (и на промежутке не возникает отрицательных чисел).
Алгоритм Хавела—Хакими (процедура)
1. Отсортировать $d$ по невозрастанию.
2. Если все члены равны $0$, то последовательность графическая (строим граф по накопленным связям).
3. Если любой член отрицателен или первый член $d_1$ больше числа оставшихся вершин $(d_1>n-1)$ или сумма степеней нечётна — не графическая.
4. Иначе удалить первый элемент $d_1$ и вычесть $1$ из следующих $d_1$ элементов (т.е. предполагаем, что вершина с этой степенью соединена с $d_1$ вершинами с наибольшими степенями). Повторить с полученной последовательностью (снова отсортировав её).
Пример 1 — графическая последовательность
Возьмём
$$d=(3,3,2,2,2).$$ Шаги Хавела—Хакими:
- Удаляем $3$ и вычитаем $1$ из следующих трёх: остаётся $(2,1,1,2)$. Отсортируем: $(2,2,1,1)$.
- Удаляем $2$ и вычитаем $1$ из следующих двух: остаётся $(1,0,1)$. Отсортируем: $(1,1,0)$.
- Удаляем $1$ и вычитаем $1$ из следующего одного: остаётся $(0,0)$.
- Все нули ⇒ последовательность графическая.
Можно одновременно строить граф: вершины $v_1,\dots ,v_5$ с начальными степенями как в $d$.
- Связать $v_1$ с $v_2,v_3,v_4$.
- Затем связать следующую вершину с остаточной степенью $2$ (например, $v_2$) с $v_5$ и $v_3$.
- Затем связать оставшиеся пары — в итоге рёбра: $(v_1,v_2),(v_1,v_3),(v_1,v_4),(v_2,v_5),(v_2,v_3),(v_4,v_5)$.
Пример 2 — не графическая последовательность
Возьмём
$$d=(3,3,3,1).$$ Шаги:
- Удаляем $3$, вычитаем $1$ из следующих трёх: остаётся $(2,2,0)$.
- Удаляем $2$, вычитаем $1$ из следующих двух: остаётся $(1,-1)$ — появилось отрицательное число ⇒ последовательность не графическая.
Заключение
- Используйте сначала проверку на чётность суммы и условие $d_i\le n-1$ (быстрая фильтрация).
- Для окончательного ответа применяйте либо неравенства Эрдёша—Галлая, либо алгоритм Хавела—Хакими (последний удобен на практике и конструктивен — даёт способ построить граф при успехе).