En gittergraf är en graf vars ritning , inbäddad i något euklidiskt utrymme R n , bildar en vanlig mosaik . Detta innebär att den grupp av bijektiva transformationer som tar grafen in i sig är ett gitter i gruppteoretisk mening .
Vanligtvis görs ingen tydlig åtskillnad mellan sådana grafer, i den mer abstrakta betydelsen av grafteori, och en ritning i rymden (ofta ett plan eller tredimensionellt rum). Denna typ av graf kan helt enkelt kallas ett gitter för kort . Samma term används dock ofta för de ändliga delarna av oändliga grafer, till exempel "8x8 square lattice".
Termen gitter i litteraturen ges till olika andra typer av grafer med någon regelbunden struktur, såsom den direkta produkten av ett antal kompletta grafer [1] .
Den allmänna formen av en gittergraf (känd under olika namn såsom kvadratgittergrafen ) är en graf vars hörn motsvarar punkter i planet med olika koordinater, x-koordinater i intervallet 1,..., n, y- koordinater i intervallet 1, ..., m, och vars hörn är förbundna med en kant om motsvarande punkter är på ett avstånd av 1. Detta är med andra ord grafen för enhetsavstånd för de angivna punkterna [2] .
Grafen för ett kvadratiskt gitter är en direkt produkt av grafer , nämligen två banor med n-1 och m-1 kanter [2] . Eftersom banan är en mediangraf är grafen för ett kvadratiskt gitter också median. Alla gittergrafer är tvådelade .
En bana kan också betraktas som en gittergraf n gånger 1. En 2x2 gittergraf är en 4-cykel [2] .
En triangulär gittergraf är en graf som motsvarar ett triangulärt gitter. Hanan-grafen för en ändlig uppsättning punkter i planet erhålls från det gitter som erhålls genom skärningspunkten mellan alla vertikala och horisontella linjer som passerar genom varje punkt i uppsättningen.
Torngrafen (grafen som motsvarar alla lagliga torndrag på ett schackbräde ) kallas ibland även gittergrafen .