Введение

Граф, представляющий грани другого графа. В математической дисциплине теории графов двойной граф планарного графа G — это граф, имеющий вершину для каждой грани G. Двойной граф имеет ребро для каждой пары граней в G, которые разделены ребром, и петлю, если одна и та же грань находится по обе стороны от ребра. Таким образом, каждое ребро e графа G имеет соответствующее двойное ребро, конечными вершинами которого являются двойные вершины, соответствующие граням по обе стороны от e. Определение двойственного зависит от выбора вложения графа G, поэтому это свойство плоских графов (графов, которые уже вложены в плоскость), а не планарных графов (графов, которые могут быть вложены, но для которых вложение еще не известно). Для планарных графов в целом может существовать несколько двойных графов, в зависимости от выбора планарного вложения графа. Исторически первой формой двойственности графов было сопоставление платоновых тел в пары двойственных многогранников. Двойственность графов — это топологическое обобщение геометрических понятий двойственных многогранников и двойственных тесселяций, которое, в свою очередь, комбинаторно обобщается понятием двойного матроида. Вариации двойственности планарных графов включают версию двойственности для ориентированных графов и двойственность для графов, вложенных в непланарные двумерные поверхности. Эти понятия двойных графов не следует путать с другим понятием — двойственным графом «ребро-вершина» или линейным графом графа. Термин «двойственный» используется, поскольку свойство быть двойственным графом симметрично, то есть если H является двойственным связного графа G, то G является двойственным H. При обсуждении двойственности графа G сам граф G может называться «исходным графом». Многие другие свойства и структуры графа могут быть перенесены в другие естественные свойства и структуры двойственного графа. Например, циклы двойственны разрезам, остовные деревья двойственны дополнениям остовных деревьев, а простые графы (без параллельных ребер или петель) двойственны 3-реберно связным графам. Двойственность графов может помочь объяснить структуру лабиринтов и бассейнов водосбора. Двойные графы также применяются в компьютерном зрении, вычислительной геометрии, генерации сеток и проектировании интегральных схем.

Циклы и диполи

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

Двойные полиэдры

Согласно теореме Штайница, любой многогранный граф (граф, образованный вершинами и ребрами трехмерного выпуклого многогранника) должен быть планарным и 3-связным, и любой 3-связный планарный граф может быть получен из выпуклого многогранника таким образом. Каждый трехмерный выпуклый многогранник имеет двойственный многогранник; двойственный многогранник имеет вершину для каждой грани исходного многогранника, при этом две вершины двойственного многогранника смежны, когда соответствующие две грани имеют общее ребро. Если два многогранника двойственны, то их графы также двойственны. Например, платоновы тела образуют двойственные пары: октаэдр двойственен кубу, додекаэдр двойственен икосаэдру, а тетраэдр двойственен самому себе. Двойственность многогранников также может быть расширена на двойственность многомерных политопов, однако это расширение геометрической двойственности не имеет очевидных связей с двойственностью в теории графов.

Графики с самодуальными

Говорят, что плоский граф является самодвойственным, если он изоморфен своему двойственному графу. Колесные графы образуют бесконечное семейство самодвойственных графов, происходящих из самодвойственных многогранников (пирамид). Из формулы Эйлера следует, что каждый самодвойственный граф с n вершинами имеет ровно 2n − 2 ребер. Каждый простой самодвойственный планарный граф содержит как минимум четыре вершины степени три, и каждое самодвойственное вложение имеет как минимум четыре треугольных грани.

Свойства

Многие естественные и важные понятия в теории графов находят соответствие другим, столь же естественным, но различным понятиям в двойственном графе. Поскольку двойственный граф двойственного графа связного планарного графа изоморфен исходному графу, каждое из этих соответствий является взаимным: если понятие X в планарном графе соответствует понятию Y в двойственном графе, то понятие Y в планарном графе соответствует понятию X в двойственном графе.

Простые графики против мультиграфиков

