Wykres sieciowy - Lattice graph
Kraty wykres , siatki wykres lub wykres siatki , to wykres którego rysunek , osadzone w pewnej przestrzeni euklidesowej R n , tworzy regularną posadzka . Oznacza to, że grupa z bijective przemian , które wysyłają do siebie wykres jest kratownica w sensie teoretycznym grupowego .
Zazwyczaj nie ma wyraźnego rozróżnienia między takim grafem w bardziej abstrakcyjnym sensie teorii grafów a jego rysowaniem w przestrzeni (często na płaszczyźnie lub przestrzeni 3D). Ten typ grafu można w skrócie nazwać po prostu kratą , siatką lub siatką . Co więcej, terminy te są również powszechnie używane dla skończonej części nieskończonego wykresu, jak w „siatce kwadratowej 8×8”.
W literaturze termin graf sieciowy jest również nadawany różnym innym rodzajom grafów o pewnej regularnej strukturze, takich jak iloczyn kartezjański szeregu kompletnych grafów .
Wykres siatki kwadratowej
Popularnym typem grafu kratowego (znanego pod różnymi nazwami, np. graf z siatką kwadratową ) jest graf, którego wierzchołki odpowiadają punktom na płaszczyźnie o współrzędnych całkowitych, przy czym współrzędne x należą do zakresu 1,..., n, Współrzędne y mieszczące się w zakresie 1,..., mi dwa wierzchołki są połączone krawędzią, gdy odpowiadające im punkty znajdują się w odległości 1. Innymi słowy, jest to wykres odległości jednostkowej dla opisanego zbioru punktów.
Nieruchomości
Graf z siatką kwadratową jest iloczynem kartezjańskim grafów , czyli dwóch grafów ścieżkowych z krawędziami i krawędziami. Ponieważ wykres ścieżki jest wykresem mediany , ten ostatni fakt sugeruje, że wykres siatki kwadratowej jest również wykresem mediany. Wszystkie wykresy siatkowe są dwudzielne , co łatwo zweryfikować faktem, że można pokolorować wierzchołki w sposób szachownicowy.
Wykres ścieżkowy może być również uważany za wykres siatkowy na siatce n razy 1. Wykres siatkowy 2x2 jest 4-cyklem .
Każdy graf planarny H jest podrzędną z siatki h × h , gdzie .
Inne rodzaje
Trójkątny wykres siatki to wykres, który odpowiada trójkątnej siatki.
Hanan siatki wykres dla skończonego zbioru punktów na płaszczyźnie jest wytwarzany przez sieć otrzymanej przecięcia wszystkich poziomych i pionowych linii z każdego punktu w odbiorniku.
Na wykres zRook (wykres, który reprezentuje wszystkie ruchy prawne rook kawałek szachy na szachownicy ) jest również czasami nazywana kratownica wykres , chociaż ten wykres jest ściśle inny niż krata wykresie opisanego w tym artykule. Prawidłowe ruchy bajkowego szachownicy wazir tworzą kwadratowy wykres kratowy.