Просмотр кода страницы Критерий Эрдеша-Галлаи

'''Критерий Эрдеша - Галлаи''' (''[[Erdos - Gallai criterion|<math>Erd\ddot{o}s - Gallai criterion</math>]]'') — 
критерий графичности числовой последовательности.

'''Теорема'''. ''[[Правильная последовательность|Правильная <math>n</math>-последовательность]] <math>d</math> является [[графическая последовательность чисел|графической]] тогда и только тогда, когда для каждого <math>k</math>, <math>1 \leq k
\leq n-1</math>, верно неравенство
<math>\sum^{k}_{i=1} { {d_i} \leq k(k-1)} + \sum^{n}_{i=k+1} {\min\{k,{d_i}}\}.</math>
==Литература==
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.