Теорема Турана: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Теорема Турана''' (''P.Tur\'{a}n, 1941'') - ''Пусть <math>n</math> и <math>k</math> --- два целых числ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Теорема Турана''' (''P.Tur\ | '''Теорема Турана''' (''[[P.Turan, 1941|<math>P.Tur\acute{a}n, 1941</math>]]'') - | ||
''Пусть <math>n</math> и <math>k</math> | ''Пусть <math>n</math> и <math>k</math> - два целых числа (<math>n \geq k \geq 1</math>) и пусть <math>G_{n,k}</math> - [[граф]], состоящий из <math>k</math> непересекающихся [[клика|клик]] из <math>\lceil n/k \rceil</math> и <math>\lfloor n/k \rfloor</math> [[вершина|вершин]]. Если <math>G</math> - граф с <math>n</math> вершинами и неплотностью <math>\alpha(G) = k</math>, то число [[ребро|ребер]] <math>|E(G)| \geq |E(G_{n,k})|</math> и равенство имеет место тогда и только тогда, когда <math>G</math> [[изоморфизм графов|изоморфен]] <math>G_{n,k}</math>.'' | ||
==Литература== | ==Литература== | ||
[Berge], | [Berge], | ||
[Lov\ | [<math>Lov\acute{a}sz</math>] | ||
Версия от 13:11, 4 февраля 2010
Теорема Турана ([math]\displaystyle{ P.Tur\acute{a}n, 1941 }[/math]) - Пусть [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],
[[math]\displaystyle{ Lov\acute{a}sz }[/math]]