Двойственный граф простого графа не обязательно является простым: он может содержать петли (ребро, оба конца которого находятся в одной и той же вершине) или множественные ребра, соединяющие одни и те же две вершины, как уже было видно на примере дипольных мультиграфов, двойственных циклическим графам. Как частный случай двойственности разрезов и циклов, обсуждаемой ниже, мосты плоского графа G находятся во взаимно однозначном соответствии с петлями двойственного графа. По той же причине пара параллельных ребер в двойственном мультиграфе (то есть цикл длины 2) соответствует 2-краевому разрезу в исходном графе (паре ребер, удаление которых разъединяет граф). Следовательно, плоский граф является простым тогда и только тогда, когда его двойственный граф не имеет 1- или 2-краевых разрезов; то есть, если он 3-краесвязен. Простые плоские графы, двойственные графы которых также просты, являются точно 3-краесвязными простыми плоскими графами. Этот класс графов включает, но не совпадает с классом 3-вершинно-связных простых плоских графов. Например, граф, изображенный на рисунке и являющийся самодвойственным, 3-краесвязен (и, следовательно, его двойственный граф прост), но не 3-вершинно-связен.

Уникальность

Поскольку двойной граф зависит от конкретного встраивания, двойной граф плоского графа не является уникальным, в том смысле, что один и тот же плоский граф может иметь неизоморфные двойные графы. На рисунке синие графы изоморфны, но их двойные красные графы – нет. Верхний красный двойной граф имеет вершину степени 6 (соответствующую внешней грани синего графа), в то время как в нижнем красном графе все степени меньше 6. Хаслер Уитни показал, что если граф 3-связен, то встраивание, и, следовательно, двойной граф, является уникальным. Согласно теореме Штайница, эти графы являются точно полиэдральными графами, графами выпуклых многогранников. Плоский граф 3-вершинно-связен тогда и только тогда, когда его двойной граф 3-вершинно-связен. В более общем случае, плоский граф имеет уникальное встраивание, и, следовательно, также уникальный двойной граф, если и только если он является подразбиением 3-вершинно-связного плоского графа (граф, образованный из 3-вершинно-связного плоского графа заменой некоторых его ребер путями). Для некоторых плоских графов, которые не являются 3-вершинно-связными, например, для полного двудольного графа K2,4, встраивание не является уникальным, но все встраивания изоморфны. В этом случае, соответственно, все двойные графы также изоморфны. Поскольку различные встраивания могут приводить к различным двойным графам, проверка того, является ли один граф двойным к другому (не зная их встраиваний), представляет собой нетривиальную алгоритмическую задачу. Для бисвязных графов она может быть решена за полиномиальное время с использованием SPQR-деревьев графов для построения канонической формы для отношения эквивалентности наличия общего взаимного двойственного графа. Например, два красных графа на иллюстрации эквивалентны в соответствии с этим отношением. Однако для плоских графов, которые не являются бисвязными, это отношение не является отношением эквивалентности, и задача проверки взаимной двойственности является NP-полной.

Разрез и циклы

Срез в произвольном связном графе — это подмножество ребер, определяемое разбиением множества вершин на два подмножества, путем включения ребра в подмножество, если оно имеет по одной конечной точке с каждой стороны разбиения. Удаление ребер среза обязательно разделяет граф как минимум на две связные компоненты. Минимальный срез (также называемый связью) — это срез, для которого любое собственное подмножество не является срезом. Минимальный срез связного графа обязательно разделяет граф ровно на две компоненты и состоит из множества ребер, имеющих по одной конечной точке в каждой компоненте. Простой цикл — это связный подграф, в котором каждая вершина цикла инцидентна ровно двум ребрам цикла. В связном планарном графе G каждый простой цикл G соответствует минимальному срезу в дуальном графе G, и наоборот. Это можно рассматривать как форму теоремы Жордана о кривых: каждый простой цикл разделяет грани G на грани внутри цикла и грани снаружи цикла, а дуальные ребра цикла — это именно те ребра, которые переходят от внутренней области к внешней. Длина окружности любого планарного графа (размер его наименьшего цикла) равна краевой связности его дуального графа (размер его наименьшего среза). В ориентированных планарных графах простые ориентированные циклы двойственны ориентированным разрезам (разбиениям множества вершин на два подмножества, таким образом, что все ребра направлены в одном направлении, от одного подмножества к другому). Сильно ориентированные планарные графы (графы, в которых лежащий в основе неориентированный граф связен, и в которых каждое ребро принадлежит циклу) двойственны ориентированным ациклическим графам, в которых ни одно ребро не принадлежит циклу. Иными словами, сильные ориентации связного планарного графа (назначения направлений ребрам графа, приводящие к сильно связному графу) двойственны ациклическим ориентациям (назначениям направлений, приводящим к ориентированному ациклическому графу). Аналогично, дизъюнкты (множества ребер, включающие ребро из каждого ориентированного разреза) двойственны множествам ребер обратной связи (множествам ребер, включающим ребро из каждого цикла).

