Erdos--Gallai criterion

Материал из WikiGrapp
Версия от 15:54, 21 апреля 2011; Glk (обсуждение | вклад) (Новая страница: «'''Erd\"{o}s--Gallai criterion''' --- критерий Эрдёша--Галлаи. A sequence of integers <math>d_{1}, \ldots, d_{n}</math> with <math>n - 1 \geq d…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Erd\"{o}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\"{o}s-Gallai inequality).