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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Критерий Эрдеша - Галлаи''' (''Erd\"{o}s - Gallai criterion'') - критерий графичности числ...)
 
Нет описания правки
Строка 1: Строка 1:
'''Критерий Эрдеша - Галлаи''' (''Erd\"{o}s - Gallai criterion'') -  
'''Критерий Эрдеша - Галлаи''' (''[[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>$\sum_{{i=1}^{{k} d_{{i} \leq k(k-1) + \sum_{{i=k+1''^{n} \min\{k,
<math>\sum^{k}_{i=1} { {d_i} \leq k(k-1)} + \sum^{n}_{i=k+1} {\min\{k,{d_i}}\}.</math>
d_{i}\}.</math>
==Литература==
==Литература==
[Лекции]
[Лекции]

Версия от 12:14, 16 ноября 2009

Критерий Эрдеша - Галлаи ([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]

Литература

[Лекции]