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

'''Теорема Турана''' (''P.Tur\'{a}n, 1941'') -  

''Пусть <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>.''

[Lov\'{a}sz]