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

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

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

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

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

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

.

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

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

[1]

[2]

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

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

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

Примечания

Литература

Категории