Критерий Эрдеша-Галлаи: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Критерий Эрдеша - Галлаи''' (''Erd\"{o}s - Gallai criterion'') - критерий графичности числ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Критерий Эрдеша - Галлаи''' (''Erd\ | '''Критерий Эрдеша - Галлаи''' (''[[Erdos - Gallai criterion|<math>Erd\ddot{o}s - Gallai criterion</math>]]'') — | ||
критерий графичности числовой последовательности. | критерий графичности числовой последовательности. | ||
'''Теорема'''. ''Правильная <math>n</math>-последовательность <math>d</math> является | '''Теорема'''. ''[[Правильная последовательность|Правильная <math>n</math>-последовательность]] <math>d</math> является [[графическая последовательность чисел|графической]] тогда и только тогда, когда для каждого <math>k</math>, <math>1 \leq k | ||
графической тогда и только тогда, когда для каждого <math>k</math>, <math>1 \leq k | |||
\leq n-1</math>, верно неравенство | \leq n-1</math>, верно неравенство | ||
<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.