Rácsgráf
A matematika, azon belül a gráfelmélet területén egy rácsgráf, csempézési gráf vagy hálógráf (lattice graph, mesh graph vagy grid graph) olyan gráf, melynek valamely Rn euklideszi térbe történő beágyazása szabályos csempézést alkot. Ebből az is következik, hogy a gráfot saját magába vivő bijektív transzformáció csoportja maga is háló, csoportelméleti értelemben.
Általában nem tesznek éles különbségtételt az absztrakt gráfelméleti rácsgráf és annak lerajzolása (gyakran síkba vagy 3D térbe rajzolása) között. Ezt a fajta gráfot röviden rácsnak vagy hálónak is nevezik (lattice, mesh, grid), de használják ezeket a kifejezéseket a végtelen gráf valamely véges részletének leírására is, például „egy 8×8-as rács”.
A hálógráf (lattice graph) kifejezést a szakirodalomban esetenként más, valamely szabályos szerkezettel rendelkező gráfra is alkalmazzák, mint például teljes gráfok Descartes-szorzatára.[1]
Derékszögű rácsgráf szerkesztés
A rácsgráfok gyakori típusa a derékszögű rácsgráf, négyzetrácsgráf vagy négyzethálógráf (square grid graph); ennek a gráfnak a csúcsai a sík egész koordinátájú pontjainak felelnek meg, ahol az x koordináták 1…n közé, az y koordináták pedig 1…m közé esnek, és két csúcs közt akkor húzódik él, ha a nekik megfelelő pontok közötti távolság éppen 1. Más szavakkal, a leírt ponthalmaz egységtávolsággráfjáról van szó.[2]
Tulajdonságok szerkesztés
A derékszögű rácsgráf az n - 1 és m - 1 élű útgráfok Descartes-szorzatával áll elő.[2] Mivel az útgráfok mediángráfok, ezért a derékszögű rácsgráf is mediángráf. Minden rácsgráf páros, ami könnyen ellenőrizhető a csúcsok sakktáblaszerű kiszínezésével.
Egy útgráf tekinthető n×1-es rácsgráfnak is. A 2×2-es rácsgráf megegyezik a 4-körrel.[2]
Minden H síkbarajzolható gráf a h×h-rács minora, ahol .[3]
Egyéb fajtái szerkesztés
A háromszögrácsgráf olyan gráf, ami egy háromszögű rácsnak felel meg.
A sík véges ponthalmazának Hanan-rácsa olyan gráf, amit a halmaz pontjain keresztül húzott összes függőleges és vízszintes egyenes metszéspontjai határoznak meg.
Néha a bástyagráfot (a sakkjátékban szereplő bástya nevű figura sakktáblán lehetséges lépéseit megjelenítő gráfot) is rácsgráfnak nevezik.
Kapcsolódó szócikkek szerkesztés
Fordítás szerkesztés
- Ez a szócikk részben vagy egészben a Lattice 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. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek szerkesztés
- ↑ Weisstein, Eric W.: Lattice graph (angol nyelven). Wolfram MathWorld
- ↑ a b c Weisstein, Eric W.: Grid graph (angol nyelven). Wolfram MathWorld
- ↑ (1994. november 1.) „Quickly Excluding a Planar Graph”. Journal of Combinatorial Theory, Series B 62 (2), 323–348. o. DOI:10.1006/jctb.1994.1073.