Граф без трикутників

У теорії графів графом без трикутників називається неорієнтований граф, в якому ніякі три вершини не утворюють трикутний граф з ребер. Графи без трикутників можна визначити також як графи з кліковим числом ≤ 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] знайшов приклади графів без трикутників з довільно великим хроматичним числом і мінімальним ступенем   для будь-якого  .


Див. такожРедагувати

ПосиланняРедагувати

Примітки
Джерела