Leválasztott grafikon beágyazása

A nem kapcsolt gráfbeágyazás egy irányítatlan gráf  beágyazása az euklideszi térbe úgy, hogy a gráf két ciklusának nincs nullától eltérő összekapcsolási együtthatója . A lapos beágyazás olyan beágyazás, amelyben bármely ciklus egy olyan topológiai kör  határa, amelynek belseje nem kapcsolódik a gráfhoz. A hivatkozások nélküli beágyazható gráf  olyan grafikon, amely kapcsolat nélküli vagy lapos beágyazással rendelkezik. Ezek a gráfok síkgráfok háromdimenziós analógját alkotják [1] . Ezzel szemben a lényegében összekapcsolt gráf  olyan, amelyen nincs csatolatlan beágyazás.

A lapos beágyazások automatikusan nem tartalmaznak hivatkozásokat, de fordítva nem [2] . A teljes gráfnak , a Petersen-gráfnak és a Petersen- gráfcsalád másik öt gráfjának nincs kapcsolat nélküli beágyazása [1] . A nem csatolt beágyazó gráfokat gráf minorok [3] és Y-Δ transzformációk [2] zárják le . Ezekben a gráfokban a Petersen család gráfjai tiltott kiskorúak [4] , és síkgráfokat és csúcsgráfokat [2] tartalmaznak . A grafikonok felismerhetők (és lapos beágyazás építhető) lineáris időben [5] .

Definíciók

Két nem metsző görbét az euklideszi térben nem kapcsolódnak össze, ha a görbék folyamatos mozgása következtében két nem metsző egysíkú körré alakulnak át anélkül, hogy az egyik görbe áthaladna a másikon vagy önmagán. Ha nincs ilyen folyamatos mozgás, akkor a görbéket összekapcsoltnak mondjuk . A két kör által alkotott Hopf-hivatkozás, amelyek áthaladnak egy e körök által átívelt korongon, a legegyszerűbb példája egy összekapcsolt görbepárnak, de a görbék sokkal összetettebb módon kapcsolhatók össze. Ha a görbék nincsenek összekapcsolva, akkor találhatunk egy (topológiai) korongot az első görbével határolt térben, amely nem metszi a másodikat. Ezzel szemben, ha létezik ilyen lemez, a görbék nincsenek összekapcsolva.

Két zárt görbe kapcsolódási együtthatója háromdimenziós térben a görbe topológiai invariánsa - ez a görbékre ekvivalens módon meghatározott szám, amely nem változik, ha a görbéket folyamatosan mozgatjuk a térben anélkül, hogy kereszteznék egymást. vagy magukat. Az összekapcsolási együtthatót úgy találjuk meg, hogy egy beágyazást egy síkra vetítünk, és meghatározott módon megszámoljuk az első görbe áthaladásának számát a másodikon (+1 vagy –1 előjellel az áthaladás irányától függően). A vetítésnek "helyesnek" kell lennie, ami azt jelenti, hogy nincs két csúcs ugyanabba a pontba vetítve, nincs csúcs egy él belsejében, és a vetítés bármely pontján, ahol az élek metszik egymást, keresztirányban metszik egymást . Ilyen korlátozások mellett minden vetítés ugyanahhoz a kapcsolódási együtthatóhoz vezet. A nem kapcsolt görbék kapcsolódási együtthatója nulla, ezért ha egy görbepárnak nullától eltérő kapcsolódási együtthatója van, akkor a két görbét össze kell kapcsolni. Vannak azonban példák kapcsolt görbékre, amelyek összekapcsolási tényezője nulla, ilyen például a Whitehead hivatkozás .

A gráf háromdimenziós térbe való beágyazása abból áll, hogy a gráf csúcsait a térben lévő pontokra, az éleket pedig görbékre leképezi úgy, hogy egy él minden végpontja a megfelelő görbe egy végpontjához, a görbék pedig két görbének felelnek meg. a különböző élek nem metszik egymást (kivéve a közös végpontokat). Bármely véges gráfnak véges (esetleg exponenciális) számú különböző egyszerű ciklusa van, és ha a gráf háromdimenziós térbe van ágyazva, minden ilyen ciklus egy egyszerű zárt görbét alkot. Lehetőség van minden így kialakított, nem metsző görbepár összekapcsolási együtthatójának kiszámítására. Ha az összes cikluspár nulla összekapcsolási együtthatóval rendelkezik, akkor a beágyazást szétválasztottnak mondjuk [6] [1] [2] .