Дополнительные свойства

Любая формула подсчета, включающая вершины и грани, которая справедлива для всех планарных графов, может быть преобразована посредством планарного двойствования в эквивалентную формулу, в которой роли вершин и граней поменяны местами. Формула Эйлера, являющаяся самодвойственной, служит одним из примеров. Другой пример, предложенный Харари, основан на лемме о рукопожатиях, согласно которой сумма степеней вершин любого графа равна удвоенному числу ребер. В двойственной форме эта лемма утверждает, что в планарном графе сумма числа сторон граней графа равна удвоенному числу ребер. Медиальный граф планарного графа изоморфен медиальному графу его двойственного графа. Два планарных графа могут иметь изоморфные медиальные графы только в том случае, если они являются двойственными друг другу. Планарный граф с четырьмя или более вершинами является максимальным (то есть, нельзя добавить больше ребер, сохраняя планарность) тогда и только тогда, когда его двойственный граф является 3-связным и 3-регулярным. Связный планарный граф является эйлеровым (имеет четную степень в каждой вершине) тогда и только тогда, когда его двойственный граф является двудольным. Если планарный граф G имеет полином Тютте TG(x, y), то полином Тютте его двойственного графа получается заменой x и y. По этой причине, если конкретное значение полинома Тютте предоставляет информацию об определенных типах структур в G, то замена аргументов в полиноме Тютте даст соответствующую информацию о двойственных структурах. Например, число сильных ориентаций равно TG(0, 2), а число ациклических ориентаций — TG(2, 0). Для мостовых планарных графов раскраски графа с k цветами соответствуют потокам без нулей по модулю k на двойственном графе. Например, теорему о четырех красках (существование 4-раскраски для каждого планарного графа) можно эквивалентно сформулировать как утверждение о том, что двойственный граф любого мостового планарного графа имеет поток без нулей с пропускной способностью 4. Число k-раскрасок подсчитывается (с точностью до легко вычисляемого множителя) значением полинома Тютте TG(1 − k, 0), а двойственно число потоков без нулей с пропускной способностью k подсчитывается значением TG(0, 1 − k). st-Планарный граф — это связный планарный граф вместе с биполярной ориентацией этого графа, ориентацией, которая делает его ациклическим с единственным источником и единственным стоком, оба из которых должны находиться на одной и той же грани. Такой граф можно сделать сильно связным, добавив еще одно ребро, от стока обратно к источнику, через внешнюю грань. Двойственный граф этого расширенного планарного графа сам по себе является расширением другого st-планарного графа. Строго говоря, эта конструкция не является двойственностью ориентированных планарных графов, поскольку, начиная с графа G и применяя двойствование дважды, мы не возвращаемся к самому G, а вместо этого получаем граф, изоморфный транспонированному графу G, то есть графу, полученному из G путем обращения направления всех его ребер. Применение двойствования четыре раза возвращает к исходному графу.

Слабый двойной

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

Бесконечные графики и тесселяции

