olyan gráf, amit le lehet rajzolni egy síkra anélkül, hogy az élei (a csúcsokon kívül) metszenék egymást From Wikipedia, the free encyclopedia
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]
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 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.
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:
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: •—•—•).
A Wagner-tétel felosztások helyett minorokkal foglalkozik:
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.
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:
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.
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:
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.
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]
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.
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.
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]
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.
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 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.
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]
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]
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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.