Fogó nélkül számolj

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. szeptember 12-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A gráfelméletben a karmok nélküli gráf olyan gráf, amely nem tartalmaz generált részgráfokat , amelyek izomorfak a K 1,3 -ra ( karmok ).

A karom egy teljes kétrészes gráf K 1,3 (vagyis egy csillag három éllel, három levelével és egy központi csúcsával). A karmok nélküli gráf olyan gráf, amelyben egyetlen generált részgráf sem karm, azaz nincs négy olyan A , B , C és O csúcs , hogy O kapcsolódjon A , B és C csúcsokhoz, de az A , B és C csúcsok nem. kapcsolódnak egymáshoz. Lehetőség van arra is, hogy egy karmok nélküli gráfot olyan gráfként definiáljunk, amelyben a szomszédságbármely csúcs alkotja a háromszög nélküli gráf komplemensét .

A karmok nélküli gráfokat eredetileg a vonalgráfok általánosításaként tanulmányozták, és további ösztönzést kaptak, amikor három kulcsfontosságú tényt fedeztek fel róluk:

  1. az a tény, hogy minden összefüggő gráf, karmok nélkül, páros sorrendben tökéletesen illeszkedik ;
  2. időpolinomiális algoritmus felfedezése a maximális független halmaz megtalálásához karmok nélküli gráfokban;
  3. karmok nélküli tökéletes gráfok leírása [1] . A karmok nélküli grafikonokról több száz dolgozat és számos áttekintés született [2] .

Példák

Elismerés

Közvetlenül ellenőrizhető, hogy egy adott n csúcsú és m élű gráfnak nincsenek-e karmai O( n 4 ) idő alatt, ha négy csúcsonként ellenőrizzük, hogy generálnak-e karmot [6] . Valamivel hatékonyabban, de nehezebben ellenőrizhető, hogy a gráfnak nincsenek-e karmai, ha a gráf minden csúcsánál ellenőrizzük, hogy a csúcs szomszédos gráfjának komplementere nem tartalmaz-e háromszöget. Egy gráf akkor és csak akkor tartalmaz háromszöget, ha a szomszédsági mátrix kockája nem nulla átlós elemet tartalmaz, így a háromszög keresése ugyanabban az aszimptotikus időben elvégezhető, mint az n  ×  n mátrixszorzás [7] . Így a Coppersmith-Winograd algoritmus használatával a teljes idő annak meghatározására, hogy egy gráfnak vannak-e karmai, O( n 3,376 ).

Kloks, Kratsch és Müller ( Kloks, Kratsch, Müller ) [8] felhívta a figyelmet arra, hogy egy karmok nélküli gráfban minden csúcsnak maximum szomszédja van, különben a Turan-tétel szerint a csúcs szomszédságában nem lesz elegendő él ahhoz, hogy a gráf háromszögek nélküli komplemensét képezze. Ez a megfigyelés lehetővé teszi a szomszédok ellenőrzését a korábban említett gyors mátrix szorzatalgoritmus segítségével ugyanabban az aszimptotikus időben . Ennek az algoritmusnak a legrosszabb esete akkor fordul elő, ha Ω(√ m ) csúcsok mindegyikének Ω(√ m ) szomszédja van, a többi csúcsnak pedig kevés szomszédja van, ebben az esetben a teljes idő ( m 3,376/2 ) = O( m 1,688 ).

Felsorolás

Mivel a körmök nélküli gráfok a háromszög nélküli gráfok összes komplementerét tartalmazzák, az n csúcsú karmok nélküli gráfok száma legalább olyan ütemben növekszik, mint a háromszög nélküli gráfok száma, azaz exponenciálisan n gyökétől számítva . Összekapcsolt körmök nélküli, n élű gráfok száma, ha n = 1, 2, …

1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, ... OEIS szekvencia A022562 .

Ha a grafikonok szétválaszthatók, a grafikonok száma nagyobb:

1, 2, 4, 10, 26, 85, 302, 1285, 6170, ... OEIS sorozat A086991 .

Palmer, Read, Robinson technikája ( Palmer, Read, Robinson, 2002 ) [9] lehetővé teszi a körmök nélküli köbös gráfok számának nagyon hatékony kiszámítását, ami szokatlan a gráf-számlálási feladatoknál .

Egyező

