Геометрическая теория графов

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

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

Внешние ссылки

СМИ, связанные с геометрической теорией графов, на Викискладе?