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

У теорії графів, теорема Турана — це результат щодо числа ребер у графі, що не містить 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 On an extremal problem in graph theory // Matematikai és Fizikai Lapok. — Т. 48. — (1941) С. 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 .