Egyes esetekben egy gráf beágyazható a térbe oly módon, hogy a gráfban minden egyes ciklushoz találhatunk egy e ciklus által határolt korongot, amely nem metszi a gráf többi elemét. Ebben az esetben a ciklus nem kapcsolódhat a gráf más olyan ciklusaihoz, amelyek nem metszik egymást. Egy beágyazásról azt mondjuk, hogy lapos, ha bármely ciklus a leírt módon határolódik a lemezen [2] . Hasonlóképpen, a "jó befektetés" definícióját megadja Motwani, Raghunathan, Saran, 1988 . Lásd még Saran (1989 ) és Böhme (1990 ). A lapos beágyazás szükségszerűen nincs összekapcsolva, de előfordulhatnak olyan nem lapos beágyazások is. Például, ha G egy gráf, amelyet két különálló ciklus alkot, és a beágyazás Whitehead-hivatkozást eredményez, akkor a beágyazás nem kapcsolódik, de nem sík.

Egy gráfot lényegében összekapcsoltnak nevezünk, ha bármilyen beágyazás mindig linkelt beágyazást eredményez. Bár a nem csatolt és a lapos beágyazás nem ugyanaz, a nem csatolt beágyazású gráfokról kiderül, hogy ugyanazok, mint a lapos beágyazású gráfok [7] .

Példák és ellenpéldák

Ahogy Sacks [1] kimutatta , egy Petersen család mind a hét gráfja lényegében össze van kapcsolva, és nem mindegy, hogy ezek a gráfok hogyan vannak beágyazva a térbe, minden beágyazásnál két összekapcsolt ciklusuk van. Ezek a gráfok magukban foglalják a teljes gráfot , a Petersen -gráfot, a teljes kétrészes gráf élének eltávolításával létrehozott gráfot és a teljes háromrészes gráfot .

Bármely síkbeli gráfnak van egy lapos és nem összekapcsolt beágyazása – csak ágyazza be a gráfot egy (háromdimenziós) térben lévő síkba. Ha a gráf sík, ez az egyetlen módja annak, hogy a gráfot laposan és nem csatolva ágyazzuk be – minden lapos beágyazás folyamatosan deformálható a síkban lévő beágyazássá. Ezzel szemben minden nem síkbeli nem csatolt gráfnak több nem csatolt beágyazása van [2] .

A síkgráfhoz egy csúcs hozzáadásával kialakított csúcsgráf is rendelkezik lapos és nem láncolt beágyazással - a gráf síkbeli részét beágyazzuk a síkra, elhelyezzük a gráf csúcsát (a síkbeliséget sértő csúcsot) a sík fölé, majd szegmensek formájában rajzoljon éleket a csúcsból a szomszédos csúcsokba. A síkon lévő bármely zárt görbe egy olyan korongot határol, amely nem halad át a gráf másik elemén, és a csúcson átívelő zárt görbe egy olyan korongot határol a sík felett, amely nem megy át a gráf egyetlen másik elemén sem [2] .

Ha a gráf nem csatolt vagy lapos beágyazású, akkor módosítsa a gráfot éleinek felosztásával vagy összevonásával, több él hozzáadásával vagy eltávolításával a csúcspárok között, vagy Y-Δ transzformációk végrehajtásával , amelyekben egy harmadik fokú csúcsot egy három szomszédot összekötő háromszög, vagy fordítva, a lapos vagy nem összekapcsolt beágyazás fennmaradásához vezet [2] . Konkrétan egy köbös síkgráfban (amelyben minden csúcsnak pontosan három szomszédja van, mint egy kockának) tetszőleges független csúcshalmazról készíthetünk másolatot egy Y-Δ transzformáció végrehajtásával, és a kapott élek többszörös másolatát adjuk hozzá. háromszögeket, majd végrehajtjuk az inverz Δ -Y-transzformációkat.

