Теория геометрических графов - Geometric graph theory

Сетевая наука
Internet_map_1024.jpg
Типы сетей
Графики
Функции
Типы
Модели
Топология
Динамика
  • Списки
  • Категории
  • Категория: Теория сетей
  • Категория: Теория графов

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

Различные типы геометрических графиков

А планарный прямой график - граф, вершины которого вложены как точки в Евклидова плоскость, а рёбра вложены непересекающимися отрезки линии. Теорема Фари заявляет, что любой планарный граф может быть представлен в виде плоского прямолинейного графика. А триангуляция является плоским графом с прямыми линиями, к которому нельзя добавлять больше ребер, так называемый потому, что каждая грань обязательно является треугольником; частным случаем этого является Триангуляция Делоне, граф, определяемый из набора точек на плоскости путем соединения двух точек ребром, если существует круг, содержащий только эти две точки.

1-скелет из многогранник или многогранник - множество вершин и ребер многогранника. Каркас любого выпуклого многогранника является плоским графом, а каркас любого k-мерный выпуклый многогранник является k-связный граф. Наоборот, Теорема Стейница утверждает, что любой 3-связный плоский граф является каркасом выпуклого многогранника; по этой причине этот класс графов также известен как многогранные графы.

А Евклидов граф - граф, в котором вершины представляют точки на плоскости, а ребрам назначаются длины, равные евклидову расстоянию между этими точками. В Евклидово минимальное остовное дерево это минимальное остовное дерево евклидова полный график. Также возможно определять графики по условиям на расстояниях; в частности, график единичного расстояния образуется путем соединения пар точек, находящихся на единичном расстоянии друг от друга в плоскости. В Проблема Хадвигера – Нельсона касается хроматическое число этих графиков.

An граф пересечений представляет собой граф, в котором каждая вершина связана с набором и в котором вершины соединены ребрами, если соответствующие множества имеют непустое пересечение. Когда наборы представляют собой геометрические объекты, результатом является геометрический график. Например, график пересечений отрезков линий в одном измерении представляет собой интервальный график; граф пересечения единичных дисков на плоскости - это граф единичного диска. В Теорема об упаковке круга утверждает, что графы пересечений непересекающихся окружностей - это в точности плоские графы. Гипотеза Шайнермана (доказано в 2009 году) утверждает, что любой планарный граф может быть представлен как граф пересечений отрезков прямой на плоскости.

А Граф Леви семейства точек и прямых имеет вершину для каждого из этих объектов и ребро для каждой пары инцидентных точек и линий. Графы Леви проективные конфигурации привести ко многим важным симметричные графы и клетки.

В график видимости замкнутого многоугольника соединяет каждую пару вершин ребром, если отрезок прямой, соединяющий вершины, полностью лежит в многоугольнике. Неизвестно, как эффективно проверить, может ли неориентированный граф быть представлен как граф видимости.

А частичный куб - граф, вершины которого можно сопоставить с вершинами гиперкуб, таким образом, что расстояние на графике равно Расстояние Хэмминга между соответствующими вершинами гиперкуба. Многие важные семейства комбинаторных структур, такие как ациклические ориентации графа или смежности между областями в расположение гиперплоскости, можно представить в виде частичных кубических графов. Важным частным случаем частичного куба является скелет пермутоэдр, граф, в котором вершины представляют собой перестановки набора упорядоченных объектов, а ребра представляют собой перестановки объектов, соседних по порядку. Несколько других важных классов графов, включая медианные графики имеют связанные определения, включающие метрические вложения (Bandelt & Chepoi, 2008).

А перевернуть график представляет собой граф, сформированный из триангуляций набора точек, в котором каждая вершина представляет собой триангуляцию, а две триангуляции соединены ребром, если они отличаются заменой одного ребра другим. Также возможно определить связанные флип-графы для разбиений на четырехугольники или псевдотреугольники, а также для многомерных триангуляций. Флип-граф триангуляций выпуклого многоугольника образует остов ассоциэдр или Многогранник Сташева. Обратный график регулярные триангуляции точечного множества (проекции выпуклых оболочек более высокой размерности) также можно представить в виде каркаса так называемого вторичный многогранник.

Смотрите также

Рекомендации

  • Бандельт, Ханс-Юрген; Чепой, Виктор (2008). «Метрическая теория графов и геометрия: обзор» (PDF). Обзоры по дискретной и вычислительной геометрии - двадцать лет спустя. Современная математика. 453. Американское математическое общество. С. 49–86.
  • Пах, Янош, изд. (2004). К теории геометрических графов. Современная математика. 342. Американское математическое общество.
  • Пах, Янош (2013). «Начала геометрической теории графов». 100-летие Эрдеша. Bolyai Soc. Математика. Stud. 25. Будапешт: János Bolyai Math. Soc. С. 465–484. Дои:10.1007/978-3-642-39286-3_17. Г-Н  3203608.
  • Писанский, Томаж; Рандич, Милан (2000). «Мосты между геометрией и теорией графов». В Горини, К.А. (ред.). Геометрия в действии: статьи по прикладной геометрии. Вашингтон, округ Колумбия: Математическая ассоциация Америки. С. 174–194. Архивировано из оригинал на 2007-09-27.

внешняя ссылка