Külsíkgráf
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ésAz 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ésEgy 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ésAz 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ésEgy 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ésKétszeres összefüggőség és hamiltoniság
szerkesztésEgy 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ésMinden 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ésAz 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
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- ↑ (Felsner 2004).
- ↑ (Chartrand & Harary 1967); (Sysło 1979); (Brandstädt, Le & Spinrad 1999), Proposition 7.3.1, p. 117; (Felsner 2004).
- ↑ (Diestel 2000).
- ↑ a b (Sysło 1979).
- ↑ (Chartrand & Harary 1967); (Sysło 1979).
- ↑ (Li, Corneil & Mendelsohn 2000), Proposition 2.5.
- ↑ a b (Proskurowski & Sysło 1986).
- ↑ (Fiorini 1975).
- ↑ (Lick & White 1970).
- ↑ (Baker 1994).
- ↑ (Scheinerman 1984); (Brandstädt, Le & Spinrad 1999), p. 54.
- ↑ (Brandstädt, Le & Spinrad 1999), p. 174.
- ↑ (Brandstädt, Le & Spinrad 1999), p. 169.
- ↑ (Sysło & Proskurowski 1983).
- ↑ (Kane & Basu 1976); (Sysło 1979).
- ↑ (El-Gindy 1985); (Lin & Skiena 1995); (Brandstädt, Le & Spinrad 1999), Theorem 4.10.3, p. 65.
- ↑ (Wessel & Pöschel 1985); (Unger 1988).
- Baker, Brenda S. (1994), "Approximation algorithms for NP-complete problems on planar graphs", Journal of the ACM 41 (1): 153–180, DOI 10.1145/174644.174650.
- Boza, Luis; Fedriani, Eugenio M. & Núñez, Juan (2004), "The problem of outer embeddings in pseudosurfaces", Ars Combinatoria 71: 79–91.
- Boza, Luis; Fedriani, Eugenio M. & Núñez, Juan (2004), "Obstruction sets for outer-bananas-surface graphs", Ars Combinatoria 73: 65–77.
- Boza, Luis; Fedriani, Eugenio M. & Núñez, Juan (2006), "Uncountable graphs with all their vertices in one face", Acta Mathematica Hungarica 112 (4): 307–313, DOI 10.1007/s10474-006-0082-0.
- Boza, Luis; Fedriani, Eugenio M. & Núñez, Juan (2010), "Outer-embeddability in certain pseudosurfaces arising from three spheres", Discrete Mathematics 310: 3359–3367, DOI 10.1016/j.disc.2010.07.027.
- Brandstädt, Andreas; Le, Van Bang & Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics, ISBN 0-89871-432-X.
- Chartrand, Gary & Harary, Frank (1967), "Planar permutation graphs", Annales de l'Institut Henri Poincaré B 3 (4): 433–438, <http://www.numdam.org/item?id=AIHPB_1967__3_4_433_0>.
- Diestel, Reinhard (2000), Graph Theory, vol. 173, Graduate Texts in Mathematics, Springer-Verlag, p. 107, ISBN 0-387-98976-5.
- El-Gindy, H. (1985), Hierarchical decomposition of polygons with applications, Ph.D. thesis, McGill University. As cited by (Brandstädt, Le & Spinrad 1999).
- Felsner, Stefan (2004), Geometric graphs and arrangements: some chapters from combinational geometry, Vieweg+Teubner Verlag, p. 6, ISBN 978-3-528-06972-8.
- Fiorini, Stanley (1975), "On the chromatic index of outerplanar graphs", Journal of Combinatorial Theory, Series B 18 (1): 35–38, DOI 10.1016/0095-8956(75)90060-X.
- Fisk, Steve (1978), "A short proof of Chvátal's watchman theorem", Journal of Combinatorial Theory, Series B 24: 374, DOI 10.1016/0095-8956(78)90059-X.
- Fleischner, Herbert J.; Geller, D. P. & Harary, Frank (1974), "Outerplanar graphs and weak duals", Journal of the Indian Mathematical Society 38: 215–219.
- Kane, Vinay G. & Basu, Sanat K. (1976), "On the depth of a planar graph", Discrete Mathematics 14 (1): 63–67, DOI 10.1016/0012-365X(76)90006-6.
- Li, Ming-Chu; Corneil, Derek G. & Mendelsohn, Eric (2000), "Pancyclicity and NP-completeness in planar graphs", Discrete Applied Mathematics 98 (3): 219–225, DOI 10.1016/S0166-218X(99)00163-8.
- Lick, Don R. & White, Arthur T. (1970), "k-degenerate graphs", Canadian Journal of Mathematics 22: 1082–1096, doi:10.4153/CJM-1970-125-1, <http://www.smc.math.ca/cjm/v22/p1082> Archiválva 2012. július 23-i dátummal a Wayback Machine-ben.
- Lin, Yaw-Ling & Skiena, Steven S. (1995), "Complexity aspects of visibility graphs", International Journal of Computational Geometry and Applications 5 (3): 289–312, DOI 10.1142/S0218195995000179.
- Proskurowski, Andrzej & Sysło, Maciej M. (1986), "Efficient vertex-and edge-coloring of outerplanar graphs", SIAM Journal on Algebraic and Discrete Methods 7: 131–136, DOI 10.1137/0607016.
- Scheinerman, E. R. (1984), Intersection Classes and Multiple Intersection Parameters of a Graph, Ph.D. thesis, Princeton University. As cited by (Brandstädt, Le & Spinrad 1999).
- Sysło, Maciej M. (1979), "Characterizations of outerplanar graphs", Discrete Mathematics 26 (1): 47–53, DOI 10.1016/0012-365X(79)90060-8.
- 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.
- Unger, Walter (1988), "On the k-colouring of circle-graphs", Proc. 5th Symposium on Theoretical Aspects of Computer Science (STACS '88), vol. 294, Lecture Notes in Computer Science, Springer-Verlag, pp. 61–72, DOI 10.1007/BFb0035832.
- Wessel, W. & Pöschel, R. (1985), "On circle graphs", in Sachs, Horst, Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, October 1st to 5th, 1984, vol. 73, Teubner-Texte zur Mathematik, B.G. Teubner, pp. 207–210. As cited by (Unger 1988).