Sumner ( Sumner, 1974 ) [10] és ettől függetlenül Las Vergnas ( Las Vergnas, 1975 ) [11] bebizonyította, hogy minden páros számú csúcsot tartalmazó karmok nélküli összekapcsolt gráf tökéletesen illeszkedik [12] . Vagyis van egy olyan élhalmaz a gráfban, amelynek minden csúcsa az illesztésből pontosan egy él végcsúcsa. Ebből következik, hogy a páros számú élű vonalgráfoknál lehetőség van kettes hosszúságú útvonalon az összes él felosztására. Tökéletes illesztések használhatók a karmok nélküli gráfok egy másik jellemzőjére is – ezek pontosan azok a gráfok, amelyekben bármely összekapcsolt generált, páros sorrendű részgráf tökéletes illeszkedést tartalmaz [12] .

Sumner bizonyítása szigorúan véve azt mutatja, hogy minden karmok nélküli összekapcsolt gráfban találhatunk olyan konjugált csúcspárokat, amelyek eltávolításakor a gráf összekapcsolódik. Ennek bizonyítására Sumner talál egy olyan u és v csúcspárt , amelyek a lehető legtávolabb vannak egymástól, és az u - tól a lehető legtávolabb eső v csúcs szomszédjai közül w -et választ . Mint megmutatta, sem v , sem w nem tud a legrövidebb úton haladni bármely másik csúcstól u -hoz, így a v és w eltávolítása a gráfot összekapcsolva marad. Az ilyen párok egymás utáni eltávolítása tökéletes illeszkedést biztosít egy karmok nélküli gráfban.

Ugyanez a bizonyítási elképzelés működik általánosabb esetben is: ha u  bármely csúcs, v  minden olyan csúcs, amely a lehető legtávolabb van u -tól , w pedig v  bármely szomszédos csúcsa , amely a lehető legtávolabb van u -tól . A v és w eltávolítása a grafikonból nem változtatja meg az u távolságokat . Így az u - tól maximálisan távol eső vw párok megtalálásával és eltávolításával történő illesztések létrehozásának folyamata lineáris időben befejezhető, ha egyszerűen bejárjuk a szélesség-első keresési fát , az u csúcsból kiindulva . Chrobak, Naor és Novick ( 1989 ) [13] egy másik mélységi keresésen alapuló időlineáris algoritmust , valamint hatékony párhuzamos algoritmusokat adott ugyanarra a problémára.

Faudree , Flandrin, Ryjáček [2] számos, egymással szorosan összefüggő eredményt adott , köztük a következőket:

  1. Egy ( r − 1)-összefüggésű gráf, amely nem tartalmaz K 1-et, r páratlan rendű részgráfok tökéletes illeszkedést mutatnak bármely r ≥ 2-re.
  2. A páratlan sorrendű, karmok nélküli, legfeljebb egy elsőfokú csúcsú grafikonok egy páratlan ciklusra és egy illesztésre oszthatók.
  3. Bármely olyan k -ra, amely legalább a fele egy karmok nélküli gráf minimális fokának, amelyben vagy k , vagy a csúcsok száma páros, a gráfnak k -tényezője van .
  4. Ha egy karmok nélküli gráf ( 2k + 1) -összefüggésben van, akkor bármely k -él illesztés tökéletes illeszkedésre kiterjeszthető.

Független halmazok

Egy független halmaz egy vonalgráfban megfelel az eredeti gráf egyezésének, vagyis olyan élhalmaznak, amelyben nincs két élnek közös pontja. Ahogy Edmonds ( 1965) [14] kimutatta , a maximális illeszkedés bármely gráfban megtalálható polinomidőben; Sbihi ( 1980 ) [15] kiterjesztette ezt az algoritmust úgy, hogy az új algoritmus megtalálja a maximális független halmazt bármely karmok nélküli gráfban [16] . Minty ( Minty, 1980 ) [17] (javította: Nakamura és Tamura ( Nakamura, Tamura, 2001 ) [18] ) adott egy újabb kiterjesztést Edmond algoritmusainak karmok nélküli gráfokra, amely a problémát illeszkedéssé alakítja át egy segédgráfban, amelyet a eredeti grafikon karmok nélkül . A Minty-féle megközelítés használható annak az általánosabb problémának a megoldására, hogy megtaláljuk a polinomidőben mért maximális tömeg független halmazát. Ezeket az eredményeket a gráfok széles osztályára lehet általánosítani [16] .

Ahogy Sbihi megjegyezte, ha  egy független halmaz egy karmok nélküli gráfban, akkor a gráf bármely csúcsának legfeljebb két szomszédos csúcsa lehet  - három szomszédos csúcs alkotna egy karmot. Sbihi egy csúcsot telítettnek nevez, ha két szomszédja van -ból, és telítetlennek , ha nem tartozik hozzá , és ugyanakkor kevesebb, mint két szomszédja van -ból . Sbyha megfigyeléséből következik, hogy ha és vannak független halmazok, akkor a , által generált gráf legfeljebb kettős fokozatú lehet. Így ez az utak és a ciklusok egyesülése. Konkrétan, ha  nem maximális független halmaz, akkor ciklusok és komplementer utak által különbözik minden maximális független halmaztól , vagyis olyan utaktól, amelyekben a kiindulópontok és nem a csúcsok váltakoznak, és amelyeknél mindkét végső csúcs nincs telítve. A gráfok és a befejezési út szimmetrikus különbsége a maximális független halmaz (Az azonos V csúcskészletű H és G gráfok szimmetrikus különbsége egy olyan gráf, amelynek V csúcskészlete azonos, G és H éleket tartalmaz, de nem tartalmaz G-hez és H-hoz is tartozó közös élek). A Sbiha algoritmusa fokozatosan növeli a független halmaz méretét azáltal, hogy komplementer útvonalakat keres , ameddig ilyen utak találhatók.

A kibővítő útvonal megtalálása bonyolult, mert előfordulhat, hogy egy útvonal-kiterjesztés nem létezik, ha két olyan csúcs között van él, amelyek nem tartoznak a -hoz . Szerencsére ez csak két esetben fordulhat elő: két szomszédos csúcs lehet az út végső csúcsa, vagy van köztük egy olyan csúcs, amely mindkettővel szomszédos. Bármely másik szomszédos csúcs karmához vezet. A szomszédos végcsúcsokat úgy távolíthatjuk el, hogy ideiglenesen eltávolítjuk az összes szomszédos v -csúcsot, mielőtt v -vel kezdődő befejezési útvonalat keresnénk . Ha az elérési út nem található, a v csúcs az algoritmus végéig eltávolítható a gráfból. A gráf ilyen redukciója után a probléma leírható kapcsológráfban , bár Sbihy nem ezt a terminológiát használta. A kapcsológráf egy irányítatlan gráf, amelyben bármely csúcs ívei két csoportra vannak osztva, és a csúcson áthaladó bármely útnak mindkét csoport éleit kell tartalmaznia. Egy karmos gráf telített és telítetlen csúcsainak halmazán lehet kapcsológráfot szerkeszteni, amelynek élei összekötik a csúcsokat, ha nem szomszédosak az eredeti gráfban, és van közöttük egy 2 hosszúságú út, amely áthalad egy I -ből származó csúcson. . Az egyes csúcsokban lévő két élhalmazt az a két I csúcs alkotja, amelyeken ezek a 2 hosszúságú utak áthaladnak. A kapcsológráfban két telítetlen csúcs közötti útvonal megfelel az eredeti gráf komplementer útvonalának. A kapcsolási gráf négyzetes bonyolultságú, és a benne lévő útvonal lineáris időben megtalálható, és az algoritmus teljes időtartamára szükség lehet O( n ) feltöltési útvonalak megtalálására. Így a Sbiha-algoritmushoz O( n 3 ) futási idő szükséges.

Színezés, kattintások és uralom

A tökéletes gráf  egy olyan gráf, amelyben a kromatikus szám és a maximális klikk mérete egyenlő, és amelyben ez az egyenlőség bármely indukált részgráfban létezik. Ismeretes (a szigorú tökéletes gráf tétellel ), hogy a tökéletes gráfok olyan gráfokként jellemezhetők, amelyeknek nincsenek páratlan ciklusai, vagy páratlan ciklusok komplementerei (ún. páratlan lyukak), mint indukált részgráfok (ún. páratlan lyukak ) . 5] . Ez a tény azonban sok éven át feltételezés maradt, amely csak a gráfok speciális alosztályaira igazolódott. Az egyik ilyen alosztály a karmok nélküli gráfok családja volt – több szerző úgy találta, hogy a karmok nélküli, páratlan ciklusok és lyukak nélküli gráfok tökéletesek. A karmok nélküli gráf tökéletessége polinomiális időben ellenőrizhető. Egy karmok nélküli tökéletes gráfban bármely csúcs szomszédsága egy kétrészes gráf komplementerét alkotja . Kiszínezhet egy tökéletes gráfot karmok nélkül, vagy megtalálhatja benne a maximális klikket polinomidőben [19] .

Ha a karmok nélküli gráf nem tökéletes, a maximális klikk megtalálásának problémája NP-nehéz lesz [6] . Egy ilyen gráf optimális színezésének megtalálása szintén NP-nehéz, mivel (a vonalgráfon keresztül) ez a probléma általánosítja a gráf kromatikus számának kiszámításának NP-nehéz problémáját [6] . Ugyanezen okból NP-nehéz olyan színező algoritmust találni, amelynek garantált hatékonysága jobb, mint 4/3. A mohó színező algoritmussal azonban garantált kettős hatásfokot kaphatunk , mivel egy körömmentes gráf kromatikus száma nagyobb, mint a maximális teljesítmény fele.

