Ugrás a tartalomhoz

Síkbarajzolható gráf

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából
Példagráfok
Síkbarajzolható Síkba nem rajzolható

Pillangógráf

K5 Teljes gráf

K4 Teljes gráf

K3,3
Három ház–három kút-gráf

A matematika, azon belül a gráfelmélet területén egy síkbarajzolható gráf olyan gráf, melynek létezik a síkba való beágyazása, tehát lerajzolható úgy a síkon, hogy élei kizárólag a csúcspontokban találkoznak (metszési száma 0), vagy más megfogalmazásban, lerajzolható a síkban anélkül, hogy élei metszenék egymást.[1]

A gráf ilyen lerajzolása a síkgráf (plane graph), avagy a gráf síkra rajzolása, síkba ágyazása (planar embedding of the graph). Egy síkgráf meghatározható úgy is, hogy egy síkbarajzolható gráf minden csúcsához hozzárendeljük a sík egy pontját, minden éléhez pedig olyan síkgörbét, melynek végpontjai az él két csúcsához rendelt síkbeli pontok, és a síkgráfhoz tartozó görbék a végpontjaiktól eltekintve diszjunktak. Néha síkbarajzolható gráf helyett is a síkgráf kifejezést használják.

Sztereografikus projekcióval igazolható, hogy egy gráf akkor és csak akkor síkbarajzolható, ha gömbre rajzolható. A Fáry–Wagner-tétel szerint egy síkba rajzolható egyszerű gráf úgy is síkba rajzolható, hogy élei egyenes szakaszok.

A síkgráfok kombinatorikus térképekkel is reprezentálhatóak.

A topologikusan ekvivalens gömbre rajzolások ekvivalenciaosztályát síktérképnek (planar map) nevezik. Bár egy síkgráf rendelkezik külső vagy nem korlátos tartománnyal, a síktérkép egyik tartományának sincs megkülönböztetett státusza.

A síkbarajzolható gráfok általánosítása az adott génuszú (nemszámú) felületre rajzolható gráfok. Ezen terminológia szerint a síkba rajzolható gráfok nemszáma 0, mivel a sík (és a gömb) 0 nemszámú felületek. Lásd még: gráf beágyazása.

Kuratowski és Wagner tétele

[szerkesztés]

Kazimierz Kuratowski lengyel matematikus a síkbarajzolható gráfok tiltott gráfok szerinti osztályozását adta, mely Kuratowski-tétel néven ismeretes:

Egy véges gráf akkor és csak akkor síkbarajzolható, ha nem tartalmaz olyan részgráfot, amely topologikusan izomorf -tel (az ötcsúcsú teljes gráffal) vagy -mal (az ún. három ház–három kút gráffal).

A topologikus izomorfia tetszőleges számú csúcs elhagyását vagy él felosztását teszi lehetővé (például a •——• él változtatását erre: •—•—•).

Példagráf, ami magát a K5-öt vagy a K3,3-at nem tartalmazza részgráfjaként, azonban részgráfként tartalmaz egy K3,3-mal homeomorf gráfot (a K3,3 egy felosztását), ezért nem síkbarajzolható.

A Wagner-tétel felosztások helyett minorokkal foglalkozik:

Egy véges gráf akkor és csak akkor síkbarajzolható, ha sem a , sem a nem minora.
Animáció, mely megmutatja, hogy a Petersen-gráf minorként tartalmazza a K3,3 gráfot

Klaus Wagner általánosabb kérdése az volt, hogy vajon bármely minorképzés műveletére zárt gráfosztály meghatározható-e tiltott minorok véges halmazával. A válasz igen, az eredményt tanulmányok hosszú sorában bizonyították, és Robertson–Seymour-tétel néven ismeretes. A tétel nyelvezete szerint a véges síkbarajzolható gráfok tiltott minorai a K5 és a K3,3.

Egyéb síkbarajzolhatósági kritériumok

[szerkesztés]

A gyakorlatban nem túl hatékony a Kuratowski-féle kritériumok alapján eldönteni, hogy adott gráf síkba rajzolható-e. Léteznek azonban gyors algoritmusok is erre a problémára: egy n csúcsú gráf esetében O(n) (lineáris idő) alatt eldönthető, hogy a gráfnak létezik-e síkba rajzolása (lásd Síkgráfság tesztelése).

