Критерий Эрдеша-Галлаи: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Критерий Эрдеша - Галлаи''' (''[[Erdos - Gallai criterion|<math>Erd\ddot{o}s - Gallai criterion</math>]]'') -
'''Критерий Эрдеша - Галлаи''' (''[[Erdos - Gallai criterion|<math>Erd\ddot{o}s - Gallai criterion</math>]]'')
критерий графичности числовой последовательности.
критерий графичности числовой последовательности.


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

Текущая версия от 11:58, 15 апреля 2011

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

Теорема. Правильная [math]\displaystyle{ n }[/math]-последовательность [math]\displaystyle{ d }[/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.