Понятие дуальности применимо как к бесконечным графам, вложенным в плоскость, так и к конечным графам. Однако необходимо соблюдать осторожность, чтобы избежать топологических осложнений, таких как точки плоскости, которые не являются частью открытой области, отделенной от графа, и не являются частью ребра или вершины графа. Когда все грани являются ограниченными областями, окруженными циклом графа, вложение бесконечного планарного графа также можно рассматривать как мозаику плоскости, покрытие плоскости замкнутыми дисками (плитками мозаики), внутренности которых (грани вложения) являются непересекающимися открытыми дисками. Планарная дуальность порождает понятие двойной мозаики, мозаики, образованной путем размещения вершины в центре каждой плитки и соединения центров соседних плиток. Понятие двойной мозаики также может применяться к разбиениям плоскости на конечное число областей. В этом случае оно тесно связано с, но не идентично дуальности планарных графов. Например, диаграмма Вороного конечного набора точек представляет собой разбиение плоскости на полигоны, внутри которых одна точка ближе, чем любая другая. Точки на выпуклой оболочке входных данных порождают неограниченные полигоны Вороного, две стороны которых являются бесконечными лучами, а не конечными отрезками. Двойственным к этой диаграмме является триангуляция Делоне входных данных, планарный граф, который соединяет две точки ребром, если существует окружность, содержащая эти две точки и никакие другие. Ребра выпуклой оболочки входных данных также являются ребрами триангуляции Делоне, но они соответствуют лучам, а не отрезкам линии диаграммы Вороного. Эту двойственность между диаграммами Вороного и триангуляциями Делоне можно преобразовать в двойственность между конечными графами двумя способами: путем добавления искусственной вершины в бесконечность к диаграмме Вороного, чтобы служить другой конечной точкой для всех ее лучей, или путем рассмотрения ограниченной части диаграммы Вороного как слабой двойственности триангуляции Делоне. Хотя диаграмма Вороного и триангуляция Делоне являются двойственными, их вложение в плоскость может иметь дополнительные пересечения, помимо пересечений двойственных пар ребер. Каждая вершина триангуляции Делоне расположена внутри соответствующей ей грани диаграммы Вороного. Каждая вершина диаграммы Вороного расположена в центре описанной окружности соответствующего треугольника триангуляции Делоне, но эта точка может находиться за пределами этого треугольника.

Неплоские вставки

Концепция двойственности может быть расширена на вложения графов на двумерных многообразиях, отличных от плоскости. Определение остаётся прежним: для каждого связного компонента дополнения графа на многообразии существует двойная вершина, а для каждого ребра графа, соединяющего две двойные вершины по обе стороны от этого ребра, существует двойное ребро. В большинстве применений этой концепции она ограничивается вложениями, обладающими свойством, что каждая грань является топологическим диском; это ограничение обобщает требование связности для плоских графов. При этом ограничении двойственный граф любого графа, вложенного на поверхность, имеет естественное вложение на ту же поверхность, такое что двойственный граф двойственного графа изоморфен исходному графу и изоморфно вложен в него. Например, полный граф K7 является тороидальным графом: он не планарный, но может быть вложен в тор, причём каждая грань вложения является треугольником. Вложение этого графа имеет граф Хивуда в качестве двойственного графа. Та же концепция одинаково хорошо применима и к неориентируемым поверхностям. Например, K6 может быть вложен в проективную плоскость с десятью треугольными гранями в виде геми-икосаэдра, двойственным графом которого является граф Петерсена, вложенный в виде геми-додекаэдра. Даже планарные графы могут иметь непланарные вложения, и двойственные графы, полученные из этих вложений, отличаются от их планарных двойственных графов. Например, четыре многоугольника Петри куба (шестиугольники, образованные удалением двух противоположных вершин куба) образуют гексагональные грани вложения куба в тор. Двойственный граф этого вложения имеет четыре вершины, образующие полный граф K4 с удвоенными ребрами. Во вложении тора этого двойственного графа шесть рёбер, инцидентных каждой вершине, в циклическом порядке вокруг этой вершины, дважды проходят через три другие вершины. В отличие от ситуации на плоскости, это вложение куба и его двойственного графа не является единственным; граф куба имеет несколько других вложений в тор с различными двойственными графами. Двойственность поверхности и двойственность Петри — две из шести операций Уилсона, и вместе они порождают группу этих операций.

Матроиды и алгебраические дуалы

