Wikipédia

Fáry-tétel

gráfelméleti állítás
(Fáry–Wagner-tétel szócikkből átirányítva)
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 szerkeszté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 szerkesztés

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ó.

  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 szerkesztés

  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 szerkesztés

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Fáry-tétel&oldid=26408262”