Fáry-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 Sablon:Harvs, Sablon:Harvs és Sablon:Harvs is igazolták.
Bizonyítás
A Fáry-tétel igazolható teljes indukcióval.[1] Vegyünk egy Sablon:Math csúccsal rendelkező Sablon:Mvar egyszerű síkgráfot; ha szükséges, adjunk Sablon:Math-hez éleket addig („háromszögeljük”), amíg maximális síkgráf nem lesz. Ekkor Sablon:Mvar 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 Sablon:Math maximális síkgráf. Válasszunk ki három csúcsot: Sablon:Math, melyik a Sablon:Math háromszögű tartományát alkotják. Teljes indukcióval bizonyítjuk, hogy Sablon:Mvar-re létezik Sablon:Math-nek olyan egyenes szakaszokból álló síkba rajzolása, melynél az Sablon:Math háromszög a síkba ágyazás külső tartományával határos. Alapesetként induljunk ki a triviális Sablon:Math esetből, ahol Sablon:Mvar, Sablon:Mvar és Sablon:Mvar adják Sablon:Mvar összes csúcsát. Máskülönben bármely Sablon:Mvar-beli csúcsnak legalább három szomszédja lenne.
A síkgráfokra vonatkozó Euler-formula alapján Sablon:Mvar éleinek száma Sablon:Math; ekvivalens módon, ha definiáljuk Sablon:Mvar gráf Sablon:Mvar csúcsának „hiányát” Sablon:Math-nek, akkor a hiányok összege Sablon:Math. Sablon:Mvar 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 Sablon:Mvar csúcsot, ami különbözik az Sablon:Mvar, Sablon:Mvar és Sablon:Mvar csúcsoktól, és legfeljebb 5 szomszéddal rendelkezik. A Sablon:Math gráfot szerkesszük meg úgy, hogy a Sablon:Math csúcsot eltávolítjuk Sablon:Mvar-ből, és az így kapott tartományt újraháromszögeljük. Az indukció alapján a Sablon:Mvar-nek létezik egyenes szakaszokból álló síkba rajzolása, melynél az Sablon:Mvar a külső tartománnyal határos. Eltávolítva a Sablon:Mvar-hez hozzáadott éleket egy legfeljebb öt oldalú Sablon:Mvar sokszög jön létre, amibe Sablon:Mvar-t illesztve készül el a síkba rajzolás. Chvátal művészeti galéria tétele alapján létezik Sablon:Mvar-nek olyan belső pontja, amibe Sablon:Mvar-t elhelyezve a Sablon:Math-nek a Sablon:Mvar 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ó. Sablon:Clear
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 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ó. Sablon:Megoldatlan 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]
Sablon:Harvtxt 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
Irodalom
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation.
- ↑ Ez a bizonyítás megtalálható: Sablon:Citation.
- ↑ Sablon:Harvtxt; Sablon:Harvtxt; Sablon:Harvtxt; Sablon:Harvtxt.
- ↑ Sablon:Harvtxt.