Bár nem minden karmok nélküli gráf tökéletes, a karmok nélküli gráfok egy másik, a tökéletességgel kapcsolatos tulajdonságot is kielégítenek. Egy gráfot tökéletes dominanciagráfnak nevezünk , ha van egy minimális domináns halmaza , amely csúcsok független halmaza, és ha minden generált részgráfnak ugyanaz a tulajdonsága. A fáklyák nélküli grafikonok rendelkeznek ezzel a tulajdonsággal. Ennek bemutatásához tegyük fel, hogy D  egy domináns halmaz egy karmok nélküli gráfban, és legyen v és w D  két konjugált csúcsa . Ekkor a v által dominált, de nem w által dominált csúcsok halmazának klikknek kell lennie (különben v lenne a karom középpontja). Ha ennek a klikknek minden csúcsát már D legalább egy tagja uralja , akkor v eltávolítható egy kisebb független domináns halmaz létrehozásához. Ellenkező esetben v helyettesíthető a klikk egyik nem dominált csúcsával, így kevesebb szomszédos csúcsot tartalmazó domináns halmaz jön létre. Ezeket a helyettesítéseket megismételve egy D -nél nem nagyobb domináns halmazhoz jutunk , így ha a kezdeti D  a minimális domináns halmaz, akkor a folyamat egy azonos méretű független domináns halmazhoz vezet [20] .

A tökéletes dominancia tulajdonság ellenére a minimális domináns halmaz méretének meghatározása karmok nélküli gráfban NP-nehéz probléma [6] . Azonban a gráfok általánosabb osztályaival ellentétben a karmok nélküli gráfban a minimális domináns halmaz megtalálása parametrikusan bonyolult fix paraméterekkel  – a probléma időben megoldható, ami polinomiálisan függ a gráf méretétől és exponenciálisan a domináns halmaz mérete [21] [22 ] .

Szerkezet

Chudnovskaya és Seymour [23] egy sor közleményben bebizonyított egy karmok nélküli strukturális gráfelméletet, amely hasonló a Robertson és Seymour által bizonyított gráfstruktúra- tételhez a kisebb zárt gráfok családjaira , valamint a tökéletes gráfok strukturális elméletéhez, amelyet Chudnovsky ). Seymour és szerzőtársaik szokták bizonyítani a szigorúan tökéletes gráftételt [5] . Az elmélet túl bonyolult ahhoz, hogy itt részletesen leírjuk, de hogy megmutassa szépségét, ismertetünk néhány eredményt. Először is, a körmök nélküli gráfok egy speciális alosztályára vonatkozóan, amelyeket kvázi-vonal gráfoknak (vagy lokálisan kvázi-bipartit gráfoknak) neveztek, azt állítják, hogy minden ilyen gráfnak a következő két formája van:

  1. A fuzzy körkörös intervallumgráf  olyan gráfok osztálya, amelyek geometriailag a körön lévő pontok és ívek formájában ábrázolhatók.
  2. Olyan gráf, amely multigráfból építhető fel úgy, hogy minden élt egy fuzzy lineáris intervallumgráfra cserélünk . Ez általánosítja a vonalgráfok felépítését, amelyekben a multigráf minden élét egy csúcs helyettesíti. A fuzzy lineáris intervallumgráfok ugyanúgy készülnek, mint a fuzzy körkörös intervallumgráfok, csak egy szakaszon, és nem egy körön.

Chudnovskaya és Seymour a karmok nélküli tetszőleges összekapcsolt gráfokat a következőképpen osztályozta:

  1. Hat konkrét grafikon karmok nélkül. Közülük három vonalgráf, néhány ívdiagram és az ikozaéder generált részgráfja . A maradék három további definíciókat igényel.
  2. Kisebb, karmok nélküli grafikonokból négy egyszerű módon alakíthatók ki grafikonok.
  3. Az antiprizmatikus gráfok , a sűrű gráfok  osztálya , olyan karmok nélküli gráfok, amelyekben bármely négy csúcs legalább két élű részgráfot generál.

Osztályozási munkájuk nagy részét az antiprizmatikus gráfok elemzésére fordítják. Az elemzés ezen részében fontos szerepet játszik a Schläfli gráf , egy erősen szabályos , karmok nélküli gráf srg(27,16,10,8) paraméterekkel. Ez a szerkezeti elmélet új előrelépésekhez vezetett a poliéderek kombinatorikájában és új korlátokhoz vezetett a körmök nélküli gráfok kromatikus számában [5] , valamint új fix paraméterű parametrikus komplexitási algoritmusokhoz vezetett a körmök nélküli gráfokban uralkodó halmazokhoz [22] .

