Latice (teoria grafurilor)

Un graf latice este un graf al cărui desen , încorporat într-un spațiu euclidian R n , formează un mozaic regulat . Aceasta implică faptul că grupul de transformări bijective care ia graficul în sine este o rețea în sensul teoretic al grupului .

De obicei, nu se face o distincție clară între astfel de grafice, în sensul mai abstract al teoriei grafurilor, și un desen în spațiu (adesea un spațiu plan sau tridimensional). Acest tip de grafic poate fi numit pur și simplu o rețea pe scurt . Cu toate acestea, același termen este folosit în mod obișnuit pentru părțile finite ale graficelor infinite, cum ar fi „8x8 zăbrele pătrate”.

Termenul de zăbrele din literatură este atribuit diferitelor alte tipuri de grafuri cu o structură regulată, cum ar fi produsul direct al unui număr de grafuri complete [1] .

Grafice ale unei rețele pătrate

Forma generală a unui grafic lattice (cunoscut sub diferite denumiri, cum ar fi graficul lattice pătrat ) este un grafic ale cărui vârfuri corespund unor puncte din plan cu coordonate diferite, coordonate x în intervalul 1,..., n, y- coordonate în intervalul 1, ..., m și ale căror vârfuri sunt conectate printr-o muchie dacă punctele corespunzătoare sunt la o distanță de 1. Cu alte cuvinte, acesta este graficul distanțelor unitare pentru punctele specificate [2] .

Proprietăți

Graficul unei rețele pătrate este un produs direct al graficelor , și anume două căi cu muchii n - 1 și m - 1 [2] . Deoarece calea este un grafic median , atunci graficul unei rețele pătrate este și el median. Toate graficele latice sunt bipartite .

O cale poate fi, de asemenea, considerată un grafic reticulat n cu 1. Un graf reticulat 2x2 este un grafic cu 4 cicluri [2] .

Alte tipuri

Un grafic cu rețea triunghiulară este un grafic care corespunde unei rețele triunghiulare. Graficul Hanan pentru o mulțime finită de puncte din plan este obținut din rețeaua obținută prin intersecția tuturor liniilor verticale și orizontale care trec prin fiecare punct al mulțimii.

Graficul turnului (graficul corespunzător tuturor mișcărilor legale de turn pe o tablă de șah ) este uneori numit și graficul lattice .

Vezi și

Note

  1. Weisstein, Eric W. Grafic Lattice  pe site- ul web Wolfram MathWorld .
  2. 1 2 3 Weisstein, Eric W. Grafic grilă  (engleză) pe site-ul web Wolfram MathWorld .