Jellemzés és felismerés

Ha egy gráf kötetlen vagy lapos beágyazással rendelkezik, akkor minden kisebb gráfnak (az élek összehúzásával, valamint az élek és csúcsok eltávolításával kialakított gráf) is van csatolatlan vagy lapos beágyazás. A törlés nem szakíthatja meg a nem kapcsolt vagy lapos egymásba ágyazás lehetőségét, és az összehúzódást úgy lehet elvégezni, hogy az él egyik végpontját a helyén hagyjuk, és az összes, az ellenkező csúcsra eső élt átkapcsoljuk. Így a Robertson-Seymour-tétel szerint az összekapcsolatlan beágyazású gráfokat tiltott gráfokkal jellemezzük, mint olyan gráfokat, amelyek nem tartalmaznak egy véges mellékhalmazt sem [3] .

A tiltott kiskorúak halmazát az összekapcsolatlan beágyazást lehetővé tévő gráfokhoz Sacks [1] fedezte fel – a Petersen család hét  gráfja kisebb minimális, lényegében összekapcsolt gráf. Sachs azonban nem tudta bizonyítani, hogy csak ezek a gráfok kisebb-minimálisan kapcsolt gráfok, és ezt Robertson, Seymour és Thomas [4] tették meg .

Az összekapcsolatlan beágyazást engedélyező gráfok tiltott minorokkal történő jellemzése egy polinomiális futási idővel rendelkező algoritmust eredményez a felismerésükhöz, de ez az algoritmus nem hoz létre valódi beágyazást. Karavabaishi, Kreutzer és Mohar [5] egy lineáris idejű algoritmust írt le, amely ellenőrzi, hogy egy gráf beágyazható-e hivatkozás nélkül, és ha beágyazható, megszerkeszti a gráf lapos beágyazását. Algoritmusuk megkeresi a nagy síkbeli részgráfokat egy adott gráfon belül úgy, hogy ha van kapcsolat nélküli beágyazás, akkor azok az részgráf síkbeli beágyazását reprezentálják. A gráf újraegyszerűsítésével, amikor ilyen részgráfot találunk, a problémát olyanra csökkentik, ahol a fennmaradó gráfot korlátozza a fa szélessége , és ekkor a probléma megoldható dinamikus programozással .

Robertson, Seymour és Thomas [2] vetette fel azt a problémát, hogy hatékonyan ellenőrizze, hogy egy adott beágyazás lapos-e vagy nincs-e összekapcsolva . A probléma megoldatlan marad, és összetettségében egyenértékű a csomófeloldási problémával, annak ellenőrzésével, hogy egy térbeli görbe nincs-e feljegyzett [5] . Ismeretes, hogy az unnotting (és így a nem kapcsolt egymásba ágyazás) ellenőrzése az NP osztályba tartozik , de nem ismert, hogy az NP-teljes problémák osztályába tartozik-e [8] .

Kapcsolódó grafikoncsaládok

A Colin de Verdière invariáns  bármely gráfhoz definiált szám az algebrai gráfelmélet alapján . Egy olyan gráf, amelynek Colin de Verdière invariánsa nem haladja meg a μ-t bármely rögzített μ állandó esetén, kisebb zárt családot alkot, és az első néhány ilyen család jól ismert – a μ ≤ 1-es gráfok lineáris erdők (pályák diszjunkt uniója), gráfok ahol μ ≤ 2 a síkbeli gráfok , a μ ≤ 3 gráfok pedig sík gráfok . Amint azt Robertson, Seymour és Thomas [2] javasolta, valamint Lowash és Schreiver [9] bebizonyította , a μ ≤ 4 gráfok pontosan nem kapcsolt beágyazású gráfok.

