У теорії графів графом без клешень називається граф, який не містить клешень, як породжених підграфів.
Клешнею називається повний двочастковий граф K1,3 (тобто, зірка з трьома ребрами, трьома листками і однією центральною вершиною). Граф без клешень — це граф, в якому кожен породжений підграф не є клешнею. Тобто будь-яка підмножина з чотирьох вершин не є зіркою з трьома ребрами, що виходять з центральної вершини. Також можливо визначити граф без клешень, як граф, в якому окіл будь-якої вершини утворює доповнення графу без трикутників.
Графи без клешень спочатку вивчалися як узагальнення реберних графів і викликали додатковий інтерес лише тоді, коли було зроблено три ключових відкриття про графи без клешень: усі зв'язні графи без клешень парного порядку мають досконалі парування; відкриття поліноміального за часом алгоритму пошуку максимальних незалежних множин у графах без клешень; опис досконалих графів без клешень; Графам без клешень присвячені сотні статей і кілька оглядів.
Приклади
Реберний граф L(G) будь-якого графу G не має клешень. L(G) містить вершину для кожної дуги G , і вершини є суміжними в L(G) коли відповідні ребра мають спільну вершину в G. Реберний граф L(G) не може мати клешень, оскільки, якщо кожне з трьох ребер e1, e2, і e3 графу G має загальну вершину з четвертим ребром e4, то згідно з принципом Діріхле щонайменше 2 ребра з e1, e2, і e3 мають спільну вершину. Реберні графи можуть бути описані дев'ятьма забороненими підграфами, і клешня є найпростішим з цих дев'яти графів. Це дає мотив для вивчення графів без клешень. (графи, вершини яких відповідають n-бітовим двійковим рядкам для деякого n, а дуги відповідають (n−1)-бітним збігам двох рядків) не мають клешень. Один із способів показати це — побудувати граф де Бройна для n-бітових рядків як реберний граф від графу де Брейна для (n−1)-бітних рядків. Доповнення будь-якого графу без трикутників не має клешень. Ці графи включають будь-який повний граф як особливий випадок. (інтервальні графи, утворені як графи перетинів сімейств інтервалів, де жоден інтервал не містить інший інтервал сімейства) не мають клешень, оскільки чотири таких інтервали не можуть перетинатися за схемою клешні. Веретено Мозера (граф, що має сім вершин та використовується для доведення нижньої межі хроматичного числа площини) не має клешень. Графи деяких багатогранників і політопів не мають клешень. Сюди входять граф тетраедра і взагалі будь-який симплекс (повний граф), граф октаедра і, в загальному випадку, будь-який крос-політоп (ізоморфний граф-ізоморфен, який утворюється завдяки видаленню досконалого парування з повного графа), граф правильного ікосаедра, і граф гексадекахорона. Граф Шлефлі, сильно регулярний граф, що має 27 вершин, не має клешень.
Розпізнавання Можна перевірити безпосередньо, що заданий граф з n вершинами і m ребрами не має клешень за час O(n4)) шляхом перевірки кожної четвірки вершин — чи не породжують вони клешню. Трохи ефективніше, але складніше, можна перевірити, чи не має граф клешень шляхом перевірки для кожної вершини графу, що доповнення графу сусідів вершини не містить трикутника. Граф містить трикутник в тому і тільки в тому випадку, якщо куб матриці інцидентності містить ненульовий діагональний елемент, так що пошук трикутника може бути здійснений за той же асимптотичний час, що і множення матриць n × n. Таким чином, при використанні алгоритму Копперсміта—Винограда, загальний час визначення, чи є у графу клешні, становить O(n3.376).
Клокс, Крач і Мюллер звернули увагу на те, що в графі без клешень кожна вершина має максимум сусідів, в іншому випадку згідно з теоремою Турана околиця вершини не матиме достатнє число ребер, щоб сформувати додаток графу без трикутників. Це спостереження дозволяє перевірити сусідів з використанням згаданого раніше алгоритму швидкого добутку матриць за той же асимптотичний час . Найгірший випадок цього алгоритму виникає, коли Ω(√m) вершин мають по Ω(√m) сусідів кожна, а решта вершин мають мало сусідів, у цьому випадку загальний час дорівнює (m3.376/2) = O(m1.688).
Перерахування Оскільки графи без клешень мають усі доповнення графів без трикутників, число графів без клешень з n вершинами росте як мінімум з тією ж швидкістю, що і число графів без трикутників, тобто, по експоненті від кореня з n. Число зв'язкових графів без клешень з n ребрами для n = 1, 2, … складає: 1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, … . Якщо графи незв'язні, їх число збільшується: 1, 2, 4, 10, 26, 85, 302, 1285, 6170, … . Техніка Палмера, Ріда і Робінсона дозволяє порахувати число кубічних графів без клешень дуже ефективно, що є незвичним для задач на перерахування графів.
Парування
Самнер і, незалежно, Лас Вергнас довели, що будь-який зв'язний граф без клешень з парним числом вершин має досконале парування. Тобто існує безліч ребер в графі так, що кожна вершина є кінцевою вершиною в точності одного ребра з парування. З цього випливає, що для реберних графів, що мають парне число ребер, можна розбити всі ребра на шляхи довжиною два. Досконалі парування можуть бути використані для ще однієї характеристики графів без клешень — це точно ті графи, в яких будь-який зв'язний породжений підграф парного порядку має досконале парування.
Доведення Самнера показує, що в будь-якому зв'язковому графі без клешень можна знайти пару сполучених вершин, видалення яких залишає граф зв'язковим. Для доведення цього Самнер знаходить пару вершин u і v, які як можна більше віддалені один від одного, і вибирає w серед сусідів вершини v, віддалену від u наскільки можливо. Як він показав, ні v, ні w не можуть лежати на найкоротшому шляху від будь-якої іншої вершини до u, так що видалення вершин v і w залишає граф зв'язковим. Послідовне видалення таких пар утворює досконале парування в графі без клешень.
Та ж сама ідея доведення працює і в загальнішому випадку: якщо u — будь-яка вершина, v — будь-яка вершина, максимально віддалена від u, і w — будь-яка сусідня вершина для v, максимально віддалена від u. Тепер видалення v і w з графу не змінює відстаней до u. Таким чином, процес формування парування шляхом знаходження та видалення пар vw, максимально віддалених від u, може бути здійснений за лінійний час простим обходом дерева пошуку вшир, розпочатого з вершини u. Хробак, Наор і Новик дали інший лінійний за часом алгоритм, заснований на пошуку вглиб, а також ефективні паралельні алгоритми для тієї ж задачі. Фаудрі, Фландрін и Ріяче отримали кілька схожих результатів, зокрема:
(r − 1)-зв'язний граф, що не містить K1,r підграфів непарного порядку, має досконалі парування для будь-якого r ≥ 2; графи непарного порядку без клешень з максимум однією вершиною степені один можуть бути поділені на один непарний цикл і парування; для будь-якого k, не меншого за половину мінімальної степені графу без клешень, у якому або k, або число вершин парно, граф має k-фактор; якщо граф без клешень є (2k + 1)-зв'язним, то будь-які k-реберні парування можуть бути розширені до досконалого парування.
Незалежні множини
Незалежна множина в реберному графі відповідає паруванню у вихідному графі, тобто набору ребер, в якому ніякі два ребра не мають спільних точок. Як показав Едмондс, максимальне парування в будь-якому графі можна знайти за поліноміальний час; Сбіхі розширив цей алгоритм так, що новий алгоритм знаходить максимальну незалежну множину в будь-якому графі без клешень. Мінті , виправлений Накамурою і Тамурою, дав інше розширення алгоритмів Едмонда для графів без клешень, перетворюючого задачу на пошук парування у допоміжному графі, отриманого із вихідного графу без клешень. Підхід Мінті може бути використаний для вирішення за поліноміальний час більш загальної задачі знаходження незалежної множини максимальної ваги. Існує узагальнення цих результатів на широкий клас графів.
Як зауважив Сбіхі, якщо — незалежна множина в графі без клешень, то будь-яка вершина графу може мати максимум дві сусідні вершини з — три сусідні вершини утворили б вже саму клешню. Сбіхі називає вершину насиченою, якщо вона має дві сусідні вершини з , і ненасиченою, якщо вона не належить, і, в той же час, має менше двох сусідів з . Зі спостереження Сбіхі випливає, що, якщо і є незалежні множини, то граф, породжений , повинен мати ступінь не вище другого. Таким чином, він є об'єднанням шляхів і циклів. Зокрема, якщо — не максимальна незалежна множина, вона відрізняється від будь-якої максимальної незалежної множини циклами і поповнюючими шляхами, тобто шляхами, в яких вершини з і не з чергуються, і у яких обидві кінцеві вершини не насичені. Симетрична різниця графів і поповнюючого шляха є максимальна незалежна множина (симетрична різниця графів H і G, що мають один і той же набір вершин V — це граф з тим же набором вершин V, що містить ребра G і H, але не містить загальних ребер, що належать як G, так і H). Алгоритм Сбіхі послідовно збільшує розмір незалежної множини шляхом знаходження поповнюючих шляхів, доки такі можна знайти.
Знаходження поповнюючого шляху є складним завданням, оскільки поширення шляху може і не існувати, якщо він містить ребро між двома вершинами, що не належать . На щастя, це може статися тільки в двох випадках: дві суміжні вершини можуть бути кінцевими вершинами шляху, або між ними лежить одна вершина, суміжна обом. Будь-яка інша суміжна вершина призведе до клешні. Суміжних кінцевих вершин можна позбутися, тимчасово видаляючи всі суміжні v вершини перед пошуком поповнюючого шляху, початківця в v. Якщо знайдений шлях не буде входити у вершину v, можна видалити його з графу до кінця алгоритму. Після такої редукції графу завдання може бути описано в термінах , хоча Сбіхі і не користувався цією термінологією. Граф-перемикач — це ненаправлений граф, в якому дуги будь-якої вершини розділені на дві групи, і будь-який шлях, що проходить через вершину, зобов'язаний містити ребра з обох груп. Можна побудувати граф-перемикач на множині насичених і ненасичених вершин графу без клешень, ребра якого з'єднують вершини, якщо вони не є суміжними у вихідному графі, і існує шлях довжини 2 між ними, що проходить через вершину з I. Дві множини ребер в кожній вершині утворюються двома вершинами I, через які ці шляхи, довжиною 2, проходять. Шлях у графі-перемикачі між двома ненасиченими вершинами відповідає поповнюючому шляху у вихідному графі. Граф-перемикач має квадратичну складність, і шлях у ньому може бути знайдений за лінійний час, а за весь час роботи алгоритму можуть знадобитися O(n) поповнюючих шляхів, які необхідно знайти. Таким чином, алгоритм Сбіхі вимагає O(n3) часу роботи.
Розфарбовування, кліки, і домінування Досконалий граф — це граф, в якому хроматичне число дорівнює розміру максимальної кліки, і в якому ця рівність зберігається у всіх породжених підграфах. Відомо (зі сильної теореми про досконалі графи), що досконалі графи можуть бути охарактеризовані як графи, що не мають непарних циклів чи доповнень непарним циклам (так звані непарні діри) як індукованих підграфів . Проте багато років цей факт залишався гіпотезою, доведеною тільки для спеціальних підкласів графів. Одним з таких підкласів було сімейство графів без клешень — кілька авторів виявили, що графи без клешень і без непарних циклів і дірок досконалі. Досконалість графу без клешень може бути перевірена за поліноміальний час. У досконалому графі без клешень околиця будь-якої вершини утворює доповнення двочасткового графу. Можна розфарбувати досконалий граф без клешень або знайти в ньому максимальну кліку за поліноміальний час.