Erdos--Gallai criterion: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Erd\"{o}s--Gallai criterion''' --- критерий Эрдёша--Галлаи. A sequence of integers <math>d_{1}, \ldots, d_{n}</math> with <math>n - 1 \geq d…»)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Erd\"{o}s--Gallai criterion''' --- критерий Эрдёша--Галлаи.  
'''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 Erd\"{o}s-Gallai inequality).
(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).