Критерий Эрдеша-Галлаи

Материал из WEGA
Версия от 14:24, 12 ноября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Критерий Эрдеша - Галлаи''' (''Erd\"{o}s - Gallai criterion'') - критерий графичности числ...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

Теорема. Правильная [math]\displaystyle{ n }[/math]-последовательность [math]\displaystyle{ d }[/math] является графической тогда и только тогда, когда для каждого [math]\displaystyle{ k }[/math], [math]\displaystyle{ 1 \leq k \leq n-1 }[/math], верно неравенство [math]\displaystyle{ $\sum_{{i=1}^{{k} d_{{i} \leq k(k-1) + \sum_{{i=k+1''^{n} \min\{k, d_{i}\}. }[/math]

Литература

[Лекции]