В теории графов решетчатый граф , сетчатый граф или сетчатый граф — это граф , рисунок которого , вложенный в некоторое евклидово пространство , образует регулярную мозаику . Это означает, что группа биективных преобразований , которые переводят граф в самого себя, представляет собой решетку в теоретико-групповом смысле .
Обычно не проводится четкого различия между таким графом в более абстрактном смысле теории графов и его изображением в пространстве (часто на плоскости или в трехмерном пространстве). Этот тип графа короче можно назвать просто решеткой , сеткой или сеткой . Более того, эти термины также обычно используются для конечного участка бесконечного графа, например, «квадратной сетки 8 × 8».
Термин «решетчатый граф» также использовался в литературе для обозначения других видов графов с некоторой регулярной структурой, таких как декартово произведение ряда полных графов . [1]
Распространенный тип решетчатого графа (известный под разными названиями, например, граф с квадратной сеткой ) — это граф, вершины которого соответствуют точкам на плоскости с целочисленными координатами, причем координаты x находятся в диапазоне 1, ..., n , координаты y находятся в диапазоне 1, ..., m , и две вершины соединяются ребром всякий раз, когда соответствующие точки находятся на расстоянии 1. Другими словами, это граф единичных расстояний для описанного набора точек. [2]
Граф с квадратной сеткой — это декартово произведение графов , а именно двух графов путей с n — 1 и m — 1 ребрами. [2] Поскольку граф путей является медианным графом , из последнего факта следует, что граф с квадратной сеткой также является медианным графом. Все графы с квадратной сеткой являются двудольными , в чем легко убедиться, если вершины можно раскрасить в шахматном порядке.
Граф путей также можно рассматривать как сеточный граф на сетке n раз 1. Сетчатый граф 2 × 2 представляет собой 4-цикл . [2]
Каждый планарный граф H является минором сетки h × h , где . [3]
Сеточные графы являются фундаментальными объектами теории миноров графов из-за теоремы исключения сетки . Они играют важную роль в теории двумерности .
Граф треугольной сетки — это график, соответствующий треугольной сетке.
Граф сетки Ханана для конечного набора точек на плоскости создается сеткой, полученной пересечением всех вертикальных и горизонтальных линий, проходящих через каждую точку набора.
Граф ладьи (граф, представляющий все допустимые ходы ладейной шахматной фигуры на шахматной доске ) также иногда называют решеточным графом , хотя этот граф строго отличается от решетчатого графа, описанного в этой статье. Допустимые ходы сказочной шахматной фигуры -вазира образуют квадратную решетчатую диаграмму.
