În teoria grafurilor, un graf grilă (în engleză grid graph, uneori numit și lattice graph sau mesh graph) este un graf a cărui în spațiul euclidian formează o pavare regulată. Aceasta implică faptul că grupul transformărilor bijective care lasă graful invariant formează o rețea în sensul teoriei grupurilor.

În practică, de obicei nu se face o distincție clară între graful în sens abstract (din teoria grafurilor) și reprezentarea sa geometrică în spațiu (adesea în plan sau în spațiul tridimensional). Acest tip de graf poate fi numit pe scurt o grilă. În plus, acest termen este utilizat frecvent și pentru o porțiune finită a grafului infinit, de exemplu „o grilă pătrată 8 × 8”.

Graf grilă pătrată

Un tip comun de graf grilă este cel ale cărui vârfuri corespund punctelor din plan cu coordonate întregi, coordonatele fiind în intervalul , iar coordonatele în intervalul . Două vârfuri sunt unite printr-o muchie atunci când punctele corespunzătoare se află la distanța unu. Cu alte cuvinte, este al punctelor întregi dintr-un dreptunghi ale cărui laturi sunt paralele cu axele.

Proprietăți

Un graf grilă pătrată este un , și anume produsul a două cu n − 1 și m − 1 muchii. Deoarece un graf drum este un , rezultă că și graful grilă pătrată este un graf median. Toate grafurile grilă pătrată sunt bipartite, fapt care se verifică ușor prin colorarea vârfurilor în stilul unei table de șah.

Un graf drum este un graf grilă pe grila . Un graf grilă este un de lungime 4.

Orice graf planar H este un al grilei h × h, unde .

Grafurile grilă sunt obiecte fundamentale în teoria minorilor de graf datorită . Ele joacă un rol major în .

Alte tipuri

Un graf grilă triunghiulară este un graf care corespunde unei grile triunghiulare.

Un graf pentru o mulțime finită de puncte din plan se obține din grila formată de intersecțiile tuturor liniilor verticale și orizontale care trec prin fiecare punct al mulțimii.

(graful care reprezintă toate mutările legale ale turei pe o tablă de șah) este uneori numit și graf grilă, deși acesta diferă de graful grilă descris aici, deoarece toate punctele din aceeași linie sau coloană sunt adiacente. Mutările valide ale piesei de numită formează un graf grilă pătrată.

Note

Vezi și

Graf regulat

Categorie:Grafuri planare