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

У теорії графів, теорема Турана — це результат щодо числа ребер у графі, що не містить K_r+1.

n-вершинний граф, що не містить (r + 1)-вершинну кліку, може бути побудований розбиттям множини його вершин у r частин однакового або майже однакового розміру, та з'єднанням двох вершин ребром завжди, коли вони належать двом різним частинам. Будемо називати отриманий граф граф Турана T(n,r). Теорема Турана стверджує, що граф Турана містить найбільше число ребер у класі всіх n-вершинних графів, що не містять K_r+1.

Графи Турана були вперше описані та досліджені угорським математиком Палом Тураном у 1941 році, хоча частковий випадок теореми був сформульований раніше Мантелем у 1907 році.

Формальне твердження теореми

Формально, теорема Турана може бути сформульована таким чином.

Нехай G будь-який підграф K_n такий, що G не містить K_r+1. Тоді число ребер у G не більше

${\frac {r-1}{r}}\cdot {\frac {n^{2}}{2}}=\left(1-{\frac {1}{r}}\right)\cdot {\frac {n^{2}}{2}}.$

Еквівалентне формулювання може бути подане так: Між n-вершинних простих графів без (r + 1)-клік, T(n,r) має максимальне число ребер.

Як частковий випадок, для r = 2, отримуємо теорему Мантеля:

Максимальне число ребер у n-вершинному графі без трикутників складає $\lfloor n^{2}/4\rfloor .$

Іншими словами, необхідно видалити близько половини ребер у K_n для того, щоб отримати граф без трикутників.

Див. також

• Граф Турана
• Екстремальна теорія графів
• Теорема Ердеша — Секереша
• Багаточастковий граф
• Задача Турана про цегельний завод

Посилання

• Turán, Paul (1941). On an extremal problem in graph theory. Matematikai és Fizikai Lapok (Hungarian) . 48: 436—452.
• Aigner, Martin; Ziegler, Günter M. (1998), Proofs from THE BOOK, Berlin, New York: Springer-Verlag.
• West, Douglas Brent (1999) [1996], Introduction to Graph Theory (вид. 2nd), Prentice Hall, ISBN 978-0-13-014400-3.