Külsíkgráf

A Wikipédiából, a szabad enciklopédiából
(Outerplanar gráf szócikkből átirányítva)
Egy maximális külsíkgráf és 3-színezése
A K4 teljes gráf a legkisebb síkgráf, ami nem outerplanáris

A matematika, azon belül a gráfelmélet területén egy külsíkgráf, outerplanáris vagy outerplanar gráf olyan síkba rajzolható gráf, amely rendelkezik olyan síkba rajzolással, ahol az összes csúcs a rajzolás külső tartományába esik.

A külsíkgráfok (a síkgráfok Wagner-tételével analóg módon) leírhatók két tiltott minoruk, a K4 és K2,3, vagy Colin de Verdière-gráfinvariánsuk alapján. Akkor és csak akkor rendelkeznek Hamilton-körrel, ha kétszeresen összefüggőek, mely esetben a Hamilton-kör egyértelmű és éppen a külső tartomány alkotja azt. Minden külsíkgráf 3 színnel színezhető, degeneráltságuk és favastagságuk legfeljebb 2.

Az outerplanar gráfok a síkgráfok részhalmazát képezik; a soros-párhuzamos gráfok és a húrmetszetgráfok részgráfjai. A maximális külsíkgráfok, melyekhez nem adható új él az outerplanaritás fenntartásával, húrgráfok és láthatósági gráfok is egyben.

Történetük[szerkesztés]

Az outerplanar gráfok nevüket az őket elsőként tanulmányozó (Chartrand & Harary 1967)-tól kapták. Chartrand és Harary egy alapgráf két kópiájának teljes párosítással való összekötésével (például az általánosított Petersen-gráfok egy része így állítható elő két egyforma körgráfból) kapott gráfok síkba rajzolhatósága eldöntésének problémáját tanulmányozva jutottak el az outerplanar gráfokhoz. Megmutatták, hogy ha az alapgráf kétszeresen összefüggő, az említett módon kapott gráf pontosan akkor síkgráf, ha az alapgráf külsíkgráf és a párosítás a külső körrel diéder-permutációt alkot. Chartrand és Harary igazolták a Kuratowski-tétel analógját külsíkgráfokra, miszerint egy gráf akkor és csak akkor külsíkgráf, ha nem tartalmazza homeomorf részgráfként sem a K4, sem a K2,3 gráfot.

Meghatározás és karakterizáció[szerkesztés]

Egy külsíkgráf olyan irányítatlan gráf, amely metszésmentesen beágyazható az euklideszi síkba oly módon, hogy az összes csúcs a rajzolás végtelen lapjához tartozzék. Más szóval, egyetlen csúcsot sem vesznek körül teljesen élek. Egy másik megfogalmazás szerint, egy G gráf akkor outerplanáris, ha a minden más csúcshoz éllel csatlakozó új csúcs hozzáadásával kapott G' gráf síkgráf.[1]

Egy maximális külsíkgráf olyan külsíkgráf, amelyhez nem lehetséges új éleket hozzáadni az outerplanaritás fenntartásával. Minden n csúcsú maximális külsíkgráfnak pontosan 2n − 3 éle van, és minden véges tartománya háromszög alakú.

Tiltott gráfok[szerkesztés]

Az outerplanáris gráfoknak létezik tiltott gráfok szerinti osztályozásuk a síkgráfokra vonatkozó Kuratowski-tétellel és Wagner-tétellel analóg módon: egy gráf akkor és csak akkor outerplanáris, ha nem tartalmazza homeomorf részgráfként sem a K4 teljes gráfot, sem a K2,3 teljes páros gráfot.[2] Alternatív meghatározás szerint egy gráf akkor és csak akkor outerplanáris, ha nem tartalmazza a K4 vagy K2,3 gráfot gráfminorként, azaz élek törlésével, összehúzásával megkapható kisebb gráfként.[3]

Egy háromszögmentes gráf akkor és csak akkor külsíkgráf, ha nem tartalmazza homeomorf részgráfként a K2,3-at.[4]

Colin de Verdière-gráfinvariáns[szerkesztés]

Egy gráf akkor és csak akkor külsíkgráf, ha a hozzátartozó Colin de Verdière-gráfinvariáns legfeljebb 2. A hasonló módon karakterizált gráfok közül azok a gráfok, melyek Colin de Verdière-invariánsa legfeljebb 1, 3 vagy 4 a lineáris erdők, síkgráfok és láncmentes beágyazással rendelkező gráfok.

Tulajdonságok[szerkesztés]

Kétszeres összefüggőség és hamiltoniság[szerkesztés]

Egy külsíkgráf akkor és csak akkor kétszeresen összefüggő, ha a külső tartománya egyszerű, azaz ismétlődés nélküli kört alkot. Egy külsíkgráf akkor és csak akkor hamiltoni, ha kétszeresen összefüggő; ebben az esetben a külső tartomány alkotja az egyetlen Hamilton-körét.[5] Általánosabban, a külsíkgráf leghosszabb körének nagysága megegyezik a legnagyobb kétszeresen összefüggő komponense csúcsainak számával. Az előbbi okokból a külsíkgráfok Hamilton-köreinek, illetve leghosszabb köreinek megkeresése lineáris időben megoldható feladat, míg általános gráfokra a probléma NP-teljes.

A maximális külsíkgráfok a hamiltoniságnál erősebb feltételnek is megfelelnek: csúcs-pánciklikusok (), tehát egy n csúcsú maximális külsíkgráf bármely v csúcsához és bármely 3≤k≤n számhoz tartozik v-t tartalmazó, k hosszúságú kör. Adott hosszúságú kör megkapható a gráfhoz egyetlen éllel kapcsolódó háromszögek ismétlődő eltávolításával (úgy, hogy az eltávolított csúcs ne a v legyen), amíg a maradék gráf külső tartománya éppen k méretű.[6]

Egy síkgráf pontosan akkor külsíkgráf, ha minden kétszeresen összefüggő komponense is külsíkgráf.[4]

Színezés[szerkesztés]

Minden hurokmentes külsíkgráf kiszínezhető legfeljebb három szín felhasználásával;[7] ez a tény nagy jelentőséget kap a Chvátal-féle művészeti galéria probléma egyszerűsített bizonyításában, amit (Fisk 1978) végzett el. A 3-színezés lineáris idő alatt megtalálható egy mohó színezési algoritmussal, ami eltávolít egy legfeljebb 2 fokszámú csúcsot, a maradék gráfot rekurzívan kiszínezi, majd az eltávolított csúcsot visszahelyezi a két szomszédjától eltérő színnel.

A Vizing-tétel szerint bármely gráf élkromatikus száma (az élek színezéséhez szükséges színek minimális száma, ha nem engedjük meg, hogy két szomszédos él azonos színű legyen) vagy a gráf maximális fokszáma, vagy a maximális fokszám plusz 1. A külsíkgráfok esetében azonban az élkromatikus szám csaknem mindig megegyezik a maximális fokszámmal, kivéve azt az esetet, amikor a gráf egy páratlan hosszúságú kört alkot.[8] Az optimális számú színnel történő élszínezés lineáris idejű algoritmussal megtalálható, a gyenge duális fa szélességi keresését alapul véve.[7]

Egyéb tulajdonságok[szerkesztés]

Az outerplanar gráfok degeneráltsága legfeljebb 2: minden részgráfja tartalmaz legfeljebb 2 fokszámú csúcsot.[9]

Az outerplanar gráfok favastagsága legfeljebb 2, amiből következik, hogy számos gráfoptimalizálási probléma, ami általános gráfok esetében NP-teljes, dinamikus programozás útján polinomiális időben megoldható a külsíkgráfokra. Általánosabban, a k-külsíkgráfok (lásd lentebb) favastagsága O(k).[10]

Minden külsíkgráf megadható a síkban tengelyükkel egymáshoz igazodó téglalapok metszetgráfjaként, ezért a külsíkgráfok boxicity tulajdonsága legfeljebb 2.[11]

Kapcsolódó gráfcsaládok[szerkesztés]

Egy kaktuszgráf. A kaktuszforma a külsíkgráfok egy típusa.

Minden külsíkgráf egyben síkgráf is. Minden külsíkgráf egy soros-párhuzamos gráf részgráfja.[12] Azonban nem minden soros-párhuzamos síkgráf külsíkgráf. A K2,3 teljes páros gráf síkgráf és soros-párhuzamos, de nem külsíkgráf. A K4 teljes gráf pedig síkgráf, de se nem soros-párhuzamos, sem pedig külsíkgráf. Minden fa és kaktusz külsíkgráf.[13]

Egy beágyazott külsíkgráf gyenge duálisa (az a gráf, aminek minden csúcsa a beágyazás egy korlátos tartományának felel meg, élei pedig a szomszédos korlátos tartományoknak megfelelő csúcsok között húzódnak) erdő, egy Halin-gráf gyenge duálisa pedig külsíkgráf. Egy síkgráf akkor és csak akkor outerplanar, ha gyenge duálisa erdő, akkor és csak akkor Halin-gráf, ha gyenge duálisa kétszeresen összefüggő és outerplanar.[14]

Értelmezhető az outerplanaritás mértéke. Egy gráf 1-outerplanar beágyazása megegyezik a külsíkgráf-beágyazással. A k > 1 értékekre egy síkba rajzolás akkor k-outerplanar, ha a külső tartomány csúcsainak eltávolításával (k − 1)-outerplanar beágyazást kapunk. Egy gráf akkor k-outerplanar vagy k-külsíkgráf, ha van k-outerplanar beágyazása.[15]

Egy outer-1-síkgráf vagy kül-1-síkgráf, az 1-síkgráfok analógiájára lerajzolható egy korongra úgy, hogy a csúcsok a határon legyenek és élenként legfeljebb egy metszés essen.

Minden maximális külsíkgráf húrgráf. Minden maximális külsíkgráf egy egyszerű sokszög láthatósági gráfja.[16] A maximális külsíkgráfok előállíthatók sokszögek háromszögelése útján. A maximális külsíkgráfok 2-fák, soros-párhuzamos gráfok és húrgráfok.

Minden outerplanar gráf megadható egy kör húrjainak metszetgráfjaként, tehát húrmetszési gráfok.[17]

Jegyzetek[szerkesztés]

  1. ↑ (Felsner 2004).
  2. ↑ (Chartrand & Harary 1967); (Sysło 1979); (Brandstädt, Le & Spinrad 1999), Proposition 7.3.1, p. 117; (Felsner 2004).
  3. ↑ (Diestel 2000).
  4. ↑ a b (Sysło 1979).
  5. ↑ (Chartrand & Harary 1967); (Sysło 1979).
  6. ↑ (Li, Corneil & Mendelsohn 2000), Proposition 2.5.
  7. ↑ a b (Proskurowski & Sysło 1986).
  8. ↑ (Fiorini 1975).
  9. ↑ (Lick & White 1970).
  10. ↑ (Baker 1994).
  11. ↑ (Scheinerman 1984); (Brandstädt, Le & Spinrad 1999), p. 54.
  12. ↑ (Brandstädt, Le & Spinrad 1999), p. 174.
  13. ↑ (Brandstädt, Le & Spinrad 1999), p. 169.
  14. ↑ (Sysło & Proskurowski 1983).
  15. ↑ (Kane & Basu 1976); (Sysło 1979).
  16. ↑ (El-Gindy 1985); (Lin & Skiena 1995); (Brandstädt, Le & Spinrad 1999), Theorem 4.10.3, p. 65.
  17. ↑ (Wessel & Pöschel 1985); (Unger 1988).

További információk[szerkesztés]

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Külsíkgráf&oldid=26468250”