У теорії графів графом без клешень називається граф, який не містить клешень, як породжених підграфів.
Клешнею називається повний двочастковий граф K1,3 (тобто, зірка з трьома ребрами, трьома листками і однією центральною вершиною). Граф без клешень — це граф, в якому кожен породжений підграф не є клешнею. Тобто будь-яка підмножина з чотирьох вершин не є зіркою з трьома ребрами, що виходять з центральної вершини. Також можливо визначити граф без клешень, як граф, в якому окіл будь-якої вершини утворює доповнення графу без трикутників.
Графи без клешень спочатку вивчалися як узагальнення реберних графів і викликали додатковий інтерес лише тоді, коли було зроблено три ключових відкриття про графи без клешень:
- усі зв'язні графи без клешень парного порядку мають досконалі парування;
- відкриття поліноміального за часом алгоритму пошуку (максимальних незалежних множин) у графах без клешень;
- опис досконалих графів без клешень;
Графам без клешень присвячені сотні статей і кілька оглядів.
Приклади
- Реберний граф L(G) будь-якого графу G не має клешень. L(G) містить вершину для кожної дуги G , і вершини є суміжними в L(G) коли відповідні ребра мають спільну вершину в G. Реберний граф L(G) не може мати клешень, оскільки, якщо кожне з трьох ребер e1, e2, і e3 графу G має загальну вершину з четвертим ребром e4, то згідно з принципом Діріхле щонайменше 2 ребра з e1, e2, і e3 мають спільну вершину. Реберні графи можуть бути описані дев'ятьма забороненими підграфами, і клешня є найпростішим з цих дев'яти графів. Це дає мотив для вивчення графів без клешень.
- [en] (графи, вершини яких відповідають n-бітовим двійковим рядкам для деякого n, а дуги відповідають (n−1)-бітним збігам двох рядків) не мають клешень. Один із способів показати це — побудувати граф де Бройна для n-бітових рядків як реберний граф від графу де Брейна для (n−1)-бітних рядків.
- Доповнення будь-якого графу без трикутників не має клешень. Ці графи включають будь-який повний граф як особливий випадок.
- [en] (інтервальні графи, утворені як графи перетинів сімейств інтервалів, де жоден інтервал не містить інший інтервал сімейства) не мають клешень, оскільки чотири таких інтервали не можуть перетинатися за схемою клешні.
- Веретено Мозера (граф, що має сім вершин та використовується для доведення нижньої межі хроматичного числа площини) не має клешень.
- Графи деяких багатогранників і політопів не мають клешень. Сюди входять граф тетраедра і взагалі будь-який симплекс (повний граф), граф октаедра і, в загальному випадку, будь-який крос-політоп (ізоморфний граф-ізоморфен, який утворюється завдяки видаленню досконалого парування з повного графу), граф правильного ікосаедра, і граф гексадекахорона.
- Граф Шлефлі, сильно регулярний граф, що має 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, … послідовність A022562 з Онлайн енциклопедії послідовностей цілих чисел, OEIS.
Якщо графи незв'язні, їх число збільшується:
- 1, 2, 4, 10, 26, 85, 302, 1285, 6170, … послідовність A086991 з Онлайн енциклопедії послідовностей цілих чисел, OEIS.
Техніка Палмера, Ріда і Робінсона дозволяє порахувати число кубічних графів без клешень дуже ефективно, що є незвичним для задач на перерахування графів.
Парування
Самнер і, незалежно, Лас Вергнас довели, що будь-який зв'язний граф без клешень з парним числом вершин має досконале парування. Тобто існує безліч ребер в графі так, що кожна вершина є кінцевою вершиною в точності одного ребра з парування. З цього випливає, що для реберних графів, що мають парне число ребер, можна розбити всі ребра на шляхи довжиною два. Досконалі парування можуть бути використані для ще однієї характеристики графів без клешень — це точно ті графи, в яких будь-який зв'язний породжений підграф парного порядку має досконале парування.
Доведення Самнера показує, що в будь-якому зв'язковому графі без клешень можна знайти пару сполучених вершин, видалення яких залишає граф зв'язковим. Для доведення цього Самнер знаходить пару вершин 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, можна видалити його з графу до кінця алгоритму. Після такої редукції графу завдання може бути описано в термінах [en], хоча Сбіхі і не користувався цією термінологією. Граф-перемикач — це ненаправлений граф, в якому дуги будь-якої вершини розділені на дві групи, і будь-який шлях, що проходить через вершину, зобов'язаний містити ребра з обох груп. Можна побудувати граф-перемикач на множині насичених і ненасичених вершин графу без клешень, ребра якого з'єднують вершини, якщо вони не є суміжними у вихідному графі, і існує шлях довжини 2 між ними, що проходить через вершину з I. Дві множини ребер в кожній вершині утворюються двома вершинами I, через які ці шляхи, довжиною 2, проходять. Шлях у графі-перемикачі між двома ненасиченими вершинами відповідає поповнюючому шляху у вихідному графі. Граф-перемикач має квадратичну складність, і шлях у ньому може бути знайдений за лінійний час, а за весь час роботи алгоритму можуть знадобитися O(n) поповнюючих шляхів, які необхідно знайти. Таким чином, алгоритм Сбіхі вимагає O(n3) часу роботи.
Розфарбовування, кліки, і домінування
Досконалий граф — це граф, в якому хроматичне число дорівнює розміру максимальної кліки, і в якому ця рівність зберігається у всіх породжених підграфах. Відомо (зі сильної теореми про досконалі графи), що досконалі графи можуть бути охарактеризовані як графи, що не мають непарних циклів чи доповнень непарним циклам (так звані непарні діри) як індукованих підграфів. Проте багато років цей факт залишався гіпотезою, доведеною тільки для спеціальних підкласів графів. Одним з таких підкласів було сімейство графів без клешень — кілька авторів виявили, що графи без клешень і без непарних циклів і дірок досконалі. Досконалість графу без клешень може бути перевірена за поліноміальний час. У досконалому графі без клешень околиця будь-якої вершини утворює доповнення двочасткового графу. Можна розфарбувати досконалий граф без клешень або знайти в ньому максимальну кліку за поліноміальний час.
Якщо граф без клешень не досконалий, завдання пошуку максимальної кліки стає NP-задачею. Задача знаходження оптимального розфарбування такого графу також є NP-задачею, оскільки (через реберний граф) ця задача узагальнює NP-завдання обчислення хроматичного числа графу. З тієї ж причини NP-завданням є пошук алгоритму розфарбовування, гарантована ефективність якого краще, ніж 4/3. Однак гарантовану ефективність, рівну двом, можна отримати в алгоритмі жадібного розфарбовування, оскільки хроматичне число графу без клешень більше, ніж половина його максимального ступеня.
Хоча не всі графи без клешень досконалі, графи без клешень задовільняють іншій властивості, пов'язаній з досконалістю. Граф називається досконалим графом домінування, якщо він має мінімальну домінуючу множину, що є незалежною множиною вершин, і якщо тією ж властивістю володіють всі породжені підграфи. Графи без клешень володіють цією властивістю. Щоб показати це, уявимо, що D — домінуюча множина в графі без клешень, і нехай v і w — дві сполучені вершини D. Тоді безліч вершин, домінованих вершиною v, але не w, повинно бути кліком (в іншому випадку v виявиться центром клешні). Якщо кожна вершина цієї кліка вже домінується принаймні одним членом множини D, то v може бути видалена з породженням меншої незалежної домінуючої множини. В іншому ж випадку v можна замінити однією з недомінуючих вершин з кліка, породжуючи домінуючу множину з меншим числом суміжних вершин. Повторюючи ці заміни, ми досягнемо домінуючої множини, що не перевершує D, так що, якщо початкове D — мінімальна домінуюча множина, процес закінчиться створенням рівної за розміром незалежної домінуючої множини.
Незважаючи на властивість досконалого домінування, визначення розміру мінімальної домінуючої множини в графі без клешень є NP-завданням. Однак в контраст з більш загальними класами графів, пошук мінімальної домінуючої множини в графі без клешень володіє [en] — завдання може бути вирішено за час, поліноміально залежний від розміру графу і експоненціально від розміру домінуючої множини.
Структура
У серії статей Чудновська і Сеймур довели структурну теорію графів без клешень, аналогічну для сімейств мінорно-замкнутих графів, доведену Робертсоном і Сеймуром, і структурній теорії для досконалих графів, яку Чудновська, Сеймур та їх співавтори використовували для доведення теореми про строго досконалий граф. Теорія занадто складна, але можливо описати декілька її наслідків. По-перше, для спеціального підкласу графів без клешень, який вони назвали квазіреберні графи (або локально квазідвудольні графи), вони стверджують, що кожен такий граф має одну з двох форм:
- Нечіткий коловий інтервальний граф — клас графів, які геометрично можна представити як точки і дуги на колі.
- Граф, який можна побудувати з мультиграфу шляхом заміни кожного ребра нечітким лінійним інтервальним графом. Це узагальнює конструкцію реберних графів, в яких кожне ребро мультиграфу замінюється вершиною. Нечіткі лінійні інтервальні графи будуються так само, як і нечіткі колові інтервальні графи, тільки на відрізку, а не на колі.
Чудновська і Сеймур класифікували довільні зв'язні графи без клешень наступним чином:
- Шість специфічних графів без клешень. Три з них є реберними графами, деякі — графи дуг кола і останні — породжені підграфи ікосаедра. Решта три вимагають додаткових визначень.
- Графи, утворені чотирма простими способами з менших графів без клешень.
- Антипризматичні графи — клас щільних графів, визначаються як графи без клешень, в яких будь-які чотири вершини породжують підграф з мінімум двома ребрами.
Більша частина їх роботи з класифікації присвячена аналізу антипризматичних графів. Граф Шлефлі, сильно регулярний граф без клешень з параметрами srg (27,16,10,8), відіграє важливу роль у цій частині аналізу. Ця структурна теорія призвела до нового просування в комбінаториці багатогранників і нових кордонів хроматичних чисел графів без клешень, а також до нових алгоритмів параметричної складності з фіксованими параметрами для домінуючих множин в графах без клешень.
Посилання
- , інформаційна система на Graph Class Inclusions
- Mugan, Jonathan William; Claw-Free Graph(англ.) на сайті Wolfram MathWorld.
Джерела
- Faudree, Flandrin, Ryjáček, 1997, с. 88.
- Faudree, Flandrin, Ryjáček, 1997.
- L. W. Beineke. Beiträge zur Graphentheorie. — Teubner, 1968. — С. 17—33.
- Faudree, Flandrin, Ryjáček, 1997, с. 89.
- Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. Архівована копія // Annals of Mathematics. — 2006. — Т. 164, вип. 1. — DOI: . з джерела 11 жовтня 2015. Процитовано 30 жовтня 2015. (англ.)
- Faudree, Flandrin, Ryjáček, 1997, с. 132.
- Alon Itai, Michael Rodeh. Finding a minimum circuit in a graph // . — 1978. — Т. 7, вип. 4. — С. 413—423. — DOI: .
- Ton Kloks, Dieter Kratsch, Haiko Müller. // Information Processing Letters. — 2000. — Т. 74, вип. 3—4. — С. 115—121. — DOI: .
- Edgar M. Palmer, Ronald C. Read, Robert W. Robinson. Counting claw-free cubic graphs // SIAM Journal on Discrete Mathematics. — 2002. — Т. 16, вип. 1. — С. 65—73. — DOI:10.1137/S0895480194274777.
- David P. Sumner. Graphs with 1-factors // Proceedings of the American Mathematical Society. — American Mathematical Society, 1974. — Т. 42, вип. 1. — С. 8—12. — DOI: .
- M. Las Vergnas. A note on matchings in graphs // Cahiers du Centre d'Études de Recherche Opérationnelle. — 1975. — Т. 17, вип. 2—3—4. — С. 257—260.
- Faudree, Flandrin, Ryjáček, 1997, с. 120—124.
- Marek Chrobak, Joseph Naor, Mark B. Novick. [en]. — Springer, 1989. — Т. 382. — С. 147—162. — DOI: .
- Jack Edmonds. Paths, Trees and Flowers // Canadian J. Math. — 1965. — Т. 17, вип. 0. — С. 449—467. — DOI: .
- Najiba Sbihi. Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile // Discrete Mathematics. — 1980. — Т. 29, вип. 1. — С. 53—76. — DOI: . (фр.)
- Faudree, Flandrin, Ryjáček, 1997, с. 133—134.
- George J. Minty. On maximal independent sets of vertices in claw-free graphs // Journal of Combinatorial Theory. Series B. — 1980. — Т. 28, вип. 3. — С. 284—304. — DOI: . (англ.)
- Daishin Nakamura, Akihisa Tamura. A revision of Minty's algorithm for finding a maximum weighted stable set of a claw-free graph // Journal of the Operations Research Society of Japan. — 2001. — Т. 44, вип. 2. — С. 194—204. з джерела 3 березня 2016. Процитовано 30 жовтня 2015. (англ.)
- Faudree, Flandrin, Ryjáček, 1997, с. 135—136.
- Faudree, Flandrin, Ryjáček, 1997, с. 124—125.
- Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Dominating set is fixed parameter tractable in claw-free graphs. — 2010.
- Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, Gerhard Woeginger. Domination when the stars are out. — 2010.
- Maria Chudnovsky, Paul Seymour. Surveys in combinatorics 2005 год. — Cambridge Univ. Press, 2005. — Т. 327. — С. 153—171.
Література
- Ralph Faudree, Evelyne Flandrin, Zdeněk Ryjáček. // Discrete Mathematics. — 1997. — Т. 164, вип. 1—3. — С. 87—147. — DOI: .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U teoriyi grafiv grafom bez kleshen nazivayetsya graf yakij ne mistit kleshen yak porodzhenih pidgrafiv Kleshnya Kleshneyu nazivayetsya povnij dvochastkovij graf K1 3 tobto zirka z troma rebrami troma listkami i odniyeyu centralnoyu vershinoyu Graf bez kleshen ce graf v yakomu kozhen porodzhenij pidgraf ne ye kleshneyu Tobto bud yaka pidmnozhina z chotiroh vershin ne ye zirkoyu z troma rebrami sho vihodyat z centralnoyi vershini Takozh mozhlivo viznachiti graf bez kleshen yak graf v yakomu okil bud yakoyi vershini utvoryuye dopovnennya grafu bez trikutnikiv Grafi bez kleshen spochatku vivchalisya yak uzagalnennya rebernih grafiv i viklikali dodatkovij interes lishe todi koli bulo zrobleno tri klyuchovih vidkrittya pro grafi bez kleshen usi zv yazni grafi bez kleshen parnogo poryadku mayut doskonali paruvannya vidkrittya polinomialnogo za chasom algoritmu poshuku maksimalnih nezalezhnih mnozhin u grafah bez kleshen opis doskonalih grafiv bez kleshen Grafam bez kleshen prisvyacheni sotni statej i kilka oglyadiv PrikladiPravilnij ikosaedr bagatogrannik vershini i rebra yakogo formuyut graf bez kleshen Rebernij graf L G bud yakogo grafu G ne maye kleshen L G mistit vershinu dlya kozhnoyi dugi G i vershini ye sumizhnimi v L G koli vidpovidni rebra mayut spilnu vershinu v G Rebernij graf L G ne mozhe mati kleshen oskilki yaksho kozhne z troh reber e1 e2 i e3 grafu G maye zagalnu vershinu z chetvertim rebrom e4 to zgidno z principom Dirihle shonajmenshe 2 rebra z e1 e2 i e3 mayut spilnu vershinu Reberni grafi mozhut buti opisani dev yatma zaboronenimi pidgrafami i kleshnya ye najprostishim z cih dev yati grafiv Ce daye motiv dlya vivchennya grafiv bez kleshen en grafi vershini yakih vidpovidayut n bitovim dvijkovim ryadkam dlya deyakogo n a dugi vidpovidayut n 1 bitnim zbigam dvoh ryadkiv ne mayut kleshen Odin iz sposobiv pokazati ce pobuduvati graf de Brojna dlya n bitovih ryadkiv yak rebernij graf vid grafu de Brejna dlya n 1 bitnih ryadkiv Dopovnennya bud yakogo grafu bez trikutnikiv ne maye kleshen Ci grafi vklyuchayut bud yakij povnij graf yak osoblivij vipadok en intervalni grafi utvoreni yak grafi peretiniv simejstv intervaliv de zhoden interval ne mistit inshij interval simejstva ne mayut kleshen oskilki chotiri takih intervali ne mozhut peretinatisya za shemoyu kleshni Vereteno Mozera graf sho maye sim vershin ta vikoristovuyetsya dlya dovedennya nizhnoyi mezhi hromatichnogo chisla ploshini ne maye kleshen Grafi deyakih bagatogrannikiv i politopiv ne mayut kleshen Syudi vhodyat graf tetraedra i vzagali bud yakij simpleks povnij graf graf oktaedra i v zagalnomu vipadku bud yakij kros politop izomorfnij graf izomorfen yakij utvoryuyetsya zavdyaki vidalennyu doskonalogo paruvannya z povnogo grafu graf pravilnogo ikosaedra i graf geksadekahorona Graf Shlefli silno regulyarnij graf sho maye 27 vershin ne maye kleshen RozpiznavannyaMozhna pereviriti bezposeredno sho zadanij graf z n vershinami i m rebrami ne maye kleshen za chas O n4 shlyahom perevirki kozhnoyi chetvirki vershin chi ne porodzhuyut voni kleshnyu Trohi efektivnishe ale skladnishe mozhna pereviriti chi ne maye graf kleshen shlyahom perevirki dlya kozhnoyi vershini grafu sho dopovnennya grafu susidiv vershini ne mistit trikutnika Graf mistit trikutnik v tomu i tilki v tomu vipadku yaksho kub matrici incindentnosti mistit nenulovij diagonalnij element tak sho poshuk trikutnika mozhe buti zdijsnenij za toj zhe asimptotichnij chas sho i mnozhennya matric n n Takim chinom pri vikoristanni algoritmu Koppersmita Vinograda zagalnij chas viznachennya chi ye u grafu kleshni stanovit O n3 376 Kloks Krach i Myuller zvernuli uvagu na te sho v grafi bez kleshen kozhna vershina maye maksimum 2 m displaystyle 2 sqrt m susidiv v inshomu vipadku zgidno z teoremoyu Turana okolicya vershini ne matime dostatnye chislo reber shob sformuvati dodatok grafu bez trikutnikiv Ce sposterezhennya dozvolyaye pereviriti susidiv z vikoristannyam zgadanogo ranishe algoritmu shvidkogo dobutku matric za toj zhe asimptotichnij chas 2 m 2 m displaystyle 2 sqrt m 2 sqrt m Najgirshij vipadok cogo algoritmu vinikaye koli W m vershin mayut po W m susidiv kozhna a reshta vershin mayut malo susidiv u comu vipadku zagalnij chas dorivnyuye m3 376 2 O m1 688 PererahuvannyaOskilki grafi bez kleshen mayut usi dopovnennya grafiv bez trikutnikiv chislo grafiv bez kleshen z n vershinami roste yak minimum z tiyeyu zh shvidkistyu sho i chislo grafiv bez trikutnikiv tobto po eksponenti vid korenya z n Chislo zv yazkovih grafiv bez kleshen z n rebrami dlya n 1 2 skladaye 1 1 2 5 14 50 191 881 4494 26389 184749 poslidovnist A022562 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Yaksho grafi nezv yazni yih chislo zbilshuyetsya 1 2 4 10 26 85 302 1285 6170 poslidovnist A086991 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Tehnika Palmera Rida i Robinsona dozvolyaye porahuvati chislo kubichnih grafiv bez kleshen duzhe efektivno sho ye nezvichnim dlya zadach na pererahuvannya grafiv ParuvannyaDovedennya Samnera sho zv yazni grafi bez kleshen parnogo poryadku mayut doskonale paruvannya vidalennya dvoh sumizhnih vershin v i w najbilsh viddalenih vid u zalishaye pidgraf zv yazkovim sho dozvolyaye prodovzhiti proces Samner i nezalezhno Las Vergnas doveli sho bud yakij zv yaznij graf bez kleshen z parnim chislom vershin maye doskonale paruvannya Tobto isnuye bezlich reber v grafi tak sho kozhna vershina ye kincevoyu vershinoyu v tochnosti odnogo rebra z paruvannya Z cogo viplivaye sho dlya rebernih grafiv sho mayut parne chislo reber mozhna rozbiti vsi rebra na shlyahi dovzhinoyu dva Doskonali paruvannya mozhut buti vikoristani dlya she odniyeyi harakteristiki grafiv bez kleshen ce tochno ti grafi v yakih bud yakij zv yaznij porodzhenij pidgraf parnogo poryadku maye doskonale paruvannya Dovedennya Samnera pokazuye sho v bud yakomu zv yazkovomu grafi bez kleshen mozhna znajti paru spoluchenih vershin vidalennya yakih zalishaye graf zv yazkovim Dlya dovedennya cogo Samner znahodit paru vershin u i v yaki yak mozhna bilshe viddaleni odin vid odnogo i vibiraye w sered susidiv vershini v viddalenu vid u naskilki mozhlivo Yak vin pokazav ni v ni w ne mozhut lezhati na najkorotshomu shlyahu vid bud yakoyi inshoyi vershini do u tak sho vidalennya vershin v i w zalishaye graf zv yazkovim Poslidovne vidalennya takih par utvoryuye doskonale paruvannya v grafi bez kleshen Ta zh sama ideya dovedennya pracyuye i v zagalnishomu vipadku yaksho u bud yaka vershina v bud yaka vershina maksimalno viddalena vid u i w bud yaka susidnya vershina dlya v maksimalno viddalena vid u Teper vidalennya v i w z grafu ne zminyuye vidstanej do u Takim chinom proces formuvannya paruvannya shlyahom znahodzhennya ta vidalennya par vw maksimalno viddalenih vid u mozhe buti zdijsnenij za linijnij chas prostim obhodom dereva poshuku vshir rozpochatogo z vershini u Hrobak Naor i Novik dali inshij linijnij za chasom algoritm zasnovanij na poshuku vglib a takozh efektivni paralelni algoritmi dlya tiyeyi zh zadachi Faudri Flandrin i Riyache otrimali kilka shozhih rezultativ zokrema r 1 zv yaznij graf sho ne mistit K1 r pidgrafiv neparnogo poryadku maye doskonali paruvannya dlya bud yakogo r 2 grafi neparnogo poryadku bez kleshen z maksimum odniyeyu vershinoyu stepeni odin mozhut buti podileni na odin neparnij cikl i paruvannya dlya bud yakogo k ne menshogo za polovinu minimalnoyi stepeni grafu bez kleshen u yakomu abo k abo chislo vershin parno graf maye k faktor yaksho graf bez kleshen ye 2k 1 zv yaznim to bud yaki k reberni paruvannya mozhut buti rozshireni do doskonalogo paruvannya Nezalezhni mnozhiniNemaksimalna nezalezhna mnozhina dvi fioletovi vershini i dopovnyuyuchij shlyah Nezalezhna mnozhina v rebernomu grafi vidpovidaye paruvannyu u vihidnomu grafi tobto naboru reber v yakomu niyaki dva rebra ne mayut spilnih tochok Yak pokazav Edmonds maksimalne paruvannya v bud yakomu grafi mozhna znajti za polinomialnij chas Sbihi rozshiriv cej algoritm tak sho novij algoritm znahodit maksimalnu nezalezhnu mnozhinu v bud yakomu grafi bez kleshen Minti vipravlenij Nakamuroyu i Tamuroyu dav inshe rozshirennya algoritmiv Edmonda dlya grafiv bez kleshen peretvoryuyuchogo zadachu na poshuk paruvannya u dopomizhnomu grafi otrimanogo iz vihidnogo grafu bez kleshen Pidhid Minti mozhe buti vikoristanij dlya virishennya za polinomialnij chas bilsh zagalnoyi zadachi znahodzhennya nezalezhnoyi mnozhini maksimalnoyi vagi Isnuye uzagalnennya cih rezultativ na shirokij klas grafiv Yak zauvazhiv Sbihi yaksho I displaystyle I nezalezhna mnozhina v grafi bez kleshen to bud yaka vershina grafu mozhe mati maksimum dvi susidni vershini z I displaystyle I tri susidni vershini utvorili b vzhe samu kleshnyu Sbihi nazivaye vershinu nasichenoyu yaksho vona maye dvi susidni vershini z I displaystyle I i nenasichenoyu yaksho vona ne nalezhit i v toj zhe chas maye menshe dvoh susidiv z I displaystyle I Zi sposterezhennya Sbihi viplivaye sho yaksho I displaystyle I i J displaystyle J ye nezalezhni mnozhini to graf porodzhenij I J displaystyle I cup J povinen mati stupin ne vishe drugogo Takim chinom vin ye ob yednannyam shlyahiv i cikliv Zokrema yaksho I displaystyle I ne maksimalna nezalezhna mnozhina vona vidriznyayetsya vid bud yakoyi maksimalnoyi nezalezhnoyi mnozhini ciklami i popovnyuyuchimi shlyahami tobto shlyahami v yakih vershini z I displaystyle I i ne z I displaystyle I cherguyutsya i u yakih obidvi kincevi vershini ne nasicheni Simetrichna riznicya grafiv I displaystyle I i popovnyuyuchogo shlyaha ye maksimalna nezalezhna mnozhina simetrichna riznicya grafiv H i G sho mayut odin i toj zhe nabir vershin V ce graf z tim zhe naborom vershin V sho mistit rebra G i H ale ne mistit zagalnih reber sho nalezhat yak G tak i H Algoritm Sbihi poslidovno zbilshuye rozmir nezalezhnoyi mnozhini shlyahom znahodzhennya popovnyuyuchih shlyahiv doki taki mozhna znajti Znahodzhennya popovnyuyuchogo shlyahu ye skladnim zavdannyam oskilki poshirennya shlyahu mozhe i ne isnuvati yaksho vin mistit rebro mizh dvoma vershinami sho ne nalezhat I displaystyle I Na shastya ce mozhe statisya tilki v dvoh vipadkah dvi sumizhni vershini mozhut buti kincevimi vershinami shlyahu abo mizh nimi lezhit odna vershina sumizhna obom Bud yaka insha sumizhna vershina prizvede do kleshni Sumizhnih kincevih vershin mozhna pozbutisya timchasovo vidalyayuchi vsi sumizhni v vershini pered poshukom popovnyuyuchogo shlyahu pochatkivcya v v Yaksho znajdenij shlyah ne bude vhoditi u vershinu v mozhna vidaliti jogo z grafu do kincya algoritmu Pislya takoyi redukciyi grafu zavdannya mozhe buti opisano v terminah en hocha Sbihi i ne koristuvavsya ciyeyu terminologiyeyu Graf peremikach ce nenapravlenij graf v yakomu dugi bud yakoyi vershini rozdileni na dvi grupi i bud yakij shlyah sho prohodit cherez vershinu zobov yazanij mistiti rebra z oboh grup Mozhna pobuduvati graf peremikach na mnozhini nasichenih i nenasichenih vershin grafu bez kleshen rebra yakogo z yednuyut vershini yaksho voni ne ye sumizhnimi u vihidnomu grafi i isnuye shlyah dovzhini 2 mizh nimi sho prohodit cherez vershinu z I Dvi mnozhini reber v kozhnij vershini utvoryuyutsya dvoma vershinami I cherez yaki ci shlyahi dovzhinoyu 2 prohodyat Shlyah u grafi peremikachi mizh dvoma nenasichenimi vershinami vidpovidaye popovnyuyuchomu shlyahu u vihidnomu grafi Graf peremikach maye kvadratichnu skladnist i shlyah u nomu mozhe buti znajdenij za linijnij chas a za ves chas roboti algoritmu mozhut znadobitisya O n popovnyuyuchih shlyahiv yaki neobhidno znajti Takim chinom algoritm Sbihi vimagaye O n3 chasu roboti Rozfarbovuvannya kliki i dominuvannyaDoskonalij graf ce graf v yakomu hromatichne chislo dorivnyuye rozmiru maksimalnoyi kliki i v yakomu cya rivnist zberigayetsya u vsih porodzhenih pidgrafah Vidomo zi silnoyi teoremi pro doskonali grafi sho doskonali grafi mozhut buti oharakterizovani yak grafi sho ne mayut neparnih cikliv chi dopovnen neparnim ciklam tak zvani neparni diri yak indukovanih pidgrafiv Prote bagato rokiv cej fakt zalishavsya gipotezoyu dovedenoyu tilki dlya specialnih pidklasiv grafiv Odnim z takih pidklasiv bulo simejstvo grafiv bez kleshen kilka avtoriv viyavili sho grafi bez kleshen i bez neparnih cikliv i dirok doskonali Doskonalist grafu bez kleshen mozhe buti perevirena za polinomialnij chas U doskonalomu grafi bez kleshen okolicya bud yakoyi vershini utvoryuye dopovnennya dvochastkovogo grafu Mozhna rozfarbuvati doskonalij graf bez kleshen abo znajti v nomu maksimalnu kliku za polinomialnij chas Yaksho graf bez kleshen ne doskonalij zavdannya poshuku maksimalnoyi kliki staye NP zadacheyu Zadacha znahodzhennya optimalnogo rozfarbuvannya takogo grafu takozh ye NP zadacheyu oskilki cherez rebernij graf cya zadacha uzagalnyuye NP zavdannya obchislennya hromatichnogo chisla grafu Z tiyeyi zh prichini NP zavdannyam ye poshuk algoritmu rozfarbovuvannya garantovana efektivnist yakogo krashe nizh 4 3 Odnak garantovanu efektivnist rivnu dvom mozhna otrimati v algoritmi zhadibnogo rozfarbovuvannya oskilki hromatichne chislo grafu bez kleshen bilshe nizh polovina jogo maksimalnogo stupenya Hocha ne vsi grafi bez kleshen doskonali grafi bez kleshen zadovilnyayut inshij vlastivosti pov yazanij z doskonalistyu Graf nazivayetsya doskonalim grafom dominuvannya yaksho vin maye minimalnu dominuyuchu mnozhinu sho ye nezalezhnoyu mnozhinoyu vershin i yaksho tiyeyu zh vlastivistyu volodiyut vsi porodzheni pidgrafi Grafi bez kleshen volodiyut ciyeyu vlastivistyu Shob pokazati ce uyavimo sho D dominuyucha mnozhina v grafi bez kleshen i nehaj v i w dvi spolucheni vershini D Todi bezlich vershin dominovanih vershinoyu v ale ne w povinno buti klikom v inshomu vipadku v viyavitsya centrom kleshni Yaksho kozhna vershina ciyeyi klika vzhe dominuyetsya prinajmni odnim chlenom mnozhini D to v mozhe buti vidalena z porodzhennyam menshoyi nezalezhnoyi dominuyuchoyi mnozhini V inshomu zh vipadku v mozhna zaminiti odniyeyu z nedominuyuchih vershin z klika porodzhuyuchi dominuyuchu mnozhinu z menshim chislom sumizhnih vershin Povtoryuyuchi ci zamini mi dosyagnemo dominuyuchoyi mnozhini sho ne perevershuye D tak sho yaksho pochatkove D minimalna dominuyucha mnozhina proces zakinchitsya stvorennyam rivnoyi za rozmirom nezalezhnoyi dominuyuchoyi mnozhini Nezvazhayuchi na vlastivist doskonalogo dominuvannya viznachennya rozmiru minimalnoyi dominuyuchoyi mnozhini v grafi bez kleshen ye NP zavdannyam Odnak v kontrast z bilsh zagalnimi klasami grafiv poshuk minimalnoyi dominuyuchoyi mnozhini v grafi bez kleshen volodiye en zavdannya mozhe buti virisheno za chas polinomialno zalezhnij vid rozmiru grafu i eksponencialno vid rozmiru dominuyuchoyi mnozhini StrukturaU seriyi statej Chudnovska i Sejmur doveli strukturnu teoriyu grafiv bez kleshen analogichnu dlya simejstv minorno zamknutih grafiv dovedenu Robertsonom i Sejmurom i strukturnij teoriyi dlya doskonalih grafiv yaku Chudnovska Sejmur ta yih spivavtori vikoristovuvali dlya dovedennya teoremi pro strogo doskonalij graf Teoriya zanadto skladna ale mozhlivo opisati dekilka yiyi naslidkiv Po pershe dlya specialnogo pidklasu grafiv bez kleshen yakij voni nazvali kvazireberni grafi abo lokalno kvazidvudolni grafi voni stverdzhuyut sho kozhen takij graf maye odnu z dvoh form Nechitkij kolovij intervalnij graf klas grafiv yaki geometrichno mozhna predstaviti yak tochki i dugi na koli Graf yakij mozhna pobuduvati z multigrafu shlyahom zamini kozhnogo rebra nechitkim linijnim intervalnim grafom Ce uzagalnyuye konstrukciyu rebernih grafiv v yakih kozhne rebro multigrafu zaminyuyetsya vershinoyu Nechitki linijni intervalni grafi buduyutsya tak samo yak i nechitki kolovi intervalni grafi tilki na vidrizku a ne na koli Chudnovska i Sejmur klasifikuvali dovilni zv yazni grafi bez kleshen nastupnim chinom Shist specifichnih grafiv bez kleshen Tri z nih ye rebernimi grafami deyaki grafi dug kola i ostanni porodzheni pidgrafi ikosaedra Reshta tri vimagayut dodatkovih viznachen Grafi utvoreni chotirma prostimi sposobami z menshih grafiv bez kleshen Antiprizmatichni grafi klas shilnih grafiv viznachayutsya yak grafi bez kleshen v yakih bud yaki chotiri vershini porodzhuyut pidgraf z minimum dvoma rebrami Bilsha chastina yih roboti z klasifikaciyi prisvyachena analizu antiprizmatichnih grafiv Graf Shlefli silno regulyarnij graf bez kleshen z parametrami srg 27 16 10 8 vidigraye vazhlivu rol u cij chastini analizu Cya strukturna teoriya prizvela do novogo prosuvannya v kombinatorici bagatogrannikiv i novih kordoniv hromatichnih chisel grafiv bez kleshen a takozh do novih algoritmiv parametrichnoyi skladnosti z fiksovanimi parametrami dlya dominuyuchih mnozhin v grafah bez kleshen Posilannya informacijna sistema na Graph Class Inclusions Mugan Jonathan William Claw Free Graph angl na sajti Wolfram MathWorld DzherelaFaudree Flandrin Ryjacek 1997 s 88 Faudree Flandrin Ryjacek 1997 L W Beineke Beitrage zur Graphentheorie Teubner 1968 S 17 33 Faudree Flandrin Ryjacek 1997 s 89 Maria Chudnovsky Neil Robertson Paul Seymour Robin Thomas Arhivovana kopiya Annals of Mathematics 2006 T 164 vip 1 DOI 10 4007 annals 2006 164 51 z dzherela 11 zhovtnya 2015 Procitovano 30 zhovtnya 2015 angl Faudree Flandrin Ryjacek 1997 s 132 Alon Itai Michael Rodeh Finding a minimum circuit in a graph 1978 T 7 vip 4 S 413 423 DOI 10 1137 0207033 Ton Kloks Dieter Kratsch Haiko Muller Information Processing Letters 2000 T 74 vip 3 4 S 115 121 DOI 10 1016 S0020 0190 00 00047 8 Edgar M Palmer Ronald C Read Robert W Robinson Counting claw free cubic graphs SIAM Journal on Discrete Mathematics 2002 T 16 vip 1 S 65 73 DOI 10 1137 S0895480194274777 David P Sumner Graphs with 1 factors Proceedings of the American Mathematical Society American Mathematical Society 1974 T 42 vip 1 S 8 12 DOI 10 2307 2039666 M Las Vergnas A note on matchings in graphs Cahiers du Centre d Etudes de Recherche Operationnelle 1975 T 17 vip 2 3 4 S 257 260 Faudree Flandrin Ryjacek 1997 s 120 124 Marek Chrobak Joseph Naor Mark B Novick en Springer 1989 T 382 S 147 162 DOI 10 1007 3 540 51542 9 13 Jack Edmonds Paths Trees and Flowers Canadian J Math 1965 T 17 vip 0 S 449 467 DOI 10 4153 CJM 1965 045 4 Najiba Sbihi Algorithme de recherche d un stable de cardinalite maximum dans un graphe sans etoile Discrete Mathematics 1980 T 29 vip 1 S 53 76 DOI 10 1016 0012 365X 90 90287 R fr Faudree Flandrin Ryjacek 1997 s 133 134 George J Minty On maximal independent sets of vertices in claw free graphs Journal of Combinatorial Theory Series B 1980 T 28 vip 3 S 284 304 DOI 10 1016 0095 8956 80 90074 X angl Daishin Nakamura Akihisa Tamura A revision of Minty s algorithm for finding a maximum weighted stable set of a claw free graph Journal of the Operations Research Society of Japan 2001 T 44 vip 2 S 194 204 z dzherela 3 bereznya 2016 Procitovano 30 zhovtnya 2015 angl Faudree Flandrin Ryjacek 1997 s 135 136 Faudree Flandrin Ryjacek 1997 s 124 125 Marek Cygan Geevarghese Philip Marcin Pilipczuk Michal Pilipczuk Jakub Onufry Wojtaszczyk Dominating set is fixed parameter tractable in claw free graphs 2010 Danny Hermelin Matthias Mnich Erik Jan van Leeuwen Gerhard Woeginger Domination when the stars are out 2010 Maria Chudnovsky Paul Seymour Surveys in combinatorics 2005 god Cambridge Univ Press 2005 T 327 S 153 171 LiteraturaRalph Faudree Evelyne Flandrin Zdenek Ryjacek Discrete Mathematics 1997 T 164 vip 1 3 S 87 147 DOI 10 1016 S0012 365X 96 00045 3