В топологической теории графов , вложение (также пишется вложения ) из графа на поверхности представляет собой представление на в каких точках связаны с вершинами и простыми дугами ( гомеоморфными образами) связаны с ребрами таким образом, что:
- конечные точки дуги, связанные с ребром - точки, связанные с концевыми вершинами
- никакие дуги не содержат точек, связанных с другими вершинами,
- две дуги никогда не пересекаются во внутренней точке любой из дуг.
Здесь поверхность представляет собой компактный , подключен - коллектор .
Неформально вложение графа в поверхность - это рисование графа на поверхности таким образом, что его ребра могут пересекаться только в своих конечных точках. Хорошо известно, что любой конечный граф можно вложить в 3-мерное евклидово пространство.. [1] плоский граф является тот , который может быть встроен в 2-мерном евклидовом пространстве
Часто вложение рассматривается как класс эквивалентности (при гомеоморфизмах) представлений только что описанного типа.
Некоторые авторы определяют более слабую версию определения «вложения графа», опуская условие непересечения ребер. В таких контекстах более строгое определение описывается как «вложение непересекающихся графов». [2]
В этой статье рассматривается только строгое определение вложения графов. Более слабое определение обсуждается в статьях « Отрисовка графика » и « Число пересечений ».
Терминология
Если график вложен в замкнутую поверхность , дополнение к объединению точек и дуг, связанных с вершинами и ребрами семейство регионов (или граней ). [3] 2-элементное вложение , клеточное вложение или отображение является вложением , в котором каждое лицо гомеоморфно открытым диск. [4] замкнутая 2-элементный вложение является вложением , в котором замыкание каждого лица гомеоморфно замкнутому диску.
Родом из графа есть минимальное целое числотакой, что граф можно вложить в поверхность рода . В частности, планарный граф имеет род, потому что его можно нарисовать на сфере без самопересечения. Неориентируемо родом из графа есть минимальное целое число такая, что граф может быть вложен в неориентируемую поверхность (неориентируемой) рода . [3]
Род Эйлера графа - это минимальное целое число такой, что граф может быть вложен в ориентируемую поверхность (ориентируемого) рода или в неориентируемой поверхности (неориентируемой) рода . Граф ориентируемо прост, если его род Эйлера меньше, чем его неориентируемый род.
Максимальный родом из графика является максимальным числом такой, что граф может быть -клетка, вложенная в ориентируемую поверхность рода .
Комбинаторное вложение
Вложенный граф однозначно определяет циклические порядки ребер, инцидентных одной и той же вершине. Множество всех этих циклических порядков называется системой вращения . Вложения с одной и той же системой вращения считаются эквивалентными, и соответствующий класс эквивалентности вложений называется комбинаторным вложением (в отличие от термина топологическое вложение , которое относится к предыдущему определению в терминах точек и кривых). Иногда саму систему вращения называют «комбинаторным вложением». [5] [6] [7]
Вложенный граф также определяет естественные циклические порядки ребер, которые составляют границы граней вложения. Однако обработка этих основанных на гранях порядков менее проста, поскольку в некоторых случаях некоторые ребра могут проходить дважды вдоль границы грани. Например, это всегда верно для вложений деревьев, которые имеют одну грань. Чтобы преодолеть эту комбинаторную неприятность, можно считать, что каждое ребро «разбито» по длине на два «полуребра» или «стороны». Согласно этому соглашению при всех обходах границы грани каждая половина кромки проходит только один раз, а две половины кромки одной и той же кромки всегда проходят в противоположных направлениях.
Другие эквивалентные представления для клеточных вложений включают ленточный граф , топологическое пространство, образованное путем склеивания топологических дисков для вершин и ребер вложенного графа, и карту с кодировкой графа, кубический граф цвета ребер с четырьмя вершинами для каждого ребра графа. встроенный граф.
Вычислительная сложность
Задача нахождения рода графа является NP-трудной (проблема определения того, является ли-вершинный граф имеет род является NP-полным ). [8]
В то же время проблема рода графов является решаемой с фиксированными параметрами , т. Е. Известны алгоритмы с полиномиальным временем , позволяющие проверить, можно ли вложить граф в поверхность заданного фиксированного рода, а также найти вложение.
Первый прорыв в этом отношении произошел в 1979 году, когда алгоритмы временной сложности O ( n O ( g ) ) были независимо представлены на ежегодном симпозиуме ACM по теории вычислений : один И. Филотти и Г.Л. Миллер, а другой - Джоном Рейфом. . Их подходы были совершенно разными, но по предложению программного комитета они представили совместный доклад. [9] Однако Венди Мирволд и Уильям Кодай доказали в 2011 году, что алгоритм, предложенный Филотти, Миллером и Рейфом, неверен. [10]
В 1999 году сообщалось, что случай фиксированного рода может быть решен во времени линейно по размеру графа и дважды экспоненциально по роду. [11]
Вложения графов в многомерные пространства
Известно, что любой конечный граф можно вложить в трехмерное пространство. [1]
Один из способов сделать это - разместить точки на любой линии в пространстве и нарисовать края в виде кривых, каждая из которых лежит в отдельной полуплоскости , причем все полуплоскости имеют эту линию в качестве общей границы. Подобное вложение, в котором ребра нарисованы на полуплоскостях, называется книжным вложением графа. Эта метафора возникает из представления, что каждая плоскость, на которой нарисован край, подобна странице книги. Было замечено, что на самом деле на одной «странице» может быть нарисовано несколько краев; книга толщина графа минимальное количество полуплоскость , необходимых для такого рисунка.
В качестве альтернативы любой конечный граф можно нарисовать с прямыми ребрами в трех измерениях без пересечений, поместив его вершины в общее положение так, чтобы никакие четыре не были компланарными. Например, этого можно достичь, поместив i- ю вершину в точку ( i , i 2 , i 3 ) кривой момента .
Вложение графа в трехмерное пространство, в котором никакие два цикла не связаны топологически, называется вложением без звеньев . Граф имеет вложение без связей тогда и только тогда, когда он не имеет одного из семи графов семейства Петерсенов в качестве младшего .
Галерея
Граф Петерсена и связанное с ним отображение, вложенное в проективную плоскость. Отождествляются противоположные точки на окружности, и получается замкнутая поверхность неориентируемого рода 1.
Граф Паппа и связанное с ним отображение, вложенное в тор.
Граф Клейна степени 7 и связанное с ним отображение, вложенные в ориентируемую поверхность рода 3.
Смотрите также
- Встраивание , для других видов вложений
- Толщина книги
- Толщина графика
- Список двусвязных ребер , структура данных для представления графа, встраиваемого в плоскость.
- Регулярная карта (теория графов)
- Теорема Фари , которая гласит, что прямолинейное планарное вложение плоского графа всегда возможно.
- Триангуляция (геометрия)
Рекомендации
- ^ a b Коэн, Роберт Ф .; Идс, Питер ; Линь, Дао; Раски, Фрэнк (1995), «Рисование трехмерного графа», Тамассия, Роберто ; Толлис, Иоаннис Г. (ред.), Рисование графиков: Международный семинар DIMACS, GD '94, Принстон, Нью-Джерси, США, 10–12 октября 1994 г., Proceedings , Lecture Notes in Computer Science , 894 , Springer, pp. 1– 11, DOI : 10.1007 / 3-540-58950-3_351 , ISBN 978-3-540-58950-1.
- ^ Като, Наоки; Танигава, Шин-ичи (2007), «Перечисление ограниченных непересекающихся геометрических остовных деревьев», Вычислительная техника и комбинаторика, 13-я ежегодная международная конференция, COCOON 2007, Банф, Канада, 16-19 июля 2007 г., Труды , Лекционные заметки по информатике , 4598 ., Springer-Verlag, стр 243-253, CiteSeerX 10.1.1.483.874 , DOI : 10.1007 / 978-3-540-73545-8_25 , ISBN 978-3-540-73544-1.
- ^ а б Гросс, Джонатан; Такер, Томас В. (2001), Теория топологических графов , Dover Publications, ISBN 978-0-486-41741-7 CS1 maint: обескураженный параметр ( ссылка ).
- ^ Ландо, Сергей К .; Звонкин, Александр К. (2004), Графы на поверхностях и их приложения , Springer-Verlag, ISBN 978-3-540-00203-1.
- ^ Муцель, Петра ; Вайскирчер, Рене (2000), «Вычисление оптимальных вложений для плоских графов», Вычисления и комбинаторика, 6-я ежегодная международная конференция, COCOON 2000, Сидней, Австралия, 26–28 июля 2000 г., Proceedings , Lecture Notes in Computer Science, 1858 , Springer -Verlag, стр 95-104,. DOI : 10.1007 / 3-540-44968-X_10 , ISBN 978-3-540-67787-1.
- ^ Диджев, Христо Н. (1995), "Рисование графа выпукло на плоскости", Graph Drawing, DIMACS International Workshop, GD '94, Принстон, Нью-Джерси, США, 10–12 октября 1994 г., Труды , Лекционные заметки в Компьютерные науки, 894 , Springer-Verlag, стр. 76–83, DOI : 10.1007 / 3-540-58950-3_358 , ISBN 978-3-540-58950-1.
- ^ Дункан, Кристиан; Гудрич, Майкл Т .; Кобуров, Стивен (2010), «Планарные рисунки графов высшего рода», Графическое изображение, 17-й Международный симпозиум, GD 2009, Чикаго, Иллинойс, США, 22-25 сентября 2009 г., Revised Papers , Lecture Notes in Computer Science, 5849 , Springer-Verlag, стр. 45–56, arXiv : 0908.1608 , doi : 10.1007 / 978-3-642-11805-0_7 , ISBN 978-3-642-11804-3.
- ^ Томасно, Карстен (1989), "Проблема графы рода NP-полная", журнал алгоритмов , 10 (4): 568-576, DOI : 10,1016 / 0196-6774 (89) 90006-0 CS1 maint: обескураженный параметр ( ссылка )
- ^ Филотти, ИС; Миллер, Гэри Л .; Рейф, Джон (1979), "Об определении рода графа за O (v O (g)) шагов (предварительный отчет)", Proc. 11-й год. Симпозиум ACM по теории вычислений , стр. 27–37, DOI : 10.1145 / 800135.804395.
- ^ Мирволд, Венди ; Коджай, Уильям (1 марта 2011 г.). «Ошибки в алгоритмах вложения графов». Журнал компьютерных и системных наук . 2 (77): 430–438. DOI : 10.1016 / j.jcss.2010.06.002 .
- ^ Мохар, Боян (1999), "Алгоритм линейного времени для вложения графов в произвольную поверхность", SIAM Journal on Discrete Mathematics , 12 (1): 6–26, CiteSeerX 10.1.1.97.9588 , doi : 10.1137 / S089548019529248X CS1 maint: обескураженный параметр ( ссылка )