Решетчатый граф
-
Определение решетчатого графа
- Решетчатый граф — это граф, который можно представить в евклидовом пространстве как правильную черепицу.
- Группа биективных преобразований, сохраняющих граф, образует решетку в теоретико-групповом смысле.
-
Использование термина
- Термин «решетчатый граф» может использоваться для обозначения как абстрактного графа, так и его отображения в пространстве.
- Термин также применяется к конечным участкам бесконечных графов и к другим графам с регулярной структурой.
-
Примеры решетчатых графов
- Квадратный сетчатый граф — это граф с вершинами на плоскости, соединенными ребрами на расстоянии 1 друг от друга.
- График с треугольной сеткой соответствует треугольной сетке на плоскости.
- График сетки Ханана строится путем пересечения вертикальных и горизонтальных линий через точки на плоскости.
-
Свойства решетчатых графов
- Графы с квадратной сеткой являются декартовыми произведениями графов путей и медианными графами.
- Все графы с квадратной сеткой являются двудольными.
- График траектории может рассматриваться как график сетки на сетке, умноженный на n раз.
- Сеточные графы играют важную роль в теории младших графов и теории двумерности.
-
Другие виды решетчатых графов
- Ладейный граф иногда называют решетчатым графом, но он отличается от описанного в статье.
- Графики с другими фигурами, такими как вазир в сказочных шахматах, также могут быть представлены как решетчатые графы.
-
Дополнительные ресурсы
- В статье упоминаются другие связанные понятия, такие как решетчатый путь и теорема Пика.
- Упоминаются целочисленные треугольники в двумерной решетке и обычный график.
Полный текст статьи: