Вложение графа

Граф Хивуда и связанное с ним отображение, вложенное в тор.

В топологической теории графов , с вложением (также пишется вложения ) в виде графика на поверхности является представлением на , в котором точки связаны с вершинами и простых дуг ( гомеоморфы образы ) связаны с ребрами таким образом , что:${\ displaystyle G}$ ${\ displaystyle \ Sigma}$${\ displaystyle G}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle [0,1]}$

• конечными точками дуги, связанной с ребром, являются точки, связанные с конечными вершинами${\ displaystyle e}$${\ displaystyle e,}$
• никакие дуги не содержат точек, связанных с другими вершинами,
• две дуги никогда не пересекаются во внутренней точке любой из дуг.

Здесь поверхность представляет собой компактное , связан - многообразие .${\displaystyle 2}$

Неформально вложение графа в поверхность - это рисование графа на поверхности таким образом, что его ребра могут пересекаться только в своих конечных точках. Хорошо известно, что любой конечный граф можно вложить в 3-мерное евклидово пространство . ^[1] плоский граф является тот , который может быть встроен в 2-мерном евклидовом пространстве${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \mathbb {R} ^{2}.}$

Часто вложение рассматривается как класс эквивалентности (относительно гомеоморфизма ) представлений только что описанного типа.${\displaystyle \Sigma }$

Некоторые авторы определяют более слабую версию определения «вложения графа», опуская условие непересечения ребер. В таких контекстах более строгое определение описывается как «вложение непересекающихся графов». ^[2]

В этой статье рассматривается только строгое определение вложения графов. Более слабое определение обсуждается в статьях « Отрисовка графика » и « Число пересечений ».

Терминология [ править ]

Если граф вложен в замкнутую поверхность , дополнение к объединению точек и дуг, связанных с вершинами и ребрами, является семейством областей (или граней ). ^[3] 2-элементное вложение , клеточное вложение или отображение является вложением , в котором каждое лицо гомеоморфно открытым диск. ^[4] замкнутая 2-элементный вложение является вложением , в котором замыкание каждого лица гомеоморфно замкнутому диску.${\displaystyle G}$${\displaystyle \Sigma }$${\displaystyle G}$

Род из графа есть минимальное целое число такое , что граф может быть встроен в поверхность рода . В частности, планарный граф имеет род , потому что его можно нарисовать на сфере без самопересечения. В неориентируемом роде из в графе есть минимальное целое число такого , что граф может быть встроен в неориентируемой поверхности (неориентируемый) рода . ^[3]${\displaystyle n}$ ${\displaystyle n}$${\displaystyle 0}$${\displaystyle n}$${\displaystyle n}$

Род Эйлера графа - это минимальное целое число, такое, что граф может быть вложен в ориентируемую поверхность (ориентируемого) рода или в неориентируемую поверхность (неориентируемого) рода . Граф ориентируемо прост, если его род Эйлера меньше, чем его неориентируемый род.${\displaystyle n}$${\displaystyle n/2}$${\displaystyle n}$

Максимальный родом из графика является максимальным числом , так что график может быть -клетка встроен в ориентируемой поверхности рода .${\displaystyle n}$${\displaystyle 2}$ ${\displaystyle n}$

Комбинаторное вложение [ править ]

Вложенный граф однозначно определяет циклические порядки ребер, инцидентных одной и той же вершине. Множество всех этих циклических порядков называется системой вращения . Вложения с одной и той же системой вращения считаются эквивалентными, и соответствующий класс эквивалентности вложений называется комбинаторным вложением (в отличие от термина топологическое вложение , которое относится к предыдущему определению в терминах точек и кривых). Иногда саму систему вращения называют «комбинаторным вложением». ^{[5] [6] [7]}

Вложенный граф также определяет естественные циклические порядки ребер, которые составляют границы граней вложения. Однако обработка этих основанных на гранях порядков менее проста, поскольку в некоторых случаях некоторые ребра могут проходить дважды вдоль границы грани. Например, это всегда верно для вложений деревьев, которые имеют одну грань. Чтобы преодолеть это комбинаторное неудобство, можно считать, что каждое ребро «разбито» по длине на два «полуребра» или «стороны». Согласно этому соглашению при всех обходах границы грани каждая половина кромки проходит только один раз, а две половины кромки одной кромки всегда проходят в противоположных направлениях.

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

Вычислительная сложность [ править ]

Задача нахождения рода графа является NP-сложной (задача определения родов -вершинного графа является NP-полной ). ^[8]${\displaystyle n}$${\displaystyle g}$

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

Первый прорыв в этом отношении произошел в 1979 году, когда алгоритмы временной сложности O ( n ^{O ( g )} ) были независимо представлены на ежегодном симпозиуме ACM по теории вычислений : один И. Филотти и Г.Л. Миллер, а другой - Джоном Рейфом. . Их подходы были совершенно разными, но по предложению программного комитета они представили совместный доклад. ^[9] Однако Венди Мирволд и Уильям Кодай доказали в 2011 году, что алгоритм, предложенный Филотти, Миллером и Рейфом, неверен. ^[10]

В 1999 году сообщалось, что случай фиксированного рода может быть решен во времени линейно по размеру графа и дважды экспоненциально по роду. ^[11]

Вложения графов в многомерные пространства [ править ]

Известно, что любой конечный граф можно вложить в трехмерное пространство. ^[1]

Один из способов сделать это - разместить точки на любой линии в пространстве и нарисовать края в виде кривых, каждая из которых лежит в отдельной полуплоскости , причем все полуплоскости имеют эту линию в качестве общей границы. Подобное вложение, в котором ребра нарисованы на полуплоскостях, называется книжным вложением графа. Эта метафора возникает из представления, что каждая плоскость, на которой нарисован край, подобна странице книги. Было замечено, что на самом деле на одной «странице» может быть нарисовано несколько краев; книга толщина графа минимальное количество полуплоскость , необходимых для такого рисунка.

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

Вложение графа в трехмерное пространство, в котором никакие два цикла не связаны топологически, называется вложением без звеньев . Граф имеет вложение без связей тогда и только тогда, когда он не имеет одного из семи графов семейства Петерсенов в качестве младшего .

См. Также [ править ]

• Встраивание , для других видов вложений
• Толщина книги
• Толщина графика
• Список двусвязных ребер , структура данных для представления графа, встраиваемого в плоскость.
• Регулярная карта (теория графов)
• Теорема Фари , которая гласит, что прямолинейное планарное вложение плоского графа всегда возможно.
• Триангуляция (геометрия)

Ссылки [ править ]