Решетчатый граф

В теории графов решётчатый граф , сетчатый граф или сетчатый граф — это граф которого рисунок , вложен в некоторое евклидово пространство . $\mathbb {R} ^{n}$ ⁠ образует правильную мозаику . Это означает, что группа биективных преобразований , которые переводят граф в самого себя, представляет собой решетку в теоретико-групповом смысле .

Обычно не проводится четкого различия между таким графом в более абстрактном смысле теории графов и его изображением в пространстве (часто на плоскости или в трехмерном пространстве). Этот тип графа короче можно назвать просто решеткой , сеткой или сеткой . Более того, эти термины также обычно используются для конечного участка бесконечного графа, например, «квадратной сетки 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 , где $h=2|V(H)|+4|E(H)|$ . ^{[ 3 ]}

Сеточные графы являются фундаментальными объектами теории миноров графов из-за теоремы исключения сетки . Они играют важную роль в теории двумерности .

Другие виды

Граф треугольной сетки — это график, соответствующий треугольной сетке.

Граф сетки Ханана для конечного набора точек на плоскости создается сеткой, полученной пересечением всех вертикальных и горизонтальных линий, проходящих через каждую точку набора.

Граф ладьи (граф, представляющий все допустимые ходы ладейной шахматной фигуры на шахматной доске ) также иногда называют решеточным графом , хотя этот граф строго отличается от решетчатого графа, описанного в этой статье. Допустимые ходы сказочной шахматной фигуры- вазира образуют квадратный решетчатый граф.

См. также

Ссылки

^ Вайсштейн, Эрик В. «Решетчатый граф» . Математический мир .
^ Перейти обратно: ^а ^б ^с Вайсштейн, Эрик В. «Сетчатый график» . Математический мир .
^ Робертсон, Н.; Сеймур, П.; Томас, Р. (ноябрь 1994 г.). «Быстрое исключение плоского графа» . Журнал комбинаторной теории, серия B. 62 (2): 323–348. дои : 10.1006/jctb.1994.1073 .

[weiss-lg-1] Вайсштейн, Эрик В. «Решетчатый граф» . Математический мир .

[weiss-gg-2] Перейти обратно: ^а ^б ^с Вайсштейн, Эрик В. «Сетчатый график» . Математический мир .

[3] Робертсон, Н.; Сеймур, П.; Томас, Р. (ноябрь 1994 г.). «Быстрое исключение плоского графа» . Журнал комбинаторной теории, серия B. 62 (2): 323–348. дои : 10.1006/jctb.1994.1073 .

[ 1 ]

[ 2 ]

[ 3 ]