Решётка (теория графов)

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

Обычно не делается явного различия между такими графами в более абстрактном смысле теории графов и рисунком в пространстве (часто на плоскости или трёхмерном пространстве). Этот тип графов можно коротко называть просто решёткой. Однако тот же термин обычно используется для конечных частей бесконечных графов, как, например, "8×8 квадратная решётка".

Термин решётка в литературе даётся различным другим видам графов с некоторой регулярной структурой, таким как прямое произведение некоторого числа полных графов[1].

Графы квадратной решётки

Общий вид графа решётки (известной под различными именами, такими как граф квадратной решётки) — это граф, вершины которого соответствуют точкам на плоскости с различными координатами, x-координатами из диапазона 1,..., n, y-координатами из диапазона 1,..., m, и вершины которого соединены ребром, если соответствующие точки находятся на расстоянии 1. Другими словами, это граф единичных расстояний для указанных точек[2].

Свойства

Граф квадратной решётки — это прямое произведение графов, а именно двух путей с n - 1 и m - 1 рёбрами[2]. Поскольку путь — это медианный граф, то граф квадратной решётки является также медианным. Все графы решёток являются двудольными.

Путь тоже можно считать графом решётки n на 1. Граф решётки 2x2 — это 4-цикл[2].

Другие виды

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

Ладейный граф (граф, соответствующий всем допустимым ходам ладьи на шахматной доске), иногда также называется графом решётки.

См. также

Примечания
  1. Weisstein, Eric W. Lattice graph (англ.) на сайте Wolfram MathWorld.
  2. Weisstein, Eric W. Grid graph (англ.) на сайте Wolfram MathWorld.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.