Mřížový graf je graf , jehož kresba , vložená do nějakého euklidovského prostoru R n , tvoří pravidelnou mozaiku . To znamená, že skupina bijektivních transformací , která přebírá graf do sebe, je mříž v grupově teoretickém smyslu .
Obvykle se mezi takovými grafy v abstraktnějším smyslu teorie grafů a kresbou v prostoru (často v rovině nebo trojrozměrném prostoru) nedělá jasný rozdíl. Tento typ grafu lze zkráceně nazvat jednoduše mřížkou . Stejný termín se však běžně používá pro konečné části nekonečných grafů, jako je „čtvercová mřížka 8x8“.
Pojem mřížka se v literatuře používá pro různé další druhy grafů s nějakou pravidelnou strukturou, jako je přímý součin určitého počtu úplných grafů [1] .
Obecná forma mřížkového grafu (známého pod různými názvy jako čtvercový mřížkový graf ) je graf, jehož vrcholy odpovídají bodům v rovině s různými souřadnicemi, x-ovými souřadnicemi v rozsahu 1,..., n, y- souřadnice v rozsahu 1, ..., m, a jejichž vrcholy jsou spojeny hranou, jsou-li odpovídající body ve vzdálenosti 1. Jinými slovy jde o graf jednotkových vzdáleností pro zadané body [2] .
Graf čtvercové mřížky je přímým součinem grafů , konkrétně dvou cest s n - 1 a m - 1 hran [2] . Protože cesta je mediánovým grafem , pak graf čtvercové mřížky je také mediánem. Všechny mřížkové grafy jsou bipartitní .
Dráhu lze také považovat za mřížkový graf n x 1. Svazový graf 2x2 je 4cyklový [2] .
Trojúhelníkový mřížkový graf je graf odpovídající trojúhelníkové mřížce. Hananův graf pro konečnou množinu bodů v rovině získáme z mřížky získané průsečíkem všech svislých a vodorovných čar procházejících každým bodem množiny.
Věžový graf (graf odpovídající všem zákonným tahům věže na šachovnici ) se někdy nazývá také mřížkový graf .