A síkgráfok és a csúcsgráfok lehetővé teszik az összekapcsolatlan beágyazást, akárcsak a belőlük Y-Δ transzformációkkal kapott gráfok [2] . Az YΔY redukálható gráfok  olyan gráfok, amelyek egyetlen csúcsra redukálhatók Y-Δ transzformációval, eltávolítva az izolált csúcsokat és a függő csúcsokat (1. fokú csúcsokat), és a második fokú csúcsban lévő íveket egyetlen ívre cserélve. Ezek a grafikonok kiskorúaknál is zártak. Léteznek azonban nem kapcsolt YΔY-irreducibilis gráfok, például a csúcsgráf, amelyet úgy alakítanak ki, hogy egy csúcsot (egy síkságot sértő csúcsot) a rombikus dodekaéder összes harmadik fokú csúcsához kapcsolunk [10] . Vannak nem kapcsolt gráfok is, amelyeket nem lehet Y-Δ transzformációkkal transzformálni, eltávolítva az izolált és függő csúcsokat, és a második fokozatú csúcson lévő íveket egy ívre cserélni csúcsgráfba. Például egy tíz csúcsú koronának van kapcsolat nélküli beágyazása, de nem konvertálható csúcsgráfrá a fent leírt módon [2] .

A nem összekapcsolt beágyazás fogalmához kapcsolódik a nem jegyzett beágyazás fogalma. Ez egy olyan gráfbeágyazás, hogy egyetlen egyszerű ciklus sem alkot nem triviális csomót . A nem jegyzett beágyazással nem rendelkező gráfok közé tartozik a K 7 és a K 3,3,1,1 [6] [11] . Mindazonáltal vannak minimálisan tiltott minorok a nem jegyzett beágyazásoknál, amelyeket nem úgy alakítanak ki (a fenti két gráftól eltérően), hogy egy lényegében összekapcsolt gráfhoz egy csúcsot adnak [12] .

Meghatározhatók gráfcsaládok a beágyazásukban lévő bonyolultabb csomók és linkek jelenléte vagy hiánya alapján [3] [13] , vagy egy, az euklideszi tértől eltérő háromdimenziós sokaság összekapcsolatlan beágyazásával [14] . Flapan, Naimi és Pommersheim [15] egy gráf beágyazását tripla linkként határozta meg, ha három ciklus van, amelyek közül egyik sem választható el a másik kettőtől. Megmutatták, hogy a K 9 lényegében nem háromszorosan kapcsolódik, míg a K 10 kapcsolódik [16] . Általánosságban elmondható, hogy az n -kapcsolt beágyazás bármely olyan beágyazáshoz definiálható, amely olyan -komponensű hivatkozást tartalmaz, amelyet egy topológiai gömb nem oszthat két külön részre. A kisebb-minimális lényeges- linked gráfok mindenki számára ismertek [17] .

Történelem

Azt a kérdést , hogy egy beágyazásnak van-e kapcsolata vagy síkja , Bothe vetette fel a hetvenes évek elején a topológiai kutatói közösségben [18] . A nem kapcsolt beágyazás felkeltette Sacks [1] gráfelméleti kutatók figyelmét , akik számos kapcsolódó problémát javasoltak, többek között azt a problémát, hogy a nem csatolt vagy lapos beágyazású gráfok tiltott gráfjaival karakterizálást találjanak. Sachs kimutatta, hogy a Petersen család hét grafikonja (köztük ) nem rendelkezik ilyen beágyazással. Ahogy Nexetril és Thomas [3] megjegyezte , a nem kapcsolt beágyazó gráfok a gráf minorjaiban vannak zárva , ami a Robertson-Seymour-tétel szerint azt jelenti, hogy létezik tiltott gráfokkal való jellemzés. A véges számú akadályozó gráf létezésének bizonyítása nem vezet a tiltott kiskorúak halmazának explicit leírásához, de Sacks eredményeiből az következik, hogy a Petersen család hét gráfja tartozik a halmazba. Ezeket a problémákat végül Robertson, Seymour és Thomas [4] [7] oldották meg, akik kimutatták, hogy a Petersen családnak ez a hét gráfja az egyetlen minimálisan tiltott kiskorú az ilyen gráfokhoz. Így az összekapcsolatlan beágyazható gráfok és a síkban beágyazható gráfok ugyanazt a gráfkészletet jelentik, és mindkét család olyan gráfként definiálható, amely nem tartalmazza a Petersen család elemeit kiskorúként.

