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