Egy összefüggő, egyszerű síkbarajzolható gráf, mely v csúccsal és e éllel rendelkezik, igazak a következők:

1. tétel. Ha v ≥ 3, akkor e ≤ 3v − 6;
2. tétel. Ha v ≥ 3 és nincsenek 3 hosszúságú körök, akkor e ≤ 2v − 4.

Az 1. tétel bizonyítása: rajzoljuk le -t síkba. Mivel a gráf egyszerű, minden tartományát legalább 3 él határolja, ugyanakkor egy él legfeljebb két tartományt határolhat. Összegezzük minden tartományra az őket határoló élek számát. Az előbbiek miatt ez az érték legalább , legfeljebb . Tehát , felhasználva az Euler-formulát, . Ezt az egyenlőtlenséget átrendezve adódik, hogy . A 2. tétel igazolása hasonló gondolatmenettel történhet, mint az előzőé, figyelembe véve, hogy most minden tartományt legalább 4 él határol. Ebből adódik, hogy és az Euler-formula alkalmazásával, hogy .

A fenti kritériumok szerint a síkgráfok ritka gráfok, mivel csak O(v) éllel rendelkeznek, aszimptotikusan jóval kevesebbel a maximális O(v2)-nél. Tekintsük például a K3,3 gráfot, melynek 6 csúcsa és 9 éle van, de nem tartalmaz 3 hosszúságú kört. Ezért a 2. tétel értelmében nem lehet síkgráf. Jegyezzük meg, hogy ezek a tételek a síkba rajzolhatóságnak szükséges, de nem elégséges feltételeit adják meg, ezért csak egy gráf síkba rajzolhatóságának cáfolatára használhatók. Ha az 1. és a 2. tétel is kevésnek bizonyul, más módszereket kell keresni.

Euler-formula

[szerkesztés]

Az Euler-formula azt mondja ki, hogy ha adott egy véges összefüggő síkgráf, és v a csúcsok, e az élek, f (faces) pedig a tartományok (élekkel határolt területek, beleértve a külső, végtelen nagy területet is) száma, akkor

.

Például a fenti pillangógráf esetében v = 5, e = 6 és f = 3. A K4 teljes gráf esetében v = 4, e = 6 és f = 4. Általában igaz, hogy ha minden f tartománnyal rendelkező síkgráfra igaz a tulajdonság, egy olyan változtatás, ami új tartományt hoz létre, de a gráfot síkgráfként megtartja, a v − e + f értékét nem változtatja. Mivel a tulajdonság igaz minden f = 2 gráfra, teljes indukció alapján minden esetre igaz. Az Euler-formula így is igazolható: először vegyük észre, hogy minden belső, korlátos tartományt a gráf egy köre határol. Ebből adódik, hogy egy síkba rajzolt fának csak egy tartománya van, ez a külső, nem korlátos tartomány. Tudjuk, hogy minden fának 1-gyel kevesebb éle van, mint ahány csúcsa. Egyszerű számolással adódik, hogy a fákra teljesül az Euler-formula. Most bebizonyítjuk az állítást a kört tartalmazó, összefüggő gráfokra is. Tekintsük a gráf valamely körének egy -mel jelölt élét. Ez az él határa egy a körön belüli és egy a körön kívüli tartománynak. Az él elhagyásával a két tartomány egyesül. Tehát az élek és a tartományok száma egyaránt 1-gyel csökken, míg a csúcsok száma nem változik. Így ha az új gráfra teljesül az Euler-formula, akkor az eredetire is. Az eljárást (egy körbeli él elhagyása) folytassuk addig, ameddig a gráfban nem marad kör. Ekkor a gráf egy feszítőfájához jutunk, amelyre teljesül a formula, tehát az eredeti gráfra is.

Véges, összefüggő egyszerű síkgráfban a külső tartomány kivételével minden tartományt legalább három él határol, és minden él legfeljebb két tartománnyal szomszédos; az Euler-formula alapján megmutatható, hogy ezek a gráfok ritkák, abban az értelemben, hogy ha v ≥ 3:

.
Szabályos dodekaéder Schlegel-diagramja, egy konvex poliéderből képezett síkgráf.

Az Euler-formula konvex poliéderekre is érvényes. Ez nem véletlen: minden konvex poliéder átalakítható egy összefüggő, egyszerű síkgráffá a poliéder Schlegel-diagramja segítségével, ami a poliéder perspektivikus vetítése egy síkra, ahol a vetítés középpontja a poliéder valamely lapjának a közepéhez van közel. Nem minden síkgráf feleltethető meg egy komplex poliédernek: például egyetlen fa sem. A Steinitz-tétel kimondja, hogy a konvex poliéderekből képezett poliédergráfok pontosan a 3-szorosan összefüggő egyszerű síkba rajzolható gráfok. Általánosabban, az Euler-képlet minden olyan poliéderre vonatkozik, melynek felülete a gömbbel topolológiailag izomorf, tekintet nélkül arra, hogy konvex-e.

Nem összefüggő gráfokra

[szerkesztés]

Az Euler-formula síkbarajzolható, egyszerű, összefüggő komponensből álló gráfokra a következőképpen módosul: , ahol a csúcsok, a tartományok, az élek számát jelöli.[2]

Átlagos fokszám

[szerkesztés]

A és (egy tartományt legalább 3 él határol, egy él legfeljebb 2 tartományhoz tartozik) összefüggésekből algebrai átalakítások után következik, hogy a véges, síkba rajzolható gráfok átlagos fokszáma 6-nál kisebb.

Érmegráfok

[szerkesztés]
Példa a körpakolási tételre a K5 gráfon, ami egy él híján az 5 csúcsú teljes gráf.

A síkban két simulókör pontosan egy pontban metszi egymást. Egy „érmegráf” egymás belső területét át nem fedő körök által alkotott érintőgráf, ahol a gráf minden csúcsa egy körnek felel meg, és két kör érintkezésekor a körökhöz tartozó csúcsok között él húzódik. A Paul Kobe által 1936-ban bizonyított körpakolási tétel szerint egy gráf pontosan akkor síkbarajzolható, ha érmegráf.

Az eredmény felhasználásával könnyű bizonyítás adódik a Fáry-tételre, ami kimondja, hogy ha egy gráf síkbarajzolható, akkor ez megtörténhet egyenes szakaszok használatával is. Ha a gráf csúcsait az érmegráf-reprezentáció megfelelő köreinek középpontjába helyezzük, az érintő körök középpontjai között húzódó egyenes szakaszok nem metszenek egyetlen más szakaszt sem.

Kapcsolódó gráfcsaládok

[szerkesztés]

Maximális síkgráfok

[szerkesztés]
A Goldner–Harary-gráf maximális síkgráf. Minden véges tartományát három él határolja.

Egy egyszerű gráf akkor maximális síkbarajzolható gráf, ha síkba rajzolható, de tetszőleges él hozzáadása után elveszítené ezt a tulajdonságát. Ekkor minden tartományát (a külsőt is beleértve) három él határolja, ami megmagyarázza az alternatív plane triangulation („síkháromszögelés”) elnevezést. A „háromszögelt gráf” (triangular graph[3] vagy triangulated graph)[4] elnevezéseket inkább a teljes gráfok élgráfjaira és a merev körű gráfokra szokás alkalmazni. Minden maximális síkgráf 3-szorosan csúcsösszefüggő.

Ha egy maximális síkbarajzolható gráf v > 2 csúccsal rendelkezik, akkor pontosan 3v − 6 éle és 2v − 4 tartománya van.

Az Apollóniusz-hálózatok olyan maximális síkbarajzolható gráfok, melyek háromszögű tartományok kisebb háromszög-hármasokra való feldarabolásával keletkeznek. Ezzel ekvivalens meghatározásuk szerint a síkba rajzolható 3-fák.

A lekötött gráfok olyan gráfok, melyek minden periferikus köre háromszög. Egy maximális síkbarajzolható gráfban (és általánosabban, bármely poliédergráfban) a periferikus körök a tartományokkal egyeznek meg, tehát a maximális síkbarajzolható gráfok lekötöttek. A lekötött gráfok közé tartoznak a merev körű gráfok, és a lekötött gráfok pontosan azok a gráfok, melyek merev körű gráfokból és maximális síkgráfokból előállíthatók a klikk-összeg művelet segítségével.[5]