Sacks [1] rákérdezett az élek számának határaira és a link nélküli beágyazható gráfok kromatikus számára is . A link nélküli beágyazható csúcsgráf éleinek száma nem haladja meg  – a c csúcsgráfok maximális száma pontosan ennyi éllel rendelkezik [1] , és Mader [19] bebizonyította a felső korlátot a K 6 -mentes gráf általánosabb osztályára. kiskorúak. 1985-ben kimutatták, hogy Sachs kromatikus számra vonatkozó kérdése megoldódna, ha bebizonyosodik Hadwiger sejtése, miszerint bármely -kromatikus gráfnak van egy teljes gráfja, amelynek csúcsai kisebbek [3] . Robertson, Seymour és Thomas [20] bizonyítéka a Hadwiger-sejtés esetére elegendő Sachs kérdésének megoldásához – a hivatkozások nélküli gráfok legfeljebb öt színnel színezhetők, mivel bármely 6-kromatikus gráf tartalmaz egy minort , és nincs szétválasztva. , és vannak összekapcsolatlan grafikonok, például , amelyek öt színt igényelnek. A snark- tételből az következik, hogy minden hivatkozás nélküli köbös beágyazható gráf 3-él színezhető .

A link nélküli beágyazások vizsgálata az algoritmusok tanulmányozásával kezdődött az 1980-as évek végén [21] [22] . Algoritmikusan megoldódott a link nélküli beágyazható és lapos beágyazható gráfok felismerésének problémája, amikor a tiltott kiskorúak általi jellemzés bizonyítást nyert – Robertson és Seymour [23] algoritmusával polinomiális időben ellenőrizhető, hogy egy adott gráf tartalmazza-e valamelyiket a hét tiltott kiskorú közül. [24] . Ez a módszer nem kötetlen vagy lapos beágyazást épít, ha létezik, hanem egy beágyazást felépítő algoritmust [25] , és később talált egy hatékonyabb algoritmust, amely lineáris időben fut [5] .

Sachs [1] utolsó kérdésére a Fari-tétel analógiájának lehetőségéről még nem érkezett meg a válasz. A kérdés a következő: mikor következik be az ívelt vagy darabonként lineáris élekkel rendelkező, össze nem kötött vagy lapos beágyazás létezése egy nem kapcsolt vagy lapos beágyazás létezésére, amelyben az élek szegmensek ?

Jegyzetek

  1. ↑ 1 2 3 4 5 6 7 8 9 Sachs, 1983 .
  2. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 Robertson, Seymour, Thomas, 1993a .
  3. ↑ 1 2 3 4 5 Nešetřil, Thomas, 1985 .
  4. ↑ 1 2 3 Robertson, Seymour, Thomas, 1995 .
  5. ↑ 1 2 3 4 Kawarabayashi, Kreutzer, Mohar, 2010 .
  6. ↑ 1 2 Conway, Gordon, 1983 .
  7. ↑ 12 Robertson, Seymour, Thomas, 1993b .
  8. ↑ Hass, Lagarias, Pippenger, 1999 .
  9. ↑ Lovász, Schrijver, 1998 .
  10. ↑ Truemper, 1992 .
  11. ↑ Foisy, 2002 .
  12. ↑ Foisy, 2003 .
  13. ↑ Fleming, Diesl, 2005 .
  14. ↑ Flapan, Howards, Lawrence, Mellor, 2006 .
  15. ↑ Flapan, Naimi, Pommersheim, 2001 .
  16. ↑ A nem háromszorosan összekapcsolt gráfok további példáit lásd: Bowlin és Foisy 2004 .
  17. ↑ Flapan, Pommersheim, Foisy, Naimi, 2001 .
  18. ↑ Bothe, 1973 .
  19. ↑ Mader, 1968 .
  20. ↑ Robertson, Seymour, Thomas, 1993c .
  21. ↑ Fellows, Langston, 1988 .
  22. ↑ Motwani, Raghunathan, Saran, 1988 .
  23. ↑ Robertson, Seymour, 1995 .
  24. ↑ A Robertson-Seymour algoritmus alkalmazhatóságát erre a problémára Fellows és Langston vette észre ( Fellows, Langston, 1988 ).
  25. ↑ van der Holst, 2009 .

Irodalom