Теорема Турана: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Теорема Турана''' (''P.Tur\'{a}n, 1941'') - ''Пусть <math>n</math> и <math>k</math> --- два целых числ...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Теорема Турана''' (''P.Tur\'{a}n, 1941'') -
'''Теорема Турана''' (''[[P.Turan, 1941|<math>P.Tur\acute{a}n, 1941</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>.''
''Пусть <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 C. Graphs (second revised edition). — Amsterdam; New York; Oxford: North-Holland, 1985.
 
[Lov\'{a}sz]
* <math>Lov\acute{a}sz\,\, L.\,\, Combinatorial\,\, problems\,\, and\,\, exercises.\,\, -\,\,  Budapest:\,\, Acad\acute{e}miqi\,\, Kiado,\,\, 1979. </math>

Текущая версия от 11:51, 19 сентября 2011

Теорема Турана ([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 C. Graphs (second revised edition). — Amsterdam; New York; Oxford: North-Holland, 1985.
  • [math]\displaystyle{ Lov\acute{a}sz\,\, L.\,\, Combinatorial\,\, problems\,\, and\,\, exercises.\,\, -\,\, Budapest:\,\, Acad\acute{e}miqi\,\, Kiado,\,\, 1979. }[/math]