Külsíkgráfok

[szerkesztés]

A külsíkgráfok (outerplanar vagy outerplanáris gráfok) olyan gráfok, melyek beágyazhatók a síkba oly módon, hogy minden csúcsuk a beágyazás a külső, végtelen tartományához tartozzon. Minden külsíkgráf síkgráf, de a fordítottja nem igaz: a K4 síkgráf, de nem külsíkgráf. A Kuratowski-tételhez hasonló tétel kimondja, hogy egy véges gráf akkor és csak akkor külsíkgráf, ha nem tartalmazza homeomorf részgráfként a K4-et vagy a K2,3-at.

Egy gráf 1-külsíkba rajzolása megegyezik a külsíkba rajzolásával. A k > 1 esetekben egy gráf síkba rajzolása akkor k-külsíkba rajzolás, ha a külső tartományhoz tartozó csúcsok eltávolításával egy (k − 1)-külsíkba rajzolás jön létre. Egy gráf akkor k-külsíkgráf, ha van neki k-külsíkba rajzolása.

Halin-gráfok

[szerkesztés]

A Halin-gráfok irányítatlan, 2 fokszámú csúcsok nélküli fákból állíthatók elő a levelek körökbe csatolásával, a síkba ágyazás által meghatározott sorrendben. Ezzel ekvivalens meghatározásban olyan poliédergráfok, melyeknek egy kijelölt tartománya az összes többivel szomszédos. Minden Halin-gráf síkbarajzolható. A külsíkgráfokhoz hasonlóan a Halin-gráfok favastagsága is alacsony, ami miatt számos probléma könnyebben megoldható rajtuk, mint az általános síkgráfokon.[6]

Egyéb kapcsolódó gráfcsaládok

[szerkesztés]

Egy csúcsgráf (apex graph) olyan gráf, ami egyetlen csúcsának eltávolításával síkbarajzolhatóvá tehető; egy k-csúcsgráf legfeljebb k csúcs eltávolításával síkbarajzolhatóvá alakítható.

Egy 1-síkgráf olyan gráf, ami lerajzolható a síkba úgy, hogy minden élt legfeljebb egyszer messen egy másik; egy k-síkgráf olyan gráf, ami lerajzolható élenként legfeljebb k metszéssel. A többszörös metszést egyik esetben sem engedjük meg.

Egy térképgráf olyan gráf, amit a sík véges sok. egyszeresen összefüggő, belsejük tekintetétben diszjunkt régióiból lehet előállítani úgy, hogy a csúcsok a régiók, két csúcsot pedig akkor köt össze él, ha a hozzájuk tartozó régiók legalább egy határpontban találkoznak. Ha legfeljebb három régió találkozik egy pontban, a térképgráf síkba rajzolható, de ha négy vagy több régió találkozik, már nem feltétlenül.

Egy tóruszra rajzolható gráf olyan gráf, ami metsző élek nélkül beágyazható egy tóruszra. Általánosabban tekintve, egy gráf nemszáma (génusza) annak a minimális nemszámú kétdimenziós felületnek a nemszáma, melybe a gráf beágyazható; a síkbarajzolható gráfok génusza 0, síkba nem, de tóruszra rajzolható gráfok génusza 1.

A háromdimenziós térbe bármely gráf élmetszés nélkül beágyazható. Létezik azonban a síkba rajzolhatóság háromdimenziós analógiája, amit a láncmentesen beágyazható gráfok jelentenek, melyek úgy ágyazhatók a háromdimenziós térbe, hogy köreik összekapcsolódási száma 0 legyen (semelyik két köre se legyen topológiailag kapcsolódva). A síkgráfok Kuratowski-, illetve Wagner-féle jellemzéséhez hasonlóan, miszerint a síkbarajzolható gráfok nem tartalmazzák a K5-öt és a K3,3-at minorként, a láncmentesen beágyazható gráfok nem tartalmazzák a Petersen-gráfcsalád hét tagjának egyikét sem minorként. A külsíkgráfok, illetve síkbarajzolható gráfok azok a gráfok, melyek Colin de Verdière-gráfinvariánsa legfeljebb 2 vagy 3; a láncmentesen beágyazható gráfok invariánsa legfeljebb négy lehet.

