A matematika, azon belül a topologikus gráfelmélet, illetve a térbeli gráfelmélet területén egy irányítatlan gráfláncmentes beágyazása(linkless embedding) a gráf az euklideszi térbe történő beágyazása oly módon, hogy a gráf semelyik két köre nincs összeláncolva. Egy lapos beágyazás(flat embedding) olyan beágyazás, melynek minden köre olyan topologikus körlemez határán található, melynek belső része a gráftól diszjunkt. Egy láncmentesen beágyazható gráf(linklessly embeddable graph) olyan gráf, ami rendelkezik láncmentes vagy lapos beágyazással; ezek a gráfok a síkbarajzolható gráfok háromdimenziós analógiájának tekinthetők.[1] Komplementer módon, egy eredendően láncolt gráf(intrinsically linked graph) olyan gráf, melynek nem létezik láncmentes beágyazása.
Ha egy körtinjektív leképezés (folytonos függvény, ami a kör két különböző pontját nem visz át a tér ugyanazon pontjába) visz át a háromdimenziós euklideszi térbe, képe egy zárt görbe. Ugyanabban a síkban lévő két diszjunkt zárt görbe összeláncolatlan, és általánosabban két diszjunkt zárt görbe is összeláncolatlan, ha létezik a térnek olyan folytonos deformációja, ami mindkét görbét azonos síkba viszi át anélkül, hogy bármelyik görbe áthaladna a másikon vagy saját magán. Ha nem létezik ilyen folyamatos mozgatás, a két görbére azt mondjuk, hogy össze vannak láncolva. Például a Hopf-láncot két kör alkotta, melyek kölcsönösen átmennek a másik által kifeszített körlemezen. Ez a láncolt görbepár legegyszerűbb példája, de más, ennél bonyolultabb módon is össze lehet két görbe láncolva. Ha a két görbe nincs összeláncolva, akkor lehetséges a térben olyan topologikus körlemezt találni, melyet az első görbe határol, és a második görbétől diszjunkt. Megfordítva, ha egy ilyen körlemez létezik, akkor a görbék szükségszerűen összeláncolatlanok.
Két zárt görbe három dimenzióbeli összekapcsolódási száma(linking number) a görbékhez tartozó topológiai invariáns: olyan, a görbék alapján több ekvivalens módon definiálható számérték, ami nem változik a görbék folyamatos, egymáson nem átmenő mozgatásakor. A gráfok láncmentes beágyazásához használt definíció szerint az összekapcsolódási szám megkapható a beágyazás síkba projektálásakor azoknak a metszéseknek a megszámlálásával, ahol az első görbe átmegy a másikon, modulo 2.[2] A projekciónak „regulárisnak” kell lennie abban az értelemben, hogy két csúcs nem vetítődhet egy pontba, egy csúcs nem vetítődhet egy él belsejébe és a projekcióban ahol két él metszi egymást, ott transzverzálisan (nem érintő helyzetben) kell találkozniuk; ezekkel a megszorításokkal bármely két projekció ugyanazt az összekapcsolódási számot adja ki.
A triviális csomó összekapcsolódási száma nulla, ezért ha egy görbepár összekapcsolódási száma nem nulla, a két görbének láncoltnak kell lennie. Fordítva azonban ez nem feltétlenül igaz, mivel léteznek olyan láncolt görbék, melyek összekapcsolódási száma nulla; ilyen például a Whitehead-lánc.
Egy gráf háromdimenziós térbe történő beágyazása áll egyrészt a gráf csúcsainak a tér pontjaiba történő leképezéséből, másrészt a gráf éleinek olyan térgörbékbe való leképezéseiből, mely görbék végpontjai az élek végpontjainak felelnek meg, továbbá két különböző élhez tartozó görbe legfeljebb az élek közös végpontján metszi egymást.
Bármely véges gráfnak véges (bár esetleg a csúcsok száma szerint exponenciális) számú köre van, és a gráf háromdimenziós térbe ágyazásakor ezek a körök egyszerű zárt görbéket alkotnak. Az így kapott térgörbék közül bármely két diszjunkt pár összekapcsolódási száma meghatározható; ha mindegyik páros esetén nulla az eredmény, az adott beágyazás láncmentes.[6]
Egyes esetekben egy gráf beágyazható úgy a térbe, hogy a gráf minden köre olyan topologikus körlemezt határoljon, melyet a gráf semmilyen más része nem metsz (belső része a gráftól diszjunkt). Ebben az esetben egy ilyen körnek és a gráfban tőle diszjunkt köröknek összeláncolatlanoknak kell lenniük. A beágyazást akkor nevezzük laposnak, ha a gráf minden köre egy ilyen körlemezt határol.[7] Egy lapos beágyazás szükségképpen láncmentes, de léteznek láncmentes beágyazások, melyek nem laposak: például ha a G gráfot két diszjunkt kör alkotja, melyekből a beágyazáskor egy Whitehead-lánc jön létre, akkor a beágyazás láncmentes, de nem lapos..
Egy gráf eredendően láncolt (intrinsically linked), ha bárhogyan is ágyazzák be, a beágyazás mindig láncolt lesz. Bár a láncmentes és a lapos beágyazások nem mindig esnek egybe, a láncmentes beágyazással rendelkező gráfok megegyeznek a lapos beágyazással rendelkezőkkel.[8]
Ahogy (Sachs 1983) megmutatta, a Petersen-gráfcsalád mind a hét gráfja eredendően láncolt: teljesen mindegy, hogyan ágyazzák be őket az euklideszi térbe, mindig lesz két egymáshoz láncolódó körük. Ezen gráfok közé tartozik a K6teljes gráf, maga a Petersen-gráf, a K4,4teljes páros gráfból egy él eltávolításával kapott gráf és a K3,3,1teljes háromrészes gráf is.
Minden síkbarajzolható gráfnak van lapos és láncmentes beágyazása: a síkba rajzolt gráfot tartalmazó síkot be kell ágyazni térbe; a síkbarajzolható gráfoknak nincs is lényegileg más lapos és láncmentes beágyazása: bármely lapos beágyazásuk átalakítható folytonos deformációval egyetlen síkon fekvővé. Megfordítva, bármely nem síkbarajzolható láncmentes gráfnak többféle láncmentes beágyazása lehetséges.[2]
Egy csúcsgráf. Ha a gráf síkbarajzolható részét a tér egy síkjába ágyazzuk, a csúcspontot pedig a sík fölött helyezzük el és egyenes szakaszokkal kötjük össze a szomszédos csúcsokkal, lapos beágyazást kapunk.
Egy csúcsgráf, amit síkbarajzolható gráfhoz egy síkba már nem rajzolható csúcs hozzáadásával kapunk, rendelkezik lapos és láncmentes beágyazással: egy ilyen beágyazás megkapható a gráf síkbarajzolható részének síkba rajzolásával, majd a csúcspont a sík fölé helyezésével és a csúcspont a szomszédaival való egyenes vonalú összekötésével.
Bármely síkbeli zárt görbe határol egy a sík alatti, más gráfrésszel nem érintkező körlemezt, és bármely, a csúcsponton áthaladó zárt görbe határol egy a sík fölötti, más gráfrésszel nem érintkező körlemezt.[2]
Ha egy gráf rendelkezik láncmentes vagy lapos beágyazással, akkor ezt a tulajdonságot nem befolyásolja, ha a gráf éleit felosztjuk vagy a felosztást visszavesszük, ugyanazon csúcspár között többszörös éleket adunk hozzá vagy távolítunk el, illetve Y-Δ átalakításokat (melyek egy 3 fokszámú csúcsot a három szomszédot egyenként összekötő háromszögre cserélnek) vagy annak megfordítását végzünk el.[2] Továbbá, egy 3-reguláris síkbarajzolható gráfban Y-Δ átalakítás, a kapott háromszög éleinek többszörözésével és a fordított Δ-Y átalakítás elvégzésével lehetséges a független csúcshalmazok megduplázása.
Karakterizáció és felismerés
Ha a G gráfnak létezik láncmentes vagy lapos beágyazása, akkor G minden minorának (élösszehúzások, él- és csúcstörlések által kapott gráfoknak) is van láncmentes vagy lapos beágyazása. A törlések nyilvánvalóan nem ronthatják el a beágyazás láncmentességét vagy laposságát, az összehúzás pedig végrehajtható olyan módon, hogy az összehúzott él egyik vége a helyén maradjon, a másik végpontra illeszkedő élek pedig az összehúzott él mentén vezessenek. Ezért, a Robertson–Seymour-tétel értelmében, a láncmentesen beágyazott gráfoknak van tiltott minor alapú karakterizációjuk, azaz éppen azok a gráfok, melyek egy véges obstrukciós halmaz elemeit nem tartalmazzák minorként.[3]
A láncmentesen beágyazható gráfok obstrukciós halmazát (Sachs 1983) azonosította: a Petersen-gráfcsalád hét tagja mind minor-minimális eredendően láncolt gráfok. Sachs azonban nem tudta igazolni, hogy más gráfok nem tartoznak a halmazba, ezt végül (Robertson, Seymour & Thomas 1995) végezte el.
A láncmentesen beágyazható gráfok tiltott minor-alapú karakterizációja lehetővé teszi polinom időben történő felismerésüket, de a beágyazásnak a megkonstruálását már nem. (Kawarabayashi, Kreutzer & Mohar 2010) leír egy lineáris idejű algoritmust ami megvizsgálja, hogy egy gráf láncmentesen beágyazható-e, és ha igen, megadja egy lapos beágyazását. Az algoritmus az adott gráfnak olyan nagyméretű, síkba rajzolható részgráfjait keresi, melyek egy láncmentes beágyazás létezése esetén síkban kell maradniuk. Ilyen részgráf megtalálása esetén a gráfot újra és újra egyszerűsíti, míg a feladat egyszerűsödik egy korlátos faszélességű gráfra történő megoldásra, ami már dinamikus programozás segítségével elvégezhető.
Adott beágyazás lapos vagy láncmentességének hatékony tesztelésének problémáját (Robertson, Seymour & Thomas 1993a) vetette fel. Jelenleg is megoldatlan, és bonyolultsági osztálya szerint ekvivalens a triviális csomó-problémával, azaz annak eldöntésével, hogy adott térgörbe ekvivalens-e a triviális csomóval.[5] A kicsomózottságnak (és ezért a beágyazás láncmentességének) a tesztelése NP, de nem ismert, hogy NP-teljes-e.[9]
A síkbarajzolható gráfok és a csúcsgráfok, valamint a belőlük Y-Δ átalakítással nyerhető gráfok láncmentesen beágyazhatók.[2] A YΔY-redukálható gráfok azok a gráfok, melyek egyetlen csúcsra redukálhatók Y-Δ transzformációk, az izolált vagy 1 fokszámú csúcsok eltávolítása, illetve a 2 fokszámú csúcsok kompressziója segítségével; ezek szintén minorzártak, és közéjük tartozik az összes síkbarajzolható gráf. Léteznek azonban láncmentesen beágyazható, ám nem YΔY-redukálható gráfok, ilyen például a rombododekaéder 3 fokszámú csúcsainak egy hozzáadott csúcsponthoz kapcsolásával kapott csúcsgráf [10] Léteznek olyan láncmentesen beágyazható gráfok, melyek az említett transzformációkkal csúcsgráffá sem alakíthatók: például a tíz csúcsú koronagráfnak van láncmentes beágyazása, de nem alakítható ilyen módon csúcsgráffá.[2]
A láncmentes beágyazáshoz kapcsolódó fogalom a csomómentes beágyazás, ami a gráf olyan térbe ágyazása, melyben a gráf egyetlen egyszerű köre sem alkot nem triviális csomót. A csomómentes beágyazással nem rendelkező (azaz „eredendően csomós”) gráfok közé tartozik a K7teljes gráf és a K3,3,1,1teljes négyrészes gráf.[11] A csomómentesen beágyazható gráfok minimális tiltott minorai közé tartoznak olyanok is, melyek (az említett két gráftól eltérően) nem kaphatók meg egy eredendően láncolt gráf egy csúccsal történő kibővítésével.[12]
Definiálhatók gráfcsaládok aszerint is, hogy egyes bonyolultabb láncok vagy csomók szerepelnek-e vagy hiányoznak-e a térbe ágyazásukból,[13] vagy hogy láncmentesen beágyazhatók-e valamely az euklideszi tértől különböző háromdimenziós sokaságba.[14] (Flapan, Naimi & Pommersheim 2001) egy gráfbeágyazást háromszorosan láncoltnak (triple linked) neveznek, ha van benne három kör, melyek egyike sem szeparálható a másik kettőtől; megmutatják, hogy a K9 nem eredendően háromszorosan láncolt, a K10 viszont igen.[15] Természetesen adódó általánosítással tetszőleges n-re definiálható az n-szeresen láncolt beágyazás, ami tartalmaz olyan n komponensből álló láncot, ami egy topologikus gömb által nem osztható két részre; minden n-re ismert legalább egy eredendően n-szeresen láncolt minor-minimális gráf.[16]
Története
A kérdés, hogy a K6 teljes gráf rendelkezik-e láncmentes vagy lapos beágyazással, a topológiai kutatóközösségben az 1970-es évek elején merült fel (Bothe 1973) cikkében. A láncmentes beágyazásokra a gráfelméleti közösség figyelmét elsőként Horst Sachs (1983) hívta fel, aki számos kapcsolódó kérdést feltett a láncmentes vagy lapos beágyazással rendelkező gráfok tiltott gráfok szerinti osztályozásával kapcsolatban; Sachs megmutatta, hogy a Petersen-gráfcsalád hét tagja (köztük a K6) nem rendelkezik ilyen beágyazással. Ahogy (Nešetřil & Thomas 1985) megfigyelték. a láncmentesen beágyazható gráfok a minorképzés műveletére nézve zártak, amiből a Robertson–Seymour-tétel alapján következik tiltott minor-alapú osztályozásuk létezése. A véges obstrukciós halmaz létezésének igazolása nem feltétlenül konstrukciós bizonyítás, de Sachs eredményeiből következett, hogy a Petersen-gráfcsalád beletartozik az obstrukciós halmazba. A problémát végül (Robertson, Seymour & Thomas 1995)[17] döntötte el, megmutatva, hogy a Petersen-gráfcsalád hét gráfján kívül nincs más minimális tiltott minora ezeknek a gráfoknak. Tehát a láncmentesen és a laposan beágyazható gráfok ugyanazok a gráfok, melyek úgy jellemezhetők, hogy nem szerepel bennük minorként a Petersen-gráfcsalád egyik tagja sem.
(Sachs 1983) vizsgálta a láncmentesen beágyazható gráfok kromatikus számára és éleinek számára vonatkozó korlátokat. Egy n csúcsú láncmentesen beágyazható gráf éleinek száma legfeljebb 4n − 10: n > 4 esetén a maximális csúcsgráfok pontosan ennyi éllel rendelkeznek,[1] és (Mader 1968) ugyanezt a felső korlátot igazolta a K6-minormentes gráfok általánosabb osztályára. (Nešetřil & Thomas 1985) megfigyelése szerint Sachs kromatikus számra vonatkozó kérdésére választ adna a Hadwiger-sejtés bizonyítása (miszerint bármely k-kromatikus gráf tartalmazza a k csúcsú teljes gráfot minorként). A Hadwiger-sejtés k = 6 esetének (Robertson, Seymour & Thomas 1993c) általi bizonyítása elegendő Sachs kérdésének megválaszolására: a láncmentes gráfok legfeljebb öt színnel színezhetők, mivel egy 6-kromatikus gráf tartalmazza a K6-ot minorként, ezért nem láncmentes, továbbá léteznek láncmentesen beágyazható gráfok (pl. a K5) melyekhez öt színre van szükség. A snark-tételből következik, hogy bármely 3-reguláris láncmentesen beágyazható gráf 3-élszínezhető.
Az algoritmusok kutatóközössége az 1980-as évek végén kezdett foglalkozni a láncmentes beágyazásokkal, (Fellows & Langston 1988) és (Motwani, Raghunathan & Saran 1988) munkáiban. Attól kezdve, hogy a láncmentesen, illetve laposan beágyazható gráfok tiltott minor-alapú karakterizációja rendelkezésre állt, ezen gráfok felismerésének kérdése eldőlt: (Robertson & Seymour 1995) egy algoritmusa polinom időben képes eldönteni, hogy adott gráf tartalmazza-e a hét tiltott minor bármelyikét.[18] Ez a módszer nem konstruálja meg a láncmentes vagy lapos beágyazást, de (van der Holst 2009) későbbi algoritmusa már igen, (Kawarabayashi, Kreutzer & Mohar 2010) pedig hatékonyabb, időben futó algoritmust talált..
(Sachs 1983) utolsó kérdésére, ami a Fáry-tétel láncmentes gráfokra vonatkozó változatáról szól, eddig nem született válasz: vajon a görbe vagy töröttvonalas láncmentes/lapos beágyazás létezéséből következik-e, hogy egyenes szakaszokkal is létrehozható a láncmentes/lapos beágyazás?
Ez a szócikk részben vagy egészben a Linkless embedding című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
↑A Robertson–Seymour-algoritmus erre a problémára való alkalmazását (Fellows & Langston 1988) említi.
Források
Böhme, Thomas (1990), "On spatial representations of graphs", in Bodendieck, Rainer, Contemporary Methods in Graph Theory: In honor of Prof. Dr. Klaus Wagner, Mannheim: Bibliographisches Institut, Wissenschaftsverlag, pp. 151–167, ISBN 978-3-411-14301-6. As cited by (Robertson, Seymour & Thomas 1993a).
Bothe, H.-G. (1973), "Problem P855", Colloquium Mathematicum28: 163, New Scottish Book, Problem 876, 20.5.1972. As cited by (Sachs 1983).
Bowlin, Garry & Foisy, Joel (2004), "Some new intrinsically 3-linked graphs", Journal of Knot Theory and its Ramifications13 (8): 1021–1028, DOI 10.1142/S0218216504003652.
