Gittergraph
Ein Gittergraph ist ein planarer Graph, der so in die Ebene gezeichnet werden kann, dass all seine Knoten auf ganzzahligen Punkten in einem 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>
{{#invoke:Vorlage:Literatur|f}}{{#if: | {{#if: Vorlage:Cite book/ParamBool | Vorlage:Toter Link/archivebot | Vorlage:Webarchiv/archiv-bot }}
}}{{#invoke:TemplatePar|check
|all = title= |opt = vauthors= author= author-link= authorlink= author1= author-link1= author1-link= first= last= first1= last1= first2= last2= author2= first3= last3= author3= first4= last4= author4= first5= last5= author5= first6= last6= author6= first7= last7= author7= first8= last8= author8= others= coauthors= script-title= trans-title= orig-date= orig-year= chapter= chapter-url= editor= editor-first= editor-last= editor-first1= editor-last1= editor-first2= editor-last2= editor-first3= editor-last3= editor-link= editor-link1= language= format= others= series= issue= number= edition= volume= publisher= location= date= year= isbn= page= at= pages= arxiv= doi= jstor= bibcode= pmc= pmid= lccn= oclc= id= url= url-status= access-date= accessdate= archive-url= archiveurl= archive-date= archivedate= quote= url-access= ref= coauthors= origyear= archivebot= offline= |cat = Wikipedia:Vorlagenfehler/Vorlage:Cite book |errNS = 0 |template = Vorlage:Cite book |format = |preview = 1
}}Vorlage:Cite book/URLVorlage:Cite book/Meldung2{{#if: Vorlage:Cite book/ParamBool | Vorlage:Cite book/Meldung }}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:Gurski|^^|0|1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:Irene Rothe, Jörg Rothe, Egon Wanke|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:32|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}</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 isomorph zum Kreisgraphen <math>C_4</math>. Die Gittergraphen der Form <math>G_{2,n}</math> heißen Leitergraphen.
Einzelnachweise
<references />