Алгебраический дуал связного графа G – это граф G^(*), такой, что G и G^(*) имеют один и тот же набор ребер, любой цикл в G является разрезом в G^(*), и любой разрез в G является циклом в G^(*). Каждый планарный граф имеет алгебраический дуал, который, как правило, не является единственным (любой дуал, определенный плоским вложением, подойдет). Обратное также верно, как установил Хасслер Уитни в критерии планарности Уитни: связный граф G планарен тогда и только тогда, когда он имеет алгебраический дуал. Тот же факт можно выразить в теории матроидов. Если M – графический матроид графа G, то граф G^(*) является алгебраическим дуалом G, если и только если графический матроид G^(*) является двойным матроидом к M. Тогда критерий планарности Уитни можно перефразировать следующим образом: двойной матроид графического матроида M сам является графическим матроидом тогда и только тогда, когда исходный граф G, соответствующий M, планарен. Если G планарен, то двойной матроид является графическим матроидом двойственного графа G. В частности, все двойственные графы, для всех различных планарных вложений G, имеют изоморфные графические матроиды. Для непланарных поверхностных вложений, в отличие от планарных дуалов, двойственный граф обычно не является алгебраическим дуалом исходного графа. И для непланарного графа G, двойной матроид графического матроида G сам по себе не является графическим матроидом. Однако это все еще матроид, чьи циклы соответствуют разрезам в G, и в этом смысле его можно рассматривать как комбинаторно обобщенный алгебраический дуал G.

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

Приложения

Наряду с применением в теории графов, двойственность планарных графов находит применение в нескольких других областях математических и вычислительных исследований. В географических информационных системах сети потоков (например, сети, показывающие направление течения воды в системе ручьев и рек) двойственны сотовым сетям, описывающим водоразделы. Эту двойственность можно объяснить моделированием сети потоков как остовного дерева на решетчатом графе подходящего масштаба, а водораздела – как дополнительного остовного дерева хребтов на двойственном решетчатом графе. В компьютерном зрении цифровые изображения разбиваются на небольшие квадратные пиксели, каждый из которых имеет свой цвет. Двойственный граф этого разбиения на квадраты имеет вершину для каждого пикселя и ребро между парами пикселей, имеющих общую границу; он полезен для задач, включая кластеризацию пикселей в связанные области схожих цветов. В вычислительной геометрии двойственность между диаграммами Вороного и триангуляциями Делоне подразумевает, что любой алгоритм построения диаграммы Вороного можно непосредственно преобразовать в алгоритм для триангуляции Делоне, и наоборот. Та же двойственность также может быть использована при генерации сеток конечных элементов. Алгоритм Ллойда, метод, основанный на диаграммах Вороного для перемещения набора точек на поверхности в более равномерно распределенные положения, обычно используется для сглаживания сетки конечных элементов, описываемой двойственной триангуляцией Делоне. Этот метод улучшает сетку, делая ее треугольники более однородными по размеру и форме. При синтезе CMOS-схем синтезируемая функция представляется в виде формулы булевой алгебры. Затем эта формула преобразуется в два последовательно-параллельных мультиграфа. Эти графы можно интерпретировать как схемы, в которых ребра графов представляют транзисторы, управляемые входами функции. Одна схема вычисляет саму функцию, а другая – ее дополнение. Одна из двух схем получается путем преобразования конъюнкций и дизъюнкций формулы в последовательные и параллельные композиции графов соответственно. Другая схема выполняет обратное преобразование, преобразуя конъюнкции и дизъюнкции формулы в параллельные и последовательные композиции графов. Эти две схемы, дополненные дополнительным ребром, соединяющим вход каждой схемы с ее выходом, являются планарными двойственными графами.

История

Двойственность выпуклых многогранников была отмечена Иоганном Кеплером в его книге 1619 года «Harmonices Mundi». Распознаваемые плоские двойные графы, вне связи с многогранниками, появились еще в 1725 году в посмертно опубликованной работе Пьера Вариньона «Nouvelle Méchanique ou Statique». Это произошло даже раньше работы Леонарда Эйлера 1736 года о семи мостах Кёнигсберга, которую часто рассматривают как первую работу по теории графов. Вариньон анализировал силы, действующие на статические системы распорок, строя граф, двойственный распоркам, с длинами ребер, пропорциональными силам, действующим на распорки; этот двойственный граф является разновидностью диаграммы Кремоны. В связи с теоремой о четырех красках двойные графы карт (разбиения плоскости на области) были упомянуты Альфредом Кемпе в 1879 году и расширены на карты на непланарных поверхностях к 1891 году. Дуальность как операция над абстрактными планарными графами была введена Хасслером Уитни в 1931 году.