Перейти до вмісту

Розщеплюваний граф

Матеріал з Вікіпедії — вільної енциклопедії.
Розщеплюваний граф, розділений на кліку і незалежну множину.

У теорії графів розщеплюваним графом називають граф, у якому вершини можна розділити на кліку і незалежну множину. Розщеплювані графи вперше вивчали Фелдес і Гаммер[1][2], і незалежно ввели Тишкевич і Черняк[3][4].

Розщеплюваний граф може мати кілька розкладів на кліку та незалежну множину. Так, шлях a-b-c є розщеплюваним і його можна розбити трьома різними способами:

  1. кліка {a,b} і незалежна множина {c}
  2. кліка {b,c} і незалежне безліч {a}
  3. кліка {b} і незалежне безліч {a,c}

Розщеплювані графи можна охарактеризувати в термінах заборонених підграфів — граф розщеплюваний тоді й лише тоді, коли жодний породжений підграф не є циклом з чотирма або п'ятьма вершинами, а також немає пари незв'язних вершин (тобто доповнення циклу з 4 вершин)[5][6].

Зв'язок з іншими сімействами графів

[ред. | ред. код]

За визначенням, клас розщеплюваних графів замкнутий відносно операції доповнення[7]. Ще одна характеристика розщеплюваних графів, що залучає доповнення — це хордальні графи, доповнення яких також хордальні[8]. Оскільки хордальні графи є графами перетинів піддерев дерев, розщеплювані графи, є графами перетинів різних підзірок зірок[9]. Майже всі хордальні графи є розщеплюваними графами. Тобто, при прямуванні n до нескінченності, відношення числа хордальних графів з n вершинами до числа розщеплюваних графів прямує до одиниці[10].

Оскільки хордальні графи є досконалими, то розщеплювані графи теж досконалі. Подвійні розщеплювані графи, сімейство графів, отриманих з розщеплюваних графів подвоєнням числа вершин (так що кліка дає антисполучення — множину ребер, розташованих на відстані не більше 2 одне від одного, а незалежна множина перетворюється на парування), з'являється як один із п'яти основних класів досконалих графів, з яких можна побудувати всі інші на доведення сильної теореми про досконалі графи[11].

Якщо граф і розщеплюваний, і інтервальний, його доповнення є і розщеплюваним, і графом порівнянності, і навпаки. Розщеплювані графи порівнянності, а отже й розщеплювані інтервальні графи, можна описати в термінах трьох заборонених підграфів[12]. Розщеплювані кографи — це точно порогові графи, а розщеплювані графи перестановки — це точно інтервальні графи, доповнення яких теж є інтервальними[13]. Кохроматичне число[en] розщеплюваних графів дорівнює 2.

Максимальна кліка та максимальна незалежна множина

[ред. | ред. код]

Нехай G — розщеплюваний граф, розкладений на кліку C і незалежну множину I. Тоді будь-яка максимальна кліка в розщеплюваному графі або збігається із C або є околом вершини з I. Отже, в розщеплюваному графі легко знайти максимальну кліку і, крім того, максимальну незалежну множину. В будь-якому розщеплюваному графі має виконуватися одне з таких тверджень[14]:

  1. Існує вершина x в I, така що C ∪ { x } є повним. У цьому випадку, C ∪ { x } — максимальна кліка і I — максимальна незалежна множина.
  2. Існує вершина x в C, така що I ∪ { x } — незалежна множина. У цьому випадку I ∪ { x } — максимальна незалежна множина і C — максимальна кліка.
  3. C є найбільшою клікою та I найбільшою незалежною множиною. У цьому випадку G має єдиний розклад (C, I) на кліку та незалежну множину, C є максимальною клікою, і I є максимальною незалежною множиною.

Деякі інші оптимізаційні задачі, NP-повні на загальніших сімействах графів, включно з розфарбовуванням, розв'язуються просто на розщеплюваних графах.

Послідовності степенів

[ред. | ред. код]

Одна з чудових властивостей розщеплюваних графів — це те, що їх можна розпізнати чисто за послідовностями степенів їхніх вершин. Нехай d 1 ≥ d 2 ≥ … ≥ d n — послідовність степенів вершин графа G і m — найбільше значення i для якого d i ≥ i — 1. Тоді G є розщеплюваним графом тоді й лише тоді, коли

Якщо це виконується, то m вершин з найбільшими степенями утворюють максимальну кліку G, а решта вершин дадуть незалежну множину[15].

Підрахунок розщеплюваних графів

[ред. | ред. код]

Ройл[16] показав, що розщеплювані графи з n вершинами один до одного відповідають деяким сімействам Спернера[en]. Скориставшись цим, він знайшов формулу числа (неізоморфних) розщеплюваних графів з n вершинами. Для малих значень n, починаючи від n = 1, ці числа дорівнюють

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, … послідовність A048194 з Онлайн енциклопедії послідовностей цілих чисел, OEIS.

Це перерахування раніше довели Тишкевич та Черняк[17].

Примітки

[ред. | ред. код]
  1. ↑ Földes, Hammer, 1977a.
  2. ↑ Földes, Hammer, 1977b.
  3. ↑ Тышкевич, Черняк, 1979.
  4. ↑ Фелдес і Гаммер (Földes, Hammer, 1977a) дали загальніше визначення, в якому графи, які вони називають розщеплюваними, включають також двочасткові графи (тобто, графи, розбиті на дві незалежних множини) і доповнення двочасткових графів (тобто, графи, які можна розкласти на дві кліки). Фелдес і Гаммер (Földes, Hammer, 1977b) дають визначення, наведене тут, і використовуване в подальшій літературі, наприклад у Брандштедта, Лі та Спінрада (Brandstädt, Le, Spinrad, 1999).
  5. ↑ Földes, Hammer, 1977a; Golumbic, 1980, теорема 6.3, стор. 151.
  6. ↑ Pinar Heggernes, Dieter Kratsch. Linear-time certifying recognition algorithms and forbidden induced subgraphs // Nordic Journal of Computing. — 2007. — Т. 14 (26 грудня).
  7. ↑ Golumbic, 1980, теорема 6.1, стор. 150.
  8. ↑ Földes, Hammer, 1977a; Golumbic, 1980, теорема 6.3, стор. 151; Brandstädt, Le, Spinrad, 1999, теорема 3.2.3, стор. 41.
  9. ↑ McMorris, Shier, 1983; Voss, 1985; Brandstädt, Le, Spinrad, 1999, теорема 4.4.2, стор. 52.
  10. ↑ Bender, Richmond, Wormald, 1985.
  11. ↑ Chudnovsky, Robertson, Seymour, Thomas, 2006.
  12. ↑ Földes, Hammer, 1977b; Golumbic, 1980, теорема 9.7, стор. 212.
  13. ↑ Brandstädt, Le, Spinrad, 1999, наслідок 7.1.1 стор. 106 і теорема 7.1.2 стор. 107.
  14. ↑ Hammer, Simeone, 1981; Golumbic, 1980, теорема 6.2, стор. 150.
  15. ↑ Hammer, Simeone, 1981; Тышкевич, 1980; Тышкевич, Мельников, Котов, 1981; Golumbic, 1980, теорема 6.7 і наслідок 6.8, стор. 154; Brandstädt, Le, Spinrad, 1999, теорема 13.3.2, стор. 203. Merris, 2003 подальший розгляд послідовності степенів розщеплюваних графів.
  16. ↑ Royle, 2000.
  17. ↑ Тышкевич, Черняк, 1990.

Література

[ред. | ред. код]
  • 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.
  • Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong perfect graph theorem // Annals of Mathematics. — 2006. — Т. 164, вип. 1. — С. 51—229. — DOI:10.4007/annals.2006.164.51.
  • Stéphane Földes, Peter L. Hammer. Congressus Numerantium. — Winnipeg : Utilitas Math, 1977a. — Т. XIX. — С. 311—315.
  • Stéphane Földes, Peter L. Hammer. Split graphs having Dilworth number two // Canadian Journal of Mathematics. — 1977b. — Т. 29, вип. 3. — С. 666—672. — DOI:10.4153/CJM-1977-069-1.
  • 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.
  • Russell Merris. Split graphs // European Journal of Combinatorics. — 2003. — Т. 24, вип. 4. — С. 413—430. — DOI:10.1016/S0195-6698(03)00030-1.
  • Gordon F. Royle. Counting set covers and split graphs // Journal of Integer Sequences. — 2000. — Т. 3, вип. 2. — С. 00.2.6.
  • Регина И. Тышкевич. Каноническое разложение графа // Доклады Академии Наук БССР. — 1980. — Т. 24, вип. 8. — С. 677—679.
  • Р. И. Тышкевич, А. А. Черняк. Каноническое разложение графа, определяемого степенями его вершин // Известия АН БССР, сер. физ.-мат. наук. — 1979. — Т. 5. — С. 14—26.
  • Р. И. Тышкевич, А. А. Черняк. Еще один метод перечисления непомеченных комбинаторных объектов // Matem. Zametki. — 1990. — Т. 48, вип. 6. — С. 98—105.
  • Р. И. Тышкевич, О. И. Мельников, В. М. Котов. О графах и степенных последовательностях: каноническое разложение // Кибернетика. — 1981. — Т. 6. — С. 5—8.
  • H.-J. Voss. Note on a paper of McMorris and Shier // Commentationes Mathematicae Universitatis Carolinae. — 1985. — Т. 26. — С. 319—322.

Додаткова література

[ред. | ред. код]
Отримано з https://uk.wikipedia.org/w/index.php?title=Розщеплюваний_граф&oldid=36556784