Fáry-tétel

Nem tévesztendő össze a következővel: Fáry–Milnor-tétel.

A matematika, azon belül a gráfelmélet területén a Fáry-tétel vagy Fáry–Wagner-tétel kimondja, hogy bármely egyszerű síkbarajzolható gráf beágyazható a síkba úgy is, hogy a gráf éleit egyenes szakaszok alkotják. Más szóval, ha megengedjük, hogy a gráf éleit egyenes szakaszok helyett görbék jelöljék, az nem teszi lehetővé több gráf lerajzolását. A tételt Fáry Istvánról nevezték el, bár egymástól függetlenül Klaus Wagner (1936), Fáry (1948) és S. K. Stein (1951) is igazolták.

Bizonyítás

A Fáry-tétel bizonyításának egy indukciós lépése.

A Fáry-tétel igazolható teljes indukcióval.[1] Vegyünk egy n csúccsal rendelkező G egyszerű síkgráfot; ha szükséges, adjunk G-hez éleket addig („háromszögeljük”), amíg maximális síkgráf nem lesz. Ekkor G minden tartománya háromszög lesz, hiszen bármely háromnál több szögű tartományhoz a síkba rajzolhatóság fenntartásával hozzáadható egy új él, ami ellentmond a korábbi követelménynek, hogy G maximális síkgráf. Válasszunk ki három csúcsot: a,b,c, melyik a G háromszögű tartományát alkotják. Teljes indukcióval bizonyítjuk, hogy n-re létezik G-nek olyan egyenes szakaszokból álló síkba rajzolása, melynél az abc háromszög a síkba ágyazás külső tartományával határos. Alapesetként induljunk ki a triviális n = 3 esetből, ahol a, b és c adják G összes csúcsát. Máskülönben bármely G-beli csúcsnak legalább három szomszédja lenne.

A síkgráfokra vonatkozó Euler-formula alapján G éleinek száma 3n − 6; ekvivalens módon, ha definiáljuk G gráf v csúcsának „hiányát” 6 − deg(v)-nek, akkor a hiányok összege 12. G minden csúcsának legfeljebb 3 lehet a hiánya, ezért legalább négy pozitív hiánnyal rendelkező csúcs van a gráfban. Válasszunk egy v csúcsot, ami különbözik az a, b és c csúcsoktól, és legfeljebb 5 szomszéddal rendelkezik. A G' gráfot szerkesszük meg úgy, hogy a v csúcsot eltávolítjuk G-ből, és az így kapott tartományt újraháromszögeljük. Az indukció alapján a G'-nek létezik egyenes szakaszokból álló síkba rajzolása, melynél az abc a külső tartománnyal határos. Eltávolítva a G'-hez hozzáadott éleket egy legfeljebb öt oldalú P sokszög jön létre, amibe v-t illesztve készül el a síkba rajzolás. Chvátal művészeti galéria tétele alapján létezik P-nek olyan belső pontja, amibe v-t elhelyezve a v-nek a P csúcsaihoz húzott élei nem metszik a többi élt, ezzel befejezve a bizonyítást.

A bizonyítás indukciós lépése a jobb oldali ábrán látható.

Kapcsolódó eredmények

De Fraysseix, Pach és Pollack megmutatták, hogy lehetséges lineáris időben megtalálni egy a gráf méretével lineáris méretű (négyzetes méretű univerzális ponthalmazt alkotó) rácson a gráf egyenes szakaszos reprezentációját. Schnyder hasonló módszerrel igazolt javított korlátokat és karakterizációt a síkgráfokkal kapcsolatban, az incidencia-részbenrendezett halmaz alapján. Munkája arra volt kihegyezve, hogy létezik a maximális síkgráfok éleinek egy speciális, három fagráffá történő particionálása, amit Schnyder woodnak neveznek.

A Tutte-féle rugók tétele állítása szerint minden 3-szorosan összefüggő síkbarajzolható gráf lerajzolható a síkban oly módon, hogy élei egyenes szakaszok, és a külső tartomány konvex sokszög (Tutte 1963). A tétel nevének az az eredete, hogy az ilyen beágyazás a gráf éleibe helyezett rugórendszer egyensúlyi helyzetének ismeretében állítható elő.

A Steinitz-tétel kimondja, hogy minden 3-szorosan összefüggő síkbarajzolható gráf kifejezhető egy háromdimenziós térbeli konvex poliéder éleiként. Egy G {\displaystyle G} gráf a Tutte-féle rugók tételében leírt egyenes szakaszos síkba rajzolása megkapható a poliéder-megfeleltetés síkra vetítésével.

