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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Критерий Эрдеша - Галлаи''' (''Erd\"{o}s - Gallai criterion'') - критерий графичности числ...)
(нет различий)

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

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

Литература

[Лекции]