imported>Minzgreen: SVG

2023-06-09T16:50:21Z

SVG

Neue Seite

[[Datei:100 grid.svg|mini|Ein Gittergraph mit 11 × 11 Knoten]]
Ein '''Gittergraph''' ist ein [[planarer Graph]], der so in die Ebene gezeichnet werden kann, dass all seine Knoten auf ganzzahligen Punkten in einem [[kartesisches Koordinatensystem|kartesischen Koordinatensystem]] liegen und alle Kanten die Länge 1 haben. Jeder Gittergraph ist ein [[Einheitsdistanz-Graph]].

Meist werden Gittergraphen <math>G_{n,m}</math> betrachtet, deren Zeichnung ein rechteckiges <math>n\times m</math> Gitter bildet. Diese lassen sich schreiben als
:<math>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)</math><ref>
{{Cite book
| publisher = Springer
| isbn = 9783642044991
| last = Gurski
| first = Frank
| coauthors = Irene Rothe, Jörg Rothe, Egon Wanke
| title = Exakte Algorithmen für schwere Graphenprobleme
| date = 2010-09-28
| pages = 32
| url = https://books.google.de/books?id=J-rkKToSlRYC&lpg=PA32&ots=pw8pFpVqPK&dq=gittergraph+definition&pg=PA32&hl=de#v=onepage&q&f=false
}}</ref>
Anschaulich bedeutet dies, dass die Knotenmenge <math>\{1 \dots n\}\times \{1\dots m\}</math> von <math>G_{n,m}</math> gerade die Punkte mit den ganzzahligen Koordinaten von <math>1</math> bis <math>n</math> auf einer Achse und von <math>1</math> bis <math>m</math> auf der anderen Achse eines rechtwinkligen Koordinatensystems enthält. Zwei Knoten <math>(i,j)</math> und <math>(i',j')</math> sind genau dann durch eine Kante <math>\left\{(i,j),(i',j')\right\}</math> verbunden, wenn sie den Abstand 1 haben.

Der Gittergraph <math>G_{2,2}</math> besteht aus genau vier Knoten und vier Kanten und ist [[Isomorphie von Graphen|isomorph]] zum [[Kreisgraph]]en <math>C_4</math>. Die Gittergraphen der Form <math>G_{2,n}</math> heißen [[Leitergraph]]en.

== Einzelnachweise ==
<references />

[[Kategorie:Geometrischer Graph]]

Gittergraph - Versionsgeschichte

imported>Minzgreen: SVG