Rácsgráf

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]

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 ${\displaystyle h=2|V(H)|+4|E(H)|}$ .^[3]

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.

• Rácsséta
• Pick-tétel
• Egész oldalú háromszög
• Háló (matematika)

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