Граф без трикутників
У теорії графів графом без трикутників називається неорієнтований граф, в якому ніякі три вершини не утворюють трикутний граф з ребер. Графи без трикутників можна визначити також як графи з кліковим числом ≤ 2, графи з обхватом ≥ 4, графи без породжених 3-циклів, або локально незалежні графи.
За теоремою Турана граф з n вершинами, що не має трикутників, з максимальним числом ребер є повним двочастковим графом, в якому числа вершин у кожній частці графа близькі настільки, наскільки можливо.
Задача знаходження трикутників — це задача визначення, чи містить граф трикутники чи ні. Якщо граф містить трикутник — від алгоритму часто вимагають знайти три вершини, які утворюють трикутник.
Можна перевірити, чи є у графі з m ребрами трикутники за час O(m1.41).[1] Інший підхід — знайти слід матриці A3, де A — це матриця суміжності графа. Слід дорівнює нулю в тому і тільки в тому випадку, якщо в графі немає трикутників. Для щільних графів більш ефективний цей простий алгоритм, заснований на множенні матриць, оскільки він знижує тимчасову складність O (n2.373), де n — кількість вершин.
Як показали Імрих, Клавжар і Мулдер (Imrich, Klavžar, Mulder, 1999), розпізнавання графів без трикутників еквівалентно по складності з розпізнаванням медіанних графів[ru]. Однак на поточний момент найкращі алгоритми медіанних графів використовують як підпрограми розпізнавання трикутників, а не навпаки.
Складність дерева рішень або складність запиту завдання, де запити до оракула, який запам'ятовує матриці суміжності графа, дорівнює Θ(n2). Однак для квантових алгоритмів[ru] найкраща нижня межа дорівнює Ω(n), але найкращий відомий алгоритм має оцінку O(n1.29) (Belovs, 2011).
Незалежна множина з вершин у графі з n вершинами, які не мають трикутників, легко знайти — або існує вершина з більш ніж сусідами (в цьому випадку сусіди утворюють незалежну множину), або у всіх вершин менше ніж сусідів (у цьому випадку будь -яка найбільша незалежна множина повинна мати щонайменше вершин).[2] Цю межу можна злегка поліпшити — у будь-якому графі без трикутників існує незалежна множина з вершинами, а в деяких графах без трикутників будь-яка незалежна множина має вершин.[3] Один із способів створити графи без трикутників, в якому всі незалежні множини малі — це triangle-free process (процес без трикутників)[4], який створює максимальні графи без трикутників шляхом послідовного додавання випадково вибраних ребер, уникаючи створення трикутників. З великим ступенем імовірності процес утворює графи з числом незалежності . Можна знайти також знайти регулярні графи з тими ж властивостями.[5]
Ці результати можна також розуміти як завдання асимптотичних кордонів чисел Рамсея R(3, t) у вигляді — якщо ребра повного графа з вершинами розфарбувати в червоний і синій кольори, то або червоний граф містить трикутник, або в ньому немає трикутників, а тоді має існувати незалежна множина розміру t, відповідна кліці цього розміру в синьому графі.
Безліч досліджень за графами без трикутників зосереджені на розфарбуванні графа. Двочастковий граф (тобто, будь-який розфарбований у два кольори граф) не має трикутників, а теорема Ґрьоча стверджує, що будь —який планарний граф без трикутників може бути розфарбований у три кольори.[6] Проте для непланарных графів без трикутників може знадобитися більше трьох кольорів.
Мичельський (Mycielski, 1955) визначив побудову, тепер звану мичельськіаном, яка утворює новий граф без трикутників з іншого графа без трикутників. Якщо граф має хроматичне число k, його мичельськіан має хроматичне число k + 1, так що дану побудову можна використати, щоб показати, що довільно велика кількість кольорів може знадобитися для розмальовки непланарного графа без трикутників. Зокрема, граф Ґрьоча, граф з 11 вершинами, утворений повторенням побудови Мичельського, є графом без трикутників, який не можна розфарбувати менше ніж чотирма кольорами, і є найменшим графом з цими властивостями[7]. Гимбель і Томассен (Gimbel, Thomassen та , 2000) і (Nilli, 2000) показали, що число кольорів, необхідних для забарвлення будь-якого m-реберного графа без трикутників одно
і існують графи без трикутників, що мають хроматичні числа, пропорційні цієї межі.
Є також деякі результати щодо зв'язку розмальовки з мінімальним ступенем графів без трикутників. Андрасфай і Ердеш (Andrásfai, Erdős, vt sos, 1974) довели, що будь-який граф з n вершинами без трикутників, в якому кожна вершина має більш сусідів, повинен бути двочастковим. Це найкращий можливий результат такого типу, так як 5-цикл вимагає три кольори, але має в точності сусідів для кожної вершини. Натхнені цим результатом, Ердеш та Симомонович (Erdős, Simonovits, 1973) висловили гіпотезу, що будь-який граф без трикутників з n вершинами, в якому кожна вершина має щонайменше сусідів, може бути розфарбований тільки в три кольори. Однак Хеггквіст (Häggkvist, 1981) спростував цю гіпотезу, представивши контрприклад, в якому кожна вершина графа Ґрьоча замінена незалежною множиною спеціально підібраного розміру. Джин (Jin, 1995) показав, що будь-який граф без трикутників з n вершинами, в якому кожна вершина має більш сусідів можна розфарбувати в 3 кольори. Це найкращий результат цього типу, оскільки для графа Хеггквіста потрібно чотири кольори і він має в точності сусідів для кожної вершини. Нарешті, Брандт і Томасси (Brandt, Thomassé, 2006) довели, що будь-який граф без трикутників з n вершинами, в якому кожна вершина має більш ніж сусідів, можна розфарбувати в 4 кольори. Додаткові результати цього виду неможливі, оскільки Хайналь (Hajnal)[8] знайшов приклади графів без трикутників з довільно великим хроматичним числом і мінімальним ступенем для будь-якого .
- Примітки
- ↑ Alon, Yuster, Zwick, 1994.
- ↑ Boppana та Halldórsson, 1992 p. 184, ґрунтуючись на ідеї більш раннього апроксимаційного алгоритму Аві Вігдерсона.
- ↑ Kim, 1995.
- ↑ Erdős, Suen, Winkler, 1995; Bohman, 2008
- ↑ Alon, Ben-Shimon, Krivelevich, 2008.
- ↑ Grötzsch, 1959; (Thomassen, 1994)).
- ↑ Chvátal, 1974.
- ↑ Erdős, Simonovits, 1973.
- Джерела
- N. Alon, S. Ben-Shimon, M. Krivelevich. A note on regular Ramsey graphs. — 2008..
- N. Alon, R. Yuster, U. Zwick. Proceedings of the 2nd European Symposium on Algorithms[en], Utrecht, The Netherlands. — 1994. — С. 354-364..
- B. Andrásfai, P. Erdős, V. T. Vt sos. On the connection between chromatic number, maximal clique and minimal degree of a graph // Discrete Mathematics. — 1974. — Т. 8, вип. 3. — С. 205-218. — DOI: ..
- T. Bohman. The triangle-free process. — 2008..
- Ravi Boppana, Magnús M. Halldórsson. Approximating maximum independent sets by excluding subgraphs // BIT. — 1992. — Т. 32, вип. 2. — С. 180-196. — DOI: ..
- S. Brandt, S. Thomassé. Dense triangle-free graphs are four-colorable: a solution to the Erdős-Simonovits problem. — 2006..
- N. Chiba, T. Nishizeki. Arboricity and subgraph listing algorithms // SIAM Journal on Computing. — 1985. — Т. 14, вип. 1. — С. 210-223. — DOI: ..
- Vašek Chvátal. Graphs and комбінаторики (Proc. Capital Conf., George Washington Univ., Washington, D. C., 1973). — Springer-Verlag, 1974. — Т. 406. — С. 243-246. — (Lecture Notes in Mathematics).