Síkbarajzolható gráf

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.

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

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 $K_{5}$-tel (az ötcsúcsú teljes gráffal) vagy $K_{3,3}$-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 K₅-öt vagy a K_3,3-at nem tartalmazza részgráfjaként, azonban részgráfként tartalmaz egy K_3,3-mal homeomorf gráfot (a K_3,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 $K_{5}$, sem a $K_{3,3}$ nem minora.

Animáció, mely megmutatja, hogy a Petersen-gráf minorként tartalmazza a K_3,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 K₅ és a K_3,3.

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

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 $G$-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 $3t$, legfeljebb $2e$. Tehát $3t\leq 2e$, felhasználva az Euler-formulát, $3(e-v+2)\leq 2e$. Ezt az egyenlőtlenséget átrendezve adódik, hogy $e\leq 3v-6$. 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 $4t\leq 2e$ és az Euler-formula alkalmazásával, hogy $e\leq 2v-4$.

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(v²)-nél. Tekintsük például a K_3,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.

• A Whitney-féle síkgráfkritérium a grafikus matroidok duálisának létezésén alapuló karakterizáció;
• A Mac Lane-féle síkgráfkritérium a véges síkgráfok algebrai jellemzését adja, körterei alapján;
• A Fraysseix–Rosenstiehl-féle síkgráfkritérium a mélységi keresés kográf-fa élei kétfelé particionálásának létezésére alapoz jellemzést. A bal-jobb síkgráfteszt-algoritmus alapját képezi;
• A Schnyder-tétel a szomszédsági részbenrendezés dimenziószáma alapján adja a síkba rajzolhatóság karakterizációját;
• A Colin de Verdière-síkgráfkritérium a gráf által meghatározott bizonyos Schrödinger-operátorai második sajátértékeinek maximális multiplicitása alapján jellemzi a síkbarajzolható gráfokat.
• A Hanani–Tutte-tétel állítása szerint egy gráf pontosan akkor síkgráf, ha van olyan lerajzolása, melyben a független élpárok páros alkalommal metszik egymást; ezzel és egy modulo 2 egyenletrendszerrel jellemezhetők a síkbarajzolható gráfok.

Euler-formula

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

$v-e+f=2$.

Például a fenti pillangógráf esetében v = 5, e = 6 és f = 3. A K₄ 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 $m$-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 $m$ é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:

$e\leq 3v-6$.

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

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

Átlagos fokszám

A $v-e+f=2$ és $2e\geq 3f$ (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

Példa a körpakolási tételre a K⁻₅ 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.

Duális gráf

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

Egy síkba rajzolható gráf duális gráfja alatt azt a gráfot értjük, amelynek csúcsai az eredeti gráf tartományai, és azok a csúcsok vannak összekötve, amik megfelelői szomszédosak voltak (ha több él mentén voltak szomszédosak, akkor többszörösen is). Síkbarajzolható gráf duálisa is síkbarajzolható gráf.

Kapcsolódó gráfcsaládok

Maximális síkgráfok

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 vagy triangulated graph) 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.

Külsíkgráfok

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 K₄ 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 K₄-et vagy a K_2,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

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.

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

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 csomómentesen beágyazható gráfok jelentenek, melyek úgy ágyazhatók a háromdimenziós térbe, hogy köreik összekapcsolódási szám 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 K₅-öt és a K_3,3-at minorként, a csomómentesen 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 csomómentesen 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

Az $n$ csúcsú, címkézett síkbarajzolható gráfok száma aszimptotikusan $g\cdot n^{-7/2}\cdot \gamma ^{n}\cdot n!$, ahol $\gamma \approx 27,22687$ és $g\approx 0,43\times 10^{-5}$.

Az $n$ csúcsú, címkézetlen, nem izomorf síkbarajzolható gráfok száma $27,2^{n}$ és $30,06^{n}$ között van.

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

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

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.

Jegyzetek

• Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie", Fundamenta Mathematicae 15: 271–283, <http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf>.
• Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen 114: 570–590, DOI 10.1007/BF01594196.
• Boyer, John M. & Myrvold, Wendy J. (2005), "On the cutting edge: Simplified O(n) planarity by edge addition", Journal of Graph Algorithms and Applications 8 (3): 241–273, doi:10.7155/jgaa.00091, <http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf>.
• McKay, Brendan & Brinkmann, Gunnar, A useful planar graph generator, <http://cs.anu.edu.au/~bdm/plantri/>.
• de Fraysseix, H.; Ossona de Mendez, P. & Rosenstiehl, P. (2006), "Trémaux trees and planarity", International Journal of Foundations of Computer Science 17 (5): 1017–1029, DOI 10.1142/S0129054106004248. Special Issue on Graph Drawing.
• D.A. Bader and S. Sreshta, A New Parallel Algorithm for Planarity Testing, UNM-ECE Technical Report 03-002, October 1, 2003.
• Fisk, Steve (1978), "A short proof of Chvátal's watchman theorem", Journal of Combinatorial Theory, Series B 24 (3): 374, DOI 10.1016/0095-8956(78)90059-X.

További információk

A Wikimédia Commons tartalmaz Síkbarajzolható gráf témájú médiaállományokat.

• Edge Addition Planarity Algorithm Source Code, version 1.0 — Free C source code for reference implementation of Boyer–Myrvold planarity algorithm, which provides both a combinatorial planar embedder and Kuratowski subgraph isolator. An open source project with free licensing provides the Edge Addition Planarity Algorithms, current version.
• Public Implementation of a Graph Algorithm Library and Editor — GPL graph algorithm library including planarity testing, planarity embedder and Kuratowski subgraph exhibition in linear time.
• Boost Graph Library tools for planar graphs, including linear time planarity testing, embedding, Kuratowski subgraph isolation, and straight-line drawing.
• 3 Utilities Puzzle and Planar Graphs
• NetLogo Planarity model — NetLogo version of John Tantalo's game