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

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

ФормулировкаПравить

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

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

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

$\underset{i=1}{\overset{k}{\sum <!--\; \sum \; -->}}{d}_i\le <!--\; \le \; -->k(k-<!--\; -\; -->1)+\underset{i=k+1}{\overset{n}{\sum <!--\; \sum \; -->}}min\{k,d_i\}$$\sum _{{i=1}}^{{k}}{{d_{i}}\leq k(k-1)}+\sum _{{i=k+1}}^{{n}}{\min\{k,{d_{i}}}\}$ .

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

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

ЛитератураПравить

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