Розщеплюваний граф, розділений на кліку і незалежну множину.
У теорії графіврозщеплюваним графом називають граф, у якому вершини можна розділити на кліку і незалежну множину. Розщеплювані графи вперше вивчали Фелдес і Гаммер[1][2], і незалежно ввели Тишкевич і Черняк[3][4].
Розщеплюваний граф може мати кілька розкладів на кліку та незалежну множину. Так, шлях a-b-c є розщеплюваним і його можна розбити трьома різними способами:
кліка {a,b} і незалежна множина {c}
кліка {b,c} і незалежне безліч {a}
кліка {b} і незалежне безліч {a,c}
Розщеплювані графи можна охарактеризувати в термінах заборонених підграфів — граф розщеплюваний тоді й лише тоді, коли жодний породжений підграф не є циклом з чотирма або п'ятьма вершинами, а також немає пари незв'язних вершин (тобто доповнення циклу з 4 вершин)[5][6].
Зв'язок з іншими сімействами графів
За визначенням, клас розщеплюваних графів замкнутий відносно операції доповнення[7]. Ще одна характеристика розщеплюваних графів, що залучає доповнення — це хордальні графи, доповнення яких також хордальні[8]. Оскільки хордальні графи є графами перетинів піддерев дерев, розщеплювані графи, є графами перетинів різних підзірок зірок[9]. Майже всі хордальні графи є розщеплюваними графами. Тобто, при прямуванні n до нескінченності, відношення числа хордальних графів з n вершинами до числа розщеплюваних графів прямує до одиниці[10].
Оскільки хордальні графи є досконалими, то розщеплювані графи теж досконалі. Подвійні розщеплювані графи, сімейство графів, отриманих з розщеплюваних графів подвоєнням числа вершин (так що кліка дає антисполучення — множину ребер, розташованих на відстані не більше 2 одне від одного, а незалежна множина перетворюється на парування), з'являється як один із п'яти основних класів досконалих графів, з яких можна побудувати всі інші на доведення сильної теореми про досконалі графи[11].
Якщо граф і розщеплюваний, і інтервальний, його доповнення є і розщеплюваним, і графом порівнянності, і навпаки. Розщеплювані графи порівнянності, а отже й розщеплювані інтервальні графи, можна описати в термінах трьох заборонених підграфів[12]. Розщеплювані кографи — це точно порогові графи, а розщеплювані графи перестановки — це точно інтервальні графи, доповнення яких теж є інтервальними[13]. Кохроматичне число[en] розщеплюваних графів дорівнює 2.
Максимальна кліка та максимальна незалежна множина
Нехай G — розщеплюваний граф, розкладений на кліку C і незалежну множину I. Тоді будь-яка максимальна кліка в розщеплюваному графі або збігається із C або є околом вершини з I. Отже, в розщеплюваному графі легко знайти максимальну кліку і, крім того, максимальну незалежну множину. В будь-якому розщеплюваному графі має виконуватися одне з таких тверджень[14]:
Існує вершина x в I, така що C ∪ { x } є повним. У цьому випадку, C ∪ { x } — максимальна кліка і I — максимальна незалежна множина.
Існує вершина x в C, така що I ∪ { x } — незалежна множина. У цьому випадку I ∪ { x } — максимальна незалежна множина і C — максимальна кліка.
C є найбільшою клікою та I найбільшою незалежною множиною. У цьому випадку G має єдиний розклад (C, I) на кліку та незалежну множину, C є максимальною клікою, і I є максимальною незалежною множиною.
Деякі інші оптимізаційні задачі, NP-повні на загальніших сімействах графів, включно з розфарбовуванням, розв'язуються просто на розщеплюваних графах.
Послідовності степенів
Одна з чудових властивостей розщеплюваних графів — це те, що їх можна розпізнати чисто за послідовностями степенів їхніх вершин. Нехай d1 ≥ d2 ≥ … ≥ dn — послідовність степенів вершин графа G і m — найбільше значення i для якого di ≥ i — 1. Тоді G є розщеплюваним графом тоді й лише тоді, коли
Якщо це виконується, то m вершин з найбільшими степенями утворюють максимальну кліку G, а решта вершин дадуть незалежну множину[15].
Підрахунок розщеплюваних графів
Ройл[16] показав, що розщеплювані графи з n вершинами один до одного відповідають деяким сімействам Спернера[en]. Скориставшись цим, він знайшов формулу числа (неізоморфних) розщеплюваних графів з n вершинами. Для малих значень n, починаючи від n = 1, ці числа дорівнюють
↑Фелдес і Гаммер (Földes, Hammer, 1977a) дали загальніше визначення, в якому графи, які вони називають розщеплюваними, включають також двочасткові графи (тобто, графи, розбиті на дві незалежних множини) і доповнення двочасткових графів (тобто, графи, які можна розкласти на дві кліки). Фелдес і Гаммер (Földes, Hammer, 1977b) дають визначення, наведене тут, і використовуване в подальшій літературі, наприклад у Брандштедта, Лі та Спінрада (Brandstädt, Le, Spinrad, 1999).
E. A. Bender, L. B. Richmond, N. C. Wormald. Almost all chordal graphs split // J. Austral. Math. Soc.. — 1985. — Т. 38, вип. 2. — С. 214—221. — (A). — DOI:10.1017/S1446788700023077.
Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — ISBN 0-89871-432-X.
Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — ISBN 0-12-289260-7.
Peter L. Hammer, Bruno Simeone. The splittance of a graph // Combinatorica. — 1981. — Т. 1, вип. 3. — С. 275—284. — DOI:10.1007/BF02579333.
F. R. McMorris, D. R. Shier. Representing chordal graphs on K1,n // Commentationes Mathematicae Universitatis Carolinae. — 1983. — Т. 24. — С. 489—494.
Регина И. Тышкевич. Каноническое разложение графа // Доклады Академии Наук БССР. — 1980. — Т. 24, вип. 8. — С. 677—679.
Р. И. Тышкевич, А. А. Черняк. Каноническое разложение графа, определяемого степенями его вершин // Известия АН БССР, сер. физ.-мат. наук. — 1979. — Т. 5. — С. 14—26.
Р. И. Тышкевич, О. И. Мельников, В. М. Котов. О графах и степенных последовательностях: каноническое разложение // Кибернетика. — 1981. — Т. 6. — С. 5—8.
H.-J. Voss. Note on a paper of McMorris and Shier // Commentationes Mathematicae Universitatis Carolinae. — 1985. — Т. 26. — С. 319—322.
