Gittergraph

Ein Gittergraph i​st ein planarer Graph, d​er so i​n die Ebene gezeichnet werden kann, d​ass all s​eine Knoten a​uf ganzzahligen Punkten i​n einem kartesischen Koordinatensystem liegen u​nd alle Kanten d​ie Länge 1 haben. Jeder Gittergraph i​st ein Einheitsdistanz-Graph.

Ein Gittergraph mit 11 × 11 Knoten

Meist werden Gittergraphen ${\displaystyle G_{n,m}}$ betrachtet, deren Zeichnung ein rechteckiges ${\displaystyle n\times m}$ Gitter bildet. Diese lassen sich schreiben als

${\displaystyle 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)}$[1]

Anschaulich bedeutet dies, dass die Knotenmenge ${\displaystyle \{1\dots n\}\times \{1\dots m\}}$ von ${\displaystyle G_{n,m}}$ gerade die Punkte mit den ganzzahligen Koordinaten von ${\displaystyle 1}$ bis ${\displaystyle n}$ auf einer Achse und von ${\displaystyle 1}$ bis ${\displaystyle m}$ auf der anderen Achse eines rechtwinkligen Koordinatensystems enthält. Zwei Knoten ${\displaystyle (i,j)}$ und ${\displaystyle (i',j')}$ sind genau dann durch eine Kante ${\displaystyle \left\{(i,j),(i',j')\right\}}$ verbunden, wenn sie den Abstand 1 haben.

Der Gittergraph ${\displaystyle G_{2,2}}$ besteht aus genau vier Knoten und vier Kanten und ist isomorph zum Kreisgraphen ${\displaystyle C_{4}}$. Die Gittergraphen der Form ${\displaystyle G_{2,n}}$ heißen Leitergraphen.

Einzelnachweise

1. Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: Exakte Algorithmen für schwere Graphenprobleme. Springer, 28. September 2010, ISBN 9783642044991, S. 32.