Jegyzetek

  1. ↑ 1 2 Faudree, Flandrin, Ryjaček, 1997 , p. 88.
  2. ↑ 1 2 Faudree, Flandrin, Ryjáček, 1997 .
  3. ↑ LW Beineke. Beitrage zur Graphentheorie. - Teubner, 1968. - S. 17-33 .
  4. ↑ 1 2 Faudree, Flandrin, Ryjaček, 1997 , p. 89.
  5. ↑ 1 2 3 4 5 Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. Az erős tökéletes gráf tétel. - 2006. - T. 164 , sz. 1 . - S. 51-229 . doi : 10.4007 / annals.2006.164.51 .
  6. ↑ 1 2 3 4 Faudree, Flandrin, Ryjáček, 1997 , p. 132.
  7. ↑ Alon Itai, Michael Rodeh. Minimális áramkör keresése grafikonon // SIAM Journal on Computing . - 1978. - V. 7 , sz. 4 . - S. 413-423 . - doi : 10.1137/0207033 .
  8. ↑ Ton Kloks, Dieter Kratsch, Haiko Müller. Kis indukált részgráfok hatékony keresése és számolása // Information Processing Letters. - 2000. - T. 74 , sz. 3-4 . - S. 115-121 . - doi : 10.1016/S0020-0190(00)00047-8 .
  9. ↑ Edgar M. Palmer, Ronald C. Read, Robert W. Robinson. Karmok nélküli köbös grafikonok számolása // SIAM Journal on Discrete Mathematics . - 2002. - T. 16 , sz. 1 . - S. 65-73 . - doi : 10.1137/S0895480194274777 .
  10. ↑ David P. Sumner. Grafikonok 1-faktorral. - 1974. - T. 42 , sz. 1 . - S. 8-12 . - doi : 10.2307/2039666 . — .
  11. ↑ M. Las Vergnas. Megjegyzés a grafikonok illesztéséről // Cahiers du Centre d'Études de Recherche Opérationnelle. - 1975. - T. 17 , sz. 2-3-4 . - S. 257-260 .
  12. ↑ 1 2 Faudree, Flandrin, Ryjaček, 1997 , p. 120-124.
  13. ↑ Marek Chrobak, Joseph Naor, Mark B. Novick. Algoritmusok és adatstruktúrák : Workshop WADS '89, Ottawa, Kanada, 1989. augusztus, Proceedings. - Springer, 1989. - T. 382 . - S. 147-162 . - doi : 10.1007/3-540-51542-9_13 .
  14. ↑ Jack Edmonds. Ösvények, fák és virágok // Canadian J. Math. - 1965. - T. 17 , sz. 0 . - S. 449-467 . - doi : 10.4153/CJM-1965-045-4 .
  15. ↑ Nadzsiba Sbihi. Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile // Discrete Mathematics. - 1980. - T. 29 , sz. 1 . - S. 53-76 . - doi : 10.1016/0012-365X(90)90287-R .
  16. ↑ 1 2 Faudree, Flandrin, Ryjaček, 1997 , p. 133-134.
  17. ↑ George J. Minty. Maximális független csúcshalmazokról körmök nélküli gráfokban // Journal of Combinatorial Theory. B. sorozat - 1980. - T. 28 , sz. 3 . - S. 284-304 . - doi : 10.1016/0095-8956(80)90074-X .
  18. ↑ Daishin Nakamura, Akihisa Tamura. Minty algoritmusának átdolgozása a karmok nélküli gráf maximális súlyozott stabil halmazának megtalálására // Journal of the Operations Research Society of Japan. - 2001. - T. 44 , sz. 2 . - S. 194-204 .
  19. ↑ Faudree, Flandrin, Ryjáček, 1997 , p. 135-136.
  20. ↑ Faudree, Flandrin, Ryjáček, 1997 , p. 124-125.
  21. ↑ Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Az uralkodó halmaz fix paraméterű, körmök nélküli grafikonokon követhető. – 2010.
  22. ↑ 1 2 Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, Gerhard Woeginger. Uralkodás, amikor a csillagok kint vannak. – 2010.
  23. ↑ Maria Chudnovsky, Paul Seymour. Felmérések a kombinatorikában 2005. — Cambridge Univ. Nyomda, 2005. - T. 327 . - S. 153-171 .

Irodalom

Linkek