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

В теории графов решетчатый граф , сетчатый граф или сетчатый граф — это граф которого рисунок , встроен в некоторое евклидово пространство. $\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]

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

Другие виды [ править ]

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

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

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

См. также [ править ]

Ссылки [ править ]

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

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

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

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

[1]

[2]

[3]