Egy felfelé síkbarajzolható gráf olyan irányított körmentes gráf, mely lerajzolható úgy a síkba, hogy élei egymást nem metsző, felfelé irányítású görbék legyenek. Nem minden síkba rajzolható irányított körmentes gráf felfelé síkbarajzolható, és NP-teljes annak eldöntése, hogy adott gráf felfelé síkbarajzolható-e.

Síkbarajzolható gráfok leszámlálása

[szerkesztés]

Az csúcsú, címkézett síkbarajzolható gráfok száma aszimptotikusan , ahol és .[7]

Az csúcsú, címkézetlen, nem izomorf síkbarajzolható gráfok száma és között van.[8]

Csaknem minden síkbarajzolható gráf exponenciális számú automorfizmussal rendelkezik.[9]

További tények és definíciók

[szerkesztés]

Minden síkbarajzolható gráf 4 részes, azaz színezhető legfeljebb négy színnel. Ezt a négyszín-tétel mondja ki.

A Fáry-tétel kimondja, hogy minden egyszerű síkbarajzolható gráf olyan módon is lerajzolható, hogy élei egymást nem metsző egyenes szakaszok legyenek. Egy univerzális ponthalmaz olyan pontok halmaza a síkban, hogy bármely n csúcsú gráfnak létezik olyan síkba ágyazása, ahol az összes csúcs a halmaz pontjainak valamelyikén van. Létezik a csúcsok számával négyzetesen arányos méretű univerzális ponthalmaz, egyszerűen az egész koordinátájú négyzetrácsot tekintve. Bármely egyszerű külsíkgráf, és így bármely fa is beágyazható a síkba úgy, hogy az összes csúcs egy körön legyen, az élek pedig a körlemezen belül lévő, egymást nem metsző egyenes szakaszok, ezért az n-csúcsú szabályos sokszögek az n csúcsú külsíkgráfok univerzális ponthalmazai. Kevésbé nyilvánvaló, de ez n általános helyzetű pontra is igaz.[10]

Síkba rajzolható gráf és duálisa

Egy összefüggő, de nem feltétlenül egyszerű G gráf síkba rajzolásához tartozó G* duális gráf a következőképpen konstruálható: a G gráf minden tartománya (a korlátlant is beleértve) G* egy csúcsának felel meg, és G* csúcsait akkor kötjük össze, ha G-beli megfelelői szomszédosak voltak (ha több él mentén voltak szomszédosak, akkor többszörösen is). Így G*, mely maga is síkgráf, ugyanannyi éllel rendelkezik, mint G, ugyanannyi csúccsal, ahány tartománya volt G-nek és ugyanannyi tartománnyal, ahány csúcsa volt G-nek. A „duális” kifejezést az indokolja, hogy G** = G; itt az egyenlőség a gömbfelületbe ágyazás ekvivalenciájának a jele. Ha G egy konvex poliédernek megfelelő síkgráf, akkor G* a poliéder duálisának megfelelő síkgráf.

A duális gráfok azért is hasznosak, mert számos tulajdonságuk egyszerű módon kapcsolódik az eredeti gráf tulajdonságához, így egyes gráfokkal kapcsolatos eredmények bizonyíthatók úgy is, ha a gráfok duálisait vesszük alapul.

Bár a síkbaágyazható gráf egy konkrét beágyazásához tartozó duálisok egyediek (izomorfia erejéig), egy gráfnak létezhetnek különböző (nem izomorf) duálisai, melyek különböző (nem homeomorf) beágyazásaiból származnak.

Egy euklideszi gráf olyan gráf, melynek csúcsai a sík pontjainak felelnek meg, éleinek súlyozása pedig a pontok közötti euklideszi távolságnak; lásd geometriai gráfelmélet.

Egy síkgráf akkor konvex, ha minden tartományát (természetesen a végtelen tartományon kívül) konvex sokszögek határolják. Egy síkbarajzolható gráfnak pontosan akkor létezik konvex síkba rajzolása, ha egy 3-szorosan összefüggő síkgráf felosztásával előállítható.

A Scheinerman-sejtés (most már tétel) kimondja, hogy minden síkbarajzolható gráf előállítható a sík egyenes szakaszainak metszetgráfjaként.

A síkgráf-elválasztási tétel kimondja, hogy minden n-csúcsú síkbarajzolható gráf O(√n) csúcs eltávolításával két, legfeljebb 2n/3 méretű részgráfra particionálható. Ennek következménye, hogy a síkbarajzolható gráfok favastagsága és fafelbontásának szélessége szintén O(√n).

Két, v csúcsú síkbarajzolható gráfról O(v) időben eldönthető, hogy izomorfak-e vagy nem (lásd gráfizomorfizmus-probléma).[11]

Egy síkbarajzolható gráf behálózottsági együtthatója (meshedness coefficient) normalizálja a korlátos tartományok számát (ami megegyezik a gráf ciklomatikus rangjával, a Mac Lane-féle síkgráfkritérium alapján) úgy, hogy elosztja 2n − 5-tel, tehát az n csúcsú síkgráfban lehetséges korlátos tartományok maximális számával. Így az együttható értéke 0 (fák) és 1 (maximális síkgráfok) között mozoghat.[12]

Fordítás

[szerkesztés]
  • Ez a szócikk részben vagy egészben a Planar graph 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.

Jegyzetek

[szerkesztés]
  1. Trudeau, Richard J.. Introduction to Graph Theory, Corrected, enlarged republication., New York: Dover Pub., 64. o. (1993). ISBN 978-0-486-67870-2. Hozzáférés ideje: 2012. augusztus 8. „Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them.” 
  2. Rajzoljuk le síkba a gráfot. Ekkor külön-külön mind a komponensre teljesül az Euler-formula. Mivel minden csúcs és minden él pontosan egy komponenshez tartozik, és , ahol és az -edik komponens csúcsainak, illetve éleinek száma. A „külső” tartományok azonban mindegyik komponensnél azonosak, ezért . A komponensekre felírt Euler-formulából adódik az állítás.
  3. Schnyder, W. (1989), "Planar graphs and poset dimension", Order 5: 323–343, DOI 10.1007/BF00353652.
  4. Bhasker, Jayaram & Sahni, Sartaj (1988), "A linear algorithm to find a rectangular dual of a planar triangulated graph", Algorithmica 3 (1–4): 247–278, DOI 10.1007/BF01762117.
  5. Seymour, P. D. & Weaver, R. W. (1984), "A generalization of chordal graphs", Journal of Graph Theory 8 (2): 241–251, DOI 10.1002/jgt.3190080206.
  6. Sysło, Maciej M. & Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, vol. 1018, Lecture Notes in Mathematics, Springer-Verlag, pp. 248–256, DOI 10.1007/BFb0071635.
  7. (2009) „Asymptotic enumeration and limit laws of planar graphs”. Journal of the American Mathematical Society 22, 309–329. o. DOI:10.1090/s0894-0347-08-00624-3.  
  8. (2006) „Planar Graphs, via Well-Orderly Maps and Trees”. Graphs and Combinatorics 22, 185–202. o. DOI:10.1007/s00373-006-0647-2.  
  9. „Random planar graphs”. Journal of Combinatorial Theory, Series B 93 (2), 187–205. o. DOI:10.1016/j.jctb.2004.09.007.  
  10. (Gritzmann et al. 1991).
  11. I. S. Filotti, Jack N. Mayer. A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus. Proceedings of the 12th Annual ACM Symposium on Theory of Computing, p.236–243. 1980.
  12. Buhl, J.; Gautrais, J. & Sole, R.V. et al. (2004), "Efficiency and robustness in ant networks of galleries", European Physical Journal B: Condensed Matter and Complex Systems (Springer-Verlag) 42 (1): 123–129, DOI 10.1140/epjb/e2004-00364-9.

Források

[szerkesztés]

További információk

[szerkesztés]
Commons:Category:Planar graphs
A Wikimédia Commons tartalmaz Síkbarajzolható gráf témájú médiaállományokat.