Решетки график , сетки график , или сетки график , представляет собой график , чей рисунок , встроенные в некотором евклидовом пространстве R п , образует регулярную черепицу . Это означает , что группа из биективных преобразований , которые посылают граф себе является решеткой в теоретико - групповой смысле .
Обычно не делается четкого различия между таким графом в более абстрактном смысле теории графов и его рисованием в пространстве (часто на плоскости или в трехмерном пространстве). Этот тип графа вкратце можно назвать просто решеткой , сеткой или сеткой . Более того, эти термины также обычно используются для конечного участка бесконечного графа, например, «квадратная сетка 8 × 8».
Термин решетчатый граф также использовался в литературе для обозначения различных других типов графов с некоторой регулярной структурой, таких как декартово произведение ряда полных графов . [1]
Квадратная сетка [ править ]
Распространенным типом решетчатого графа (известного под разными именами, например, граф с квадратной сеткой ) является граф, вершины которого соответствуют точкам на плоскости с целочисленными координатами, координаты x находятся в диапазоне 1, ..., n, y-координаты находятся в диапазоне 1, ..., m, и две вершины соединяются ребром всякий раз, когда соответствующие точки находятся на расстоянии 1. Другими словами, это график единичных расстояний для описанного набора точек. [2]
Свойства [ править ]
Квадратная сетка граф является декартово произведением графов , а именно, из двух путей графов с и краев. [2] Поскольку граф путей является медианным графом , последний факт означает, что граф с квадратной сеткой также является медианным графом. Все сеточные графы двудольные , что легко проверяется тем фактом, что вершины можно раскрасить в шахматном порядке.
Граф путей также можно рассматривать как сеточный граф на сетке n раз 1. Граф сетки 2x2 представляет собой 4- тактный граф . [2]
Каждый плоский граф H является несовершеннолетний в ч × ч -grid, где . [3]
Другие виды [ править ]
Треугольная сетка графики представляют собой график , который соответствует треугольной сетке.
Сетки Ханан график для конечного множества точек на плоскости производится с помощью сетки , полученной путем пересечения всех вертикальных и горизонтальных линий , через каждую точку множества.
Граф ладьи (граф, который представляет все допустимые ходы ладьей шахматной фигуры на шахматной доске ) также иногда называют решетчатым графом , хотя этот граф строго отличается от решетчатого графа, описанного в этой статье. Допустимые ходы волшебной шахматной фигуры wazir образуют граф квадратной решетки.
См. Также [ править ]
- Решетчатый путь
- Теорема Пика
- Целочисленные треугольники в двумерной решетке
- Решетка (заказ)
Ссылки [ править ]
- ^ Вайсштейн, Эрик В. "Решетчатый граф" . MathWorld .
- ^ a b c Вайсштейн, Эрик В. «Сетка графа» . MathWorld .
- ^ Робертсон, N .; Seymour, P .; Томас Р. (ноябрь 1994 г.). «Быстрое исключение плоского графа». Журнал комбинаторной теории, серии B . 62 (2): 323–348. DOI : 10.1006 / jctb.1994.1073 .
