Gittergraph

Datei:Karopapier.png

Karopapier kann als die Darstellung eines Gittergraphen verstanden werden.

Ein Gittergraph ist eine graphentheoretische Struktur.

Im zweidimmensionalen Fall lassen sie sich schreiben als $G_{n,m}:=\left(\{1\dots n\}\times \{1\dots m\},\left\{\left\{(i,j),(i',j')\right\}\mid |i-i'|+|j-j'|=1\right\}\right)$

Anschaulich ist handelt es sich bei den Knoten von $G_{n,m}$ im kartesischen Koordinatensystem um die Punkte mit Koordinaten aus $\mathbb {N}$, die auf einer Achse nicht größer als $n$ und auf der anderen nicht größer als $m$ sind. Zwei Knoten sind genau dann verbunden, wenn sie den Abstand 1 haben.