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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Формальне твердження теореми[ред.ред. код]

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

Нехай G будь-який підграф Kn такий, що G не містить Kr+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.

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

Дивіться також[ред.ред. код]

Посилання[ред.ред. код]