Erdos--Gallai criterion: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Erd\"{o}s--Gallai criterion''' --- критерий Эрдёша--Галлаи. A sequence of integers <math>d_{1}, \ldots, d_{n}</math> with <math>n - 1 \geq d…») |
ALEXM (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
''' | '''Erdős--Gallai criterion''' --- критерий Эрдёша--Галлаи. | ||
A sequence of integers <math>d_{1}, \ldots, d_{n}</math> with <math>n - 1 \geq d_{1} | A sequence of integers <math>d_{1}, \ldots, d_{n}</math> with <math>n - 1 \geq d_{1} | ||
| Строка 9: | Строка 9: | ||
\min\{r,d_{i}\}</math> for <math>r =2, \ldots, n-1</math>. | \min\{r,d_{i}\}</math> for <math>r =2, \ldots, n-1</math>. | ||
(the <math>r</math>-th | (the <math>r</math>-th Erdő}s-Gallai inequality). | ||
Версия от 11:58, 1 марта 2018
Erdős--Gallai criterion --- критерий Эрдёша--Галлаи.
A sequence of integers [math]\displaystyle{ d_{1}, \ldots, d_{n} }[/math] with [math]\displaystyle{ n - 1 \geq d_{1} \geq \ldots \geq d_{n} }[/math] is a graphic sequence of numbers iff
(1) [math]\displaystyle{ \sum_{i=1}^{n} d_{i} }[/math] is even, and
(2)[math]\displaystyle{ \sum_{i=1}^{r} d_{i} \geq r(r-1) + \sum_{i=r+1}^{n} \min\{r,d_{i}\} }[/math] for [math]\displaystyle{ r =2, \ldots, n-1 }[/math].
(the [math]\displaystyle{ r }[/math]-th Erdő}s-Gallai inequality).