Tóruszra rajzolható gráf

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez
Egy 14 csúcsú 3-reguláris gráf tóruszba ágyazása

A matematika, azon belül a gráfelmélet területén egy tóruszra rajzolható gráf vagy tóruszba ágyazható gráf (toroidal graph) olyan gráf, melynek létezik tóruszba ágyazása. Más szavakkal a gráf csúcsai elhelyezhetők úgy egy tóruszfelületen, hogy az élei ne metsszék egymást.

Példák[szerkesztés]

Bármely síkbarajzolható gráf tóruszra is rajzolható. Ha a gráf génusza 1, a gráf tóruszra rajzolható, de síkba nem. A Heawood-gráf, a K7 teljes gráf (és így a K5 és a K6 is), a Petersen-gráf (és így a K3,3 teljes páros gráf, mivel a Petersen-gráf tartalmazza annak felosztását), a Blanuša-snarkok egyike,[1] és az összes Möbius-létra is tóruszra rajzolható. Általánosabban, az 1 metszési számú gráfok mind tóruszba ágyazhatók. Néhány magasabb metszési számmal rendelkező gráf is tóruszba ágyazható: például a Möbius–Kantor-gráf, metszési száma 4, mégis tóruszra lehet rajzolni.[2]

Tulajdonságok[szerkesztés]

Tetszőleges tóruszra rajzolható gráf kromatikus száma legfeljebb 7.[3] A K7 teljes gráf jó példa olyan tóruszra rajzolható gráfra, aminek kromatikus száma ténylegesen el is éri a hetet.[4]

A háromszögmentes tóruszra rajzolható gráfok kromatikus száma legfeljebb 4.[5]

A Fáry-tétellel analóg eredmény alapján bármely tóruszra rajzolható gráf lerajzolható egyenes vonalakkal egy periodikus peremfeltételekkel rendelkező téglalapban.[6] Ebben az esetben a Tutte-féle rugók tételének analógiája is működik.[7] A tóruszra rajzolható gráfoknak létezik olyan könyvbe ágyazásuk, melyek legfeljebb 7 lapból állnak.[8]

Obstrukciók[szerkesztés]

A Robertson–Seymour-tétel alapján létezik minimális, nem tóruszra rajzolható gráfok olyan véges H halmaza, hogy bármely gráf pontosan akkor tóruszra rajzolható, ha egyetlen gráfminora sem szerepel H-ban. Más szavakkal H megadja a tóruszra rajzolható gráfok tiltott minor-alapú karakterizációját. A teljes H halmaz nem ismert, de legalább 17 523 gráfot tartalmaz. Más megközelítésben, legalább 250 815 olyan, nem tóruszra rajzolható gráf létezik, ami a topologikus minor-rendezés szerint minimális. Egy gráf pontosan akkor tóruszra rajzolható, ha ezek közül egyiket se tartalmazza topologikus minorként.[9]

Kapcsolódó szócikkek[szerkesztés]

Fordítás[szerkesztés]

  • Ez a szócikk részben vagy egészben a Toroidal graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel.

Jegyzetek[szerkesztés]