Теорема Эрдёша — Галлаи ( критерий Эрдёша — Галлаи ) — утверждение в теории графов , задающее условие, при котором конечной последовательности натуральных чисел можно сопоставить степени вершин некоторого графа . Такие последовательности чисел называются графическими. Теорема доказана венгерскими математиками Палом Эрдёшем и ( венг. ) в 1960 году .

Формулировка

Для формулировки утверждения вводятся следующие определения:

• правильная последовательность — последовательность натуральных чисел длины ${\displaystyle n}$ , удовлетворяющая следующим условиям:
  1. ${\displaystyle n-1\geq d_{1}\geq d_{2}\geq \ldots \geq d_{n}}$ ,
  2. ${\displaystyle \sum _{i=1}^{n}d_{i}}$ — чётное число;
• графическая последовательность чисел — последовательность ${\displaystyle (d_{1},d_{2},\ldots ,d_{n})}$ целых неотрицательных чисел такая, что существует граф, последовательность степеней вершин которого совпадает с ней.

Теорема утверждает, что правильная последовательность ${\displaystyle (d_{1},d_{2},\ldots ,d_{n})}$ является графической тогда и только тогда, когда для каждого ${\displaystyle k}$ , ${\displaystyle 1\leq k\leq n-1}$ , верно неравенство:

${\displaystyle \sum _{i=1}^{k}{{d_{i}}\leq k(k-1)}+\sum _{i=k+1}^{n}{\min\{k,{d_{i}}}\}}$ .

Алгоритмизация

Построить граф по графической последовательности можно полиномиальным алгоритмом , который строится на основании критерия Гавела — Хакими .

Примечания

Литература

• Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. — М.: Наука, 1990.