Теорема Эрдёша — Галлаи

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

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

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

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

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

[math]\displaystyle{ \sum^{k}_{i=1} { {d_i} \leq k(k-1)} + \sum^{n}_{i=k+1} {\min\{k,{d_i}}\} }[/math].

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

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

Литература

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