Граф Турана T(n,r) — це граф, утворений розкладанням n вершин на r підмножин, з якомога ближчим розміром, і вершини в цьому графі з'єднані ребром, якщо вони належать різним підмножинам. Граф буде мати підмножин розміром і підмножин розміром . Таким чином, це повний r-частковий граф
Граф Турана | |
---|---|
![]() Граф Турана T(13,4) | |
Названо на честь | Пал Туран |
Вершин | n |
Ребер | ~ |
Радіус | |
Діаметр | |
Обхват | |
Хроматичне число | r |
Позначення | T(n,r) |
Кожна вершина має степінь або , або . Кількість ребер дорівнює
Граф є регулярним, якщо n ділиться на r.
Теорема Турана
Графи Турана названо на честь Пала Турана, який використав їх для доведення теореми Турана, важливого результату в екстремальній теорії графів.
За принципом Діріхле, будь-яка множина з r + 1 вершин у графі Турана включає дві вершини з однієї й тієї ж частки графа. Таким чином, граф Турана не містить кліки розміру r + 1. Згідно з теоремою Турана, граф Турана має максимально можливе число ребер серед усіх графів без клік розміру r + 1, що мають n вершин. Киваш і Судаков (Keevash, Sudakov, 2003) показали, що граф Турана є єдиним графом без клік розміру r + 1, що має порядок n, у якому будь-яка підмножина з αn вершин має щонайменше ребер, якщо α досить близьке до 1. [en] розширює теорему Турана, обмежуючи число ребер у графі, який не має підграфом фіксованого графа Турана. Внаслідок цієї теореми в теорії екстремальних графів для будь-якого забороненого підграфа можна довести схожі межі, залежні від хроматичного числа підграфа.
Особливі випадки
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHdMekEzTDA5amRHRm9aV1J5YjI0dWMzWm5MekUxTUhCNExVOWpkR0ZvWldSeWIyNHVjM1puTG5CdVp3PT0ucG5n.png)
Деякі величини параметра r графів Турана призводять до чудових графів, які вивчаються окремо.
Граф Турана T(2n,n) можна отримати видаленням досконалого парування з повного графа K2n. Як показав Робертс (Roberts, 1969), рамковість цього графа дорівнює рівно n. Цей граф іноді називають графом Робертса. Цей граф є також 1-[en] n-вимірного (кографа). Наприклад, граф T(6,3) = K2,2,2 — це граф правильного октаедра. Якщо n пар приходять на вечірку і кожна людина тисне руку всім, окрім свого партнера, то цей граф описує множину рукостискань. З цієї причини його також називають графом коктейль-вечірки.
Граф Турана T(n,2) — це повний двочастковий граф, і, якщо n парне, це (граф Мура). Якщо r — це дільник n, граф Турана є симетричним і сильно регулярним, хоча деякі автори вважають, що графи Турана є тривіальним випадком сильної регулярності і тому виключають їх з визначення строго регулярних графів.
Граф Турана має 3a2b найбільших клік, де 3a + 2b = n та b ≤ 2. Кожна найбільша кліка утворюється вибором однієї вершини з кожної частки. Це число найбільших клік є найбільшим можливим серед усіх графів з n вершинами, незалежно від числа ребер у графі (Мун і Мозер, 1965). Ці графи іноді називають графами Муна-Мозера.
Інші властивості
Будь-який граф Турана є (кографом). Таким чином, його можна утворити з окремих вершин послідовністю операцій диз'юнктного об'єднання і доповнення. Зокрема, таку послідовність можна почати утворенням усіх незалежних множин графа Турана як диз'юнктного об'єднання ізольованих вершин. Тоді весь граф є доповненням диз'юнктного об'єднання доповнень цих незалежних множин.
Чао і Новацький (Chao, Novacky, 1982) показали, що графи Турана хроматично єдині — ніякі інші графи не мають таких самих хроматичних многочленів. Нікіфоров (Nikiforov, 2005) використовував графи Турана для знаходження нижньої межі суми k-х (власних значень) графа і його доповнення.
Фолс, Повел і Сноїнк (Falls, Powell, Snoeyink) розробили ефективний алгоритм для пошуку кластерів ортологічних груп генів у геномі поданням даних як графа і пошуком великих підграфів Турана.
Графи Турана мають також низку цікавих властивостей, пов'язаних з [en]. Пор і Вуд (Pór, Wood, 2005) дають нижню межу Ω((rn)3/4) будь-якого тривимірного вкладення графа Турана. Вітсенгаузен (Witsenhausen, 1974) висловив гіпотезу, що найбільша сума квадратів відстаней між n точками всередині кулі Rd одиничного діаметра досягається на конфігурації, утвореній вкладенням графа Турана у вершини правильного симплекса.
Граф G з n вершинами є підграфом графа Турана T(n,r) тоді й лише тоді, коли G допускає (рівномірне розфарбування) в r кольорів. Розкладання графа Турана на незалежні множини відповідає розкладанню G на класи кольорів. Зокрема, граф Турана є єдиним максимальним графом з n вершинами з рівномірним розфарбуванням у r кольорів.
Література
- C. Y. Chao, G. A. Novacky. On maximally saturated graphs // Discrete Mathematics. — 1982. — Т. 41, вип. 2 (21 червня). — С. 139–143. — DOI: .
- Craig Falls, Bradford Powell, Jack Snoeyink. Computing high-stringency COGs using Turán type graphs. з джерела 17 квітня 2021. Процитовано 4 січня 2021.
- Peter Keevash, Benny Sudakov. Local density in graphs with forbidden subgraphs // Combinatorics, Probability and Computing. — 2003. — Т. 12, вип. 2 (21 червня). — С. 139–153. — DOI: .
- J. W. Moon, L. Moser. On cliques in graphs // Israel Journal of Mathematics. — 1965. — Т. 3 (21 червня). — С. 23–28. — DOI: .
- Vladimir Nikiforov. Eigenvalue problems of Nordhaus-Gaddum type. — 2005. — 21 червня. — arXiv:math.CO/0506260.
- Attila Pór, David R Wood. (Proc. Int. Symp. Graph Drawing (GD 2004)). — Lecture Notes in Computer Science no. 3383, Springer-Verlag, 2005. — С. 395–402. — DOI:
- F. S. Roberts. Recent Progress in Combinatorics. — Academic Press, 1969. — С. 301–310.
- P. Turán. On an extremal problem in graph theory // Matematiko Fizicki Lapok. — 1941. — Т. 48 (21 червня). — С. 436–452.
- H. S. Witsenhausen. On the maximum of the sum of squared distances under a diameter constraint // American Mathematical Monthly. — The American Mathematical Monthly, Vol. 81, No. 10, 1974. — Т. 81, вип. 10 (21 червня). — С. 1100–1101. — DOI: .
Посилання
- Weisstein, Eric W. Cocktail Party Graph(англ.) на сайті Wolfram MathWorld.
- Weisstein, Eric W. Граф октаедра(англ.) на сайті Wolfram MathWorld.
- Weisstein, Eric W. Граф Турана(англ.) на сайті Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет