Gittergraf - Lattice graph
En gittergraf , maskegraf eller gittergraf er en graf, hvis tegning , indlejret i et euklidisk rum R n , danner en regelmæssig flisebelægning . Dette indebærer, at gruppen af bijektive transformationer, der sender grafen til sig selv, er et gitter i gruppeteoretisk forstand .
Typisk skelnes der ikke mellem en sådan graf i den mere abstrakte betydning af grafteori og dens tegning i rummet (ofte flyet eller 3D -rummet). Denne type graf kan snarere kaldes bare et gitter , et net eller et gitter . Desuden bruges disse udtryk også almindeligt for et begrænset afsnit af den uendelige graf, som i "et 8 × 8 firkantet gitter".
Udtrykket gittergraf er også blevet givet i litteraturen til forskellige andre slags grafer med en vis regelmæssig struktur, såsom det kartesiske produkt af en række komplette grafer .
Kvadratisk gittergraf
En almindelig type af en gittergraf (kendt under forskellige navne, såsom kvadratgittergraf ) er grafen, hvis hjørner svarer til punkterne i flyet med heltalskoordinater, x-koordinater er i området 1, ..., n, y-koordinater ligger i området 1, ..., m og to hjørner er forbundet med en kant, når de tilsvarende punkter er i afstand 1. Med andre ord er det en enhedsafstandsgraf for det beskrevne punktsæt.
Ejendomme
En firkantet gittergraf er et kartesisk produkt af grafer , nemlig af to kurver med og kanter. Da en sti -graf er en median -graf , indebærer sidstnævnte kendsgerning, at kvadratgittergrafen også er en median -graf. Alle gittergrafer er topartede , hvilket let kan verificeres ved, at man kan farve hjørnerne på en tavle -måde.
En sti-graf kan også betragtes som en gittergraf på gitteret n gange 1. En 2x2 gittergraf er en 4-cyklus .
Hver plan graf H er en minor af h × h -gitteret, hvor .
Andre slags
En trekantet gittergraf er en graf, der svarer til et trekantet gitter.
En Hanan -gittergraf for et begrænset sæt punkter i flyet frembringes af nettet, der opnås ved skæringer mellem alle lodrette og vandrette linjer gennem hvert punkt i sættet.
Den Tårnet graf (grafen, som repræsenterer alle lovlige træk af tårnet skakbrik på et skakbræt ) er også undertiden kaldes gitter graf , selvom denne graf er strengt anderledes end gitteret graf beskrevet i denne artikel. De gyldige træk af fe -skakbrikker wazir danner firkantet gittergraf.
