Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

У теорії графів розщеплюваним графом називають граф у якому вершини можна розділити на кліку і незалежну множину Розщепл

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

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

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

image
Розщеплюваний граф, розділений на кліку і незалежну множину.

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

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

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

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

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

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

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

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

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

  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 є розщеплюваним графом тоді й лише тоді, коли

image

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

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

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

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

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

Примітки

  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 (18 червня).
  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. — .
  • 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 // . — 1977b. — Т. 29, вип. 3. — С. 666—672. — DOI:10.4153/CJM-1977-069-1.
  • Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — .
  • Peter L. Hammer, Bruno Simeone. The splittance of a graph // . — 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 // . — 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.

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

  • Розділ про розщеплювані графи в книзі [en] «Algorithmic Graph Theory and Perfect Graphs».

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

U teoriyi grafiv rozsheplyuvanim grafom nazivayut graf u yakomu vershini mozhna rozdiliti na kliku i nezalezhnu mnozhinu Rozsheplyuvani grafi vpershe vivchali Feldes i Gammer i nezalezhno vveli Tishkevich i Chernyak Rozsheplyuvanij graf rozdilenij na kliku i nezalezhnu mnozhinu Rozsheplyuvanij graf mozhe mati kilka rozkladiv na kliku ta nezalezhnu mnozhinu Tak shlyah a b c ye rozsheplyuvanim i jogo mozhna rozbiti troma riznimi sposobami klika a b i nezalezhna mnozhina c klika b c i nezalezhne bezlich a klika b i nezalezhne bezlich a c Rozsheplyuvani grafi mozhna oharakterizuvati v terminah zaboronenih pidgrafiv graf rozsheplyuvanij todi j lishe todi koli zhodnij porodzhenij pidgraf ne ye ciklom z chotirma abo p yatma vershinami a takozh nemaye pari nezv yaznih vershin tobto dopovnennya ciklu z 4 vershin Zv yazok z inshimi simejstvami grafivZa viznachennyam klas rozsheplyuvanih grafiv zamknutij vidnosno operaciyi dopovnennya She odna harakteristika rozsheplyuvanih grafiv sho zaluchaye dopovnennya ce hordalni grafi dopovnennya yakih takozh hordalni Oskilki hordalni grafi ye grafami peretiniv pidderev derev rozsheplyuvani grafi ye grafami peretiniv riznih pidzirok zirok Majzhe vsi hordalni grafi ye rozsheplyuvanimi grafami Tobto pri pryamuvanni n do neskinchennosti vidnoshennya chisla hordalnih grafiv z n vershinami do chisla rozsheplyuvanih grafiv pryamuye do odinici Oskilki hordalni grafi ye doskonalimi to rozsheplyuvani grafi tezh doskonali Podvijni rozsheplyuvani grafi simejstvo grafiv otrimanih z rozsheplyuvanih grafiv podvoyennyam chisla vershin tak sho klika daye antispoluchennya mnozhinu reber roztashovanih na vidstani ne bilshe 2 odne vid odnogo a nezalezhna mnozhina peretvoryuyetsya na paruvannya z yavlyayetsya yak odin iz p yati osnovnih klasiv doskonalih grafiv z yakih mozhna pobuduvati vsi inshi na dovedennya silnoyi teoremi pro doskonali grafi Yaksho graf i rozsheplyuvanij i intervalnij jogo dopovnennya ye i rozsheplyuvanim i grafom porivnyannosti i navpaki Rozsheplyuvani grafi porivnyannosti a otzhe j rozsheplyuvani intervalni grafi mozhna opisati v terminah troh zaboronenih pidgrafiv Rozsheplyuvani kografi ce tochno porogovi grafi a rozsheplyuvani grafi perestanovki ce tochno intervalni grafi dopovnennya yakih tezh ye intervalnimi en rozsheplyuvanih grafiv dorivnyuye 2 Maksimalna klika ta maksimalna nezalezhna mnozhinaNehaj G rozsheplyuvanij graf rozkladenij na kliku C i nezalezhnu mnozhinu I Todi bud yaka maksimalna klika v rozsheplyuvanomu grafi abo zbigayetsya iz C abo ye okolom vershini z I Otzhe v rozsheplyuvanomu grafi legko znajti maksimalnu kliku i krim togo maksimalnu nezalezhnu mnozhinu V bud yakomu rozsheplyuvanomu grafi maye vikonuvatisya odne z takih tverdzhen Isnuye vershina x v I taka sho C x ye povnim U comu vipadku C x maksimalna klika i I maksimalna nezalezhna mnozhina Isnuye vershina x v C taka sho I x nezalezhna mnozhina U comu vipadku I x maksimalna nezalezhna mnozhina i C maksimalna klika C ye najbilshoyu klikoyu ta I najbilshoyu nezalezhnoyu mnozhinoyu U comu vipadku G maye yedinij rozklad C I na kliku ta nezalezhnu mnozhinu C ye maksimalnoyu klikoyu i I ye maksimalnoyu nezalezhnoyu mnozhinoyu Deyaki inshi optimizacijni zadachi NP povni na zagalnishih simejstvah grafiv vklyuchno z rozfarbovuvannyam rozv yazuyutsya prosto na rozsheplyuvanih grafah Poslidovnosti stepenivOdna z chudovih vlastivostej rozsheplyuvanih grafiv ce te sho yih mozhna rozpiznati chisto za poslidovnostyami stepeniv yihnih vershin Nehaj d 1 d 2 d n poslidovnist stepeniv vershin grafa G i m najbilshe znachennya i dlya yakogo d i i 1 Todi G ye rozsheplyuvanim grafom todi j lishe todi koli i 1 m d i m m 1 i m 1 n d i displaystyle sum i 1 m d i m m 1 sum i m 1 n d i Yaksho ce vikonuyetsya to m vershin z najbilshimi stepenyami utvoryuyut maksimalnu kliku G a reshta vershin dadut nezalezhnu mnozhinu Pidrahunok rozsheplyuvanih grafivRojl pokazav sho rozsheplyuvani grafi z n vershinami odin do odnogo vidpovidayut deyakim en Skoristavshis cim vin znajshov formulu chisla neizomorfnih rozsheplyuvanih grafiv z n vershinami Dlya malih znachen n pochinayuchi vid n 1 ci chisla dorivnyuyut 1 2 4 9 21 56 164 557 2223 10766 64956 501696 poslidovnist A048194 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Ce pererahuvannya ranishe doveli Tishkevich ta Chernyak PrimitkiFoldes Hammer 1977a Foldes Hammer 1977b Tyshkevich Chernyak 1979 Feldes i Gammer Foldes Hammer 1977a dali zagalnishe viznachennya v yakomu grafi yaki voni nazivayut rozsheplyuvanimi vklyuchayut takozh dvochastkovi grafi tobto grafi rozbiti na dvi nezalezhnih mnozhini i dopovnennya dvochastkovih grafiv tobto grafi yaki mozhna rozklasti na dvi kliki Feldes i Gammer Foldes Hammer 1977b dayut viznachennya navedene tut i vikoristovuvane v podalshij literaturi napriklad u Brandshtedta Li ta Spinrada Brandstadt Le Spinrad 1999 Foldes Hammer 1977a Golumbic 1980 teorema 6 3 stor 151 Pinar Heggernes Dieter Kratsch Linear time certifying recognition algorithms and forbidden induced subgraphs Nordic Journal of Computing 2007 T 14 18 chervnya Golumbic 1980 teorema 6 1 stor 150 Foldes Hammer 1977a Golumbic 1980 teorema 6 3 stor 151 Brandstadt Le Spinrad 1999 teorema 3 2 3 stor 41 McMorris Shier 1983 Voss 1985 Brandstadt Le Spinrad 1999 teorema 4 4 2 stor 52 Bender Richmond Wormald 1985 Chudnovsky Robertson Seymour Thomas 2006 Foldes Hammer 1977b Golumbic 1980 teorema 9 7 stor 212 Brandstadt Le Spinrad 1999 naslidok 7 1 1 stor 106 i teorema 7 1 2 stor 107 Hammer Simeone 1981 Golumbic 1980 teorema 6 2 stor 150 Hammer Simeone 1981 Tyshkevich 1980 Tyshkevich Melnikov Kotov 1981 Golumbic 1980 teorema 6 7 i naslidok 6 8 stor 154 Brandstadt Le Spinrad 1999 teorema 13 3 2 stor 203 Merris 2003 podalshij rozglyad poslidovnosti stepeniv rozsheplyuvanih grafiv Royle 2000 Tyshkevich Chernyak 1990 LiteraturaE A Bender L B Richmond N C Wormald Almost all chordal graphs split J Austral Math Soc 1985 T 38 vip 2 S 214 221 A DOI 10 1017 S1446788700023077 Andreas Brandstadt 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 T 164 vip 1 S 51 229 DOI 10 4007 annals 2006 164 51 Stephane Foldes Peter L Hammer Congressus Numerantium Winnipeg Utilitas Math 1977a T XIX S 311 315 Stephane Foldes Peter L Hammer Split graphs having Dilworth number two 1977b T 29 vip 3 S 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 1981 T 1 vip 3 S 275 284 DOI 10 1007 BF02579333 F R McMorris D R Shier Representing chordal graphs on K1 n Commentationes Mathematicae Universitatis Carolinae 1983 T 24 S 489 494 Russell Merris Split graphs 2003 T 24 vip 4 S 413 430 DOI 10 1016 S0195 6698 03 00030 1 Gordon F Royle Counting set covers and split graphs Journal of Integer Sequences 2000 T 3 vip 2 S 00 2 6 Regina I Tyshkevich Kanonicheskoe razlozhenie grafa 1980 T 24 vip 8 S 677 679 R I Tyshkevich A A Chernyak Kanonicheskoe razlozhenie grafa opredelyaemogo stepenyami ego vershin Izvestiya AN BSSR ser fiz mat nauk 1979 T 5 S 14 26 R I Tyshkevich A A Chernyak Eshe odin metod perechisleniya nepomechennyh kombinatornyh obektov Matem Zametki 1990 T 48 vip 6 S 98 105 R I Tyshkevich O I Melnikov V M Kotov O grafah i stepennyh posledovatelnostyah kanonicheskoe razlozhenie Kibernetika 1981 T 6 S 5 8 H J Voss Note on a paper of McMorris and Shier Commentationes Mathematicae Universitatis Carolinae 1985 T 26 S 319 322 Dodatkova literaturaRozdil pro rozsheplyuvani grafi v knizi en Algorithmic Graph Theory and Perfect Graphs

Дата публікації:
Топ