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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Литература

  • Berge C. Graphs (second revised edition). — Amsterdam; New York; Oxford: North-Holland, 1985.
  • Lov\acute{a}sz\,\, L.\,\, Combinatorial\,\, problems\,\, and\,\, exercises.\,\, -\,\,  Budapest:\,\, Acad\acute{e}miqi\,\, Kiado,\,\, 1979.