Теорема Турана

Материал из WEGA
Версия от 15:11, 2 февраля 2010; Glk (обсуждение | вклад) (Создана новая страница размером '''Теорема Турана''' (''P.Tur\'{a}n, 1941'') - ''Пусть <math>n</math> и <math>k</math> --- два целых числ...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Теорема Турана (P.Tur\'{a}n, 1941) - Пусть [math]\displaystyle{ n }[/math] и [math]\displaystyle{ k }[/math] --- два целых числа ([math]\displaystyle{ n \geq k \geq 1 }[/math]) и пусть [math]\displaystyle{ G_{n,k} }[/math] --- граф, состоящий из [math]\displaystyle{ k }[/math] непересекающихся клик из [math]\displaystyle{ \lceil n/k \rceil }[/math] и [math]\displaystyle{ \lfloor n/k \rfloor }[/math] вершин. Если [math]\displaystyle{ G }[/math] --- граф с [math]\displaystyle{ n }[/math] вершинами и неплотностью [math]\displaystyle{ \alpha(G) = k }[/math], то число ребер [math]\displaystyle{ |E(G)| \geq |E(G_{n,k})| }[/math] и равенство имеет место тогда и только тогда, когда [math]\displaystyle{ G }[/math] изоморфен [math]\displaystyle{ G_{n,k} }[/math].

Литература

[Berge],

[Lov\'{a}sz]