A körpakolási tétel szerint minden síkgráf reprezentálható a sík egymást nem metsző körei metszetgráfjaként. A gráf minden csúcsát a megfelelő kör középpontjába helyezve megkapható az egyenes szakaszokkal történő reprezentáció.

A matematika megoldatlan problémája:
Van-e minden síkbarajzolható gráfnak egész hosszúságú egyenes szakaszokkal történő síkba rajzolása?
(A matematika további megoldatlan problémái)

Heiko Harborth vetette fel, hogy vajon lerajzolható-e minden síkbarajzolható gráf egyenes szakaszokkal oly módon, hogy az élek hosszai egész számok legyenek.[2] A Harborth-sejtés jelenleg (2016) megoldatlan. Egész hosszúságú szakaszokkal történő síkba ágyazások azonban egyes gráfosztályok esetében léteznek, ilyenek például a 3-reguláris gráfok.[3]

(Sachs 1983) felteszi a kérdést, hogy vajon minden láncmentesen beágyazható gráf esetén létezik-e a három dimenziós euklideszi térbe való olyan láncmentes beágyazás is, amiben az éleket egyenes szakaszok reprezentálják – ez a Fáry-tétel háromdimenziós analógiájának tekinthető.

Jegyzetek

  1. ↑ Ez a bizonyítás megtalálható: Chartrand, Gary; Lesniak, Linda & Zhang, Ping (2010), Graphs & Digraphs (5th ed.), CRC Press, pp. 259–260, ISBN 9781439826270, <http://books.google.com/books?id=K6-FvXRlKsQC&pg=PA259>.
  2. ↑ (Harborth et al. 1987); (Kemnitz & Harborth 2001); (Mohar & Thomassen 2001); (Mohar 2003).
  3. ↑ (Geelen, Guo & McKinnon 2008).

Irodalom

  • Fáry, István (1948), "On straight-line representation of planar graphs", Acta Sci. Math. (Szeged) 11: 229–233.
  • de Fraysseix, Hubert; Pach, János & Pollack, Richard (1988), "Small sets supporting Fary embeddings of planar graphs", Twentieth Annual ACM Symposium on Theory of Computing, pp. 426–433, ISBN 0-89791-264-0, DOI 10.1145/62212.62254.
  • de Fraysseix, Hubert; Pach, János & Pollack, Richard (1990), "How to draw a planar graph on a grid", Combinatorica 10: 41–51, DOI 10.1007/BF02122694.
  • Geelen, Jim; Guo, Anjie & McKinnon, David (2008), "Straight line embeddings of cubic planar graphs with integer edge lengths", J. Graph Theory 58 (3): 270–274, doi:10.1002/jgt.20304, <http://www.math.uwaterloo.ca/~dmckinnon/Papers/Planar.pdf>.
  • Harborth, H.; Kemnitz, A. & Moller, M. et al. (1987), "Ganzzahlige planare Darstellungen der platonischen Korper", Elem. Math. 42: 118–122.
  • Kemnitz, A. & Harborth, H. (2001), "Plane integral drawings of planar graphs", Discrete Math. 236: 191–195, DOI 10.1016/S0012-365X(00)00442-8.
  • Mohar, Bojan (2003), Problems from the book Graphs on Surfaces, <http://www.fmf.uni-lj.si/~mohar/Book/BookProblems.html>.
  • Mohar, Bojan & Thomassen, Carsten (2001), Graphs on Surfaces, Johns Hopkins University Press, pp. roblem 2.8.15, ISBN 0-8018-6689-8.
  • Sachs, Horst (1983), "On a spatial analogue of Kuratowski's theorem on planar graphs — An open problem", in Horowiecki, M.; Kennedy, J. W. & Sysło, M. M., Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981, vol. 1018, Lecture Notes in Mathematics, Springer-Verlag, pp. 230–241, ISBN 978-3-540-12687-4, DOI 10.1007/BFb0071633.
  • Schnyder, Walter (1990), "Embedding planar graphs on the grid", Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA), pp. 138–148, <http://portal.acm.org/citation.cfm?id=320176.320191>.
  • Stein, S. K. (1951), "Convex maps", Proceedings of the American Mathematical Society 2 (3): 464–466, DOI 10.2307/2031777.
  • Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society 13: 743–767, DOI 10.1112/plms/s3-13.1.743.
  • Wagner, Klaus (1936), "Bemerkungen zum Vierfarbenproblem", Jahresbericht der Deutschen Mathematiker-Vereinigung 46: 26–32, <http://www.digizeitschriften.de/index.php?id=resolveppn&PPN=GDZPPN002131633>.