Теорема Эрдёша — Галлаи (критерий Эрдёша — Галлаи) — утверждение в теории графов, задающее условие, при котором конечной последовательности натуральных чисел можно сопоставить степени вершин некоторого графа. Такие последовательности чисел называются графическими. Теорема доказана венгерскими математиками Палом Эрдёшем и в 1960 году.
Формулировка Для формулировки утверждения вводятся следующие определения: правильная последовательность — последовательность натуральных чисел длины , удовлетворяющая следующим условиям: , — чётное число; графическая последовательность чисел — последовательность целых неотрицательных чисел такая, что существует граф, последовательность степеней вершин которого совпадает с ней.
Теорема утверждает, что правильная последовательность является графической тогда и только тогда, когда для каждого , , верно неравенство:
.
Алгоритмизация Построить граф по графической последовательности можно полиномиальным алгоритмом, который строится на основании критерия Гавела — Хакими .
Примечания
Литература Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. — М.: Наука, 1990.
Э Категория:Пал Эрдёш