Двойной график - Dual graph

Красный график - это двойной график синего графика, а наоборот.

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

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

Период, термин двойной используется, потому что свойство быть двойным графом симметричный, что означает, что если ЧАС является двойником связный граф грамм, тогда грамм является двойником ЧАС. Обсуждая двойственность графа грамм, график грамм сам по себе может называться «прямым графом». Многие другие свойства и структуры графа могут быть переведены в другие естественные свойства и структуры двойственного объекта. Например, циклы двойственны порезы, остовные деревья двойственны дополняет остовных деревьев и простых графов (без параллельные края или же петли ) двойственны 3-реберные графы.

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

Примеры

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

А дипольный график
А график цикла

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

Двойные многогранники

Основная статья: Двойной многогранник
Куб и правильный октаэдр являются двойственными графами друг друга.

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

Автодуальные графы

Автодуальный граф.

Плоский граф называется самодвойственный если это изоморфный к его дуальному графу. В колесные графики предоставить бесконечное семейство самодуальных графов, происходящих из самодвойственные многогранники (в пирамиды ).[4][5] Однако существуют также самодуальные графы, которые не являются полиэдральными, например, показанный. Серватиус и Кристофер (1992) описать две операции, адгезию и взрыв, которые можно использовать для построения самодвойственного графа, содержащего данный планарный граф; например, показанный автодуальный граф может быть построен как сцепление тетраэдра с его двойственным.[5]

Из формулы Эйлера следует, что всякий самодуальный граф с п вершин ровно 2п − 2 края.[6] Каждый простой самодуальный планарный граф содержит не менее четырех вершин степени три, а каждое самодвойственное вложение имеет не менее четырех треугольных граней.[7]

Характеристики

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

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

Двойник простого графа не обязательно должен быть простым: он может иметь петли (ребро с обеими конечными точками в одной вершине) или несколько ребер, соединяющих одни и те же две вершины, как уже было очевидно в примере дипольных мультиграфов, двойственных циклическим графам. В качестве частного случая двойственности цикла разреза, обсуждаемого ниже, мосты планарного графа грамм находятся во взаимно однозначном соответствии с петлями двойственного графа.[9] По той же причине пара параллельных ребер в двойном мультиграфе (т. Е. Цикл длины 2) соответствует 2-реберному Cutset в прямом графе (пара ребер, удаление которых разъединяет граф). Следовательно, планарный граф является простым тогда и только тогда, когда его двойственный не имеет одно- или двухреберных разрезов; то есть, если это 3-х стороннее соединение. Простые планарные графы, двойственные простые которых являются простыми, в точности являются 3-связными простыми планарными графами.[10] Этот класс графов включает, но не то же самое, что класс 3-вершинно-связанный простые плоские графы. Например, рисунок, показывающий самодвойственный граф, имеет 3-реберную связность (и, следовательно, его двойственный простой), но не 3-вершинно-связный.

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

Два красных графика двойственны синему, но это не так. изоморфный.

Поскольку двойственный граф зависит от конкретного вложения, двойственный граф планарный граф не уникален в том смысле, что один и тот же планарный граф может не иметьизоморфный двойственные графы.[11] На картинке синие графики изоморфны, а их двойственные красные графики - нет. Верхний красный двойник имеет вершину со степенью 6 (соответствует внешней грани синего графа), а в нижнем красном графе все степени меньше 6.

Хасслер Уитни показал, что если график 3-связный тогда вложение, а значит, и дуальный граф, единственны.[12] К Теорема Стейница, эти графики в точности многогранные графы, графики выпуклых многогранников. Планарный граф является 3-вершинно-связным тогда и только тогда, когда его дуальный граф 3-вершинно-связный. В более общем смысле, планарный граф имеет уникальное вложение, а значит, и уникальный двойственный, если и только если он является подразделение 3-вершинно-связного плоского графа (граф, образованный из 3-вершинно-связного плоского графа путем замены некоторых его ребер путями). Для некоторых плоских графов, не связанных с 3 вершинами, таких как полный двудольный граф K2,4, вложение не единственное, но все вложения изоморфны. При этом, соответственно, все дуальные графы изоморфны.

Поскольку разные вложения могут привести к разным двойственным графам, проверка того, является ли один граф двойственным другому (без предварительного знания их вложений), является нетривиальной задачей. алгоритмический проблема. За двусвязные графы, ее можно решить за полиномиальное время с помощью Деревья SPQR графиков для построения каноническая форма для отношение эквивалентности наличия общего взаимного дуала. Например, два красных графика на иллюстрации эквивалентны в соответствии с этим соотношением. Однако для плоских графов, которые не являются двусвязными, это отношение не является отношением эквивалентности, и проблема проверки взаимной двойственности заключается в НП-полный.[13]

Порезы и циклы

А Cutset в произвольном связном графе - это подмножество ребер, определяемое разбиением вершин на два подмножества, путем включения ребра в подмножество, когда оно имеет по одной конечной точке с каждой стороны разбиения. Удаление ребер сечения обязательно разбивает граф как минимум на две связанные компоненты. Минимальное сечение (также называемое связью) - это сечение, обладающее тем свойством, что каждое собственное подмножество сечения само по себе не является разрезом. Минимальное сечение связного графа обязательно разделяет его граф ровно на два компонента и состоит из множества ребер, которые имеют по одной конечной точке в каждом компоненте.[14] А простой цикл это связанный подграф в котором каждая вершина цикла инцидентна ровно двум ребрам цикла.[15]

В связном плоском графе грамм, каждый простой цикл грамм соответствует минимальному сечению в двойственном к грамм, наоборот.[16] Это можно рассматривать как форму Теорема Жордана: каждый простой цикл разделяет грани грамм на грани внутри цикла и грани на внешней стороне цикла, а двойственные ребра цикла - это в точности ребра, которые пересекаются изнутри во внешнюю.[17] В обхват любого плоского графа (размер его наименьшего цикла) равен граничное соединение двойственного графа (размер его наименьшего сечения).[18]

Эта двойственность распространяется от отдельных разрезов и циклов до векторные пространства определяется из них. В велосипедное пространство графа определяется как семейство всех подграфов, которые имеют даже степень в каждой вершине; это можно рассматривать как векторное пространство над двухэлементное конечное поле, с симметричная разница двух наборов ребер, действующих как операция сложения векторов в векторном пространстве. Точно так же вырезать пространство графа определяется как семейство всех сечений с векторным сложением, определенным таким же образом. Тогда пространство циклов любого плоского графа и пространство разрезов его двойственного графа изоморфны как векторные пространства.[19] Таким образом классифицировать планарного графа ( измерение пространства разреза) равно циклотомическое число его двойственного (размерность его пространства цикла) и наоборот.[11] А основа цикла графа - это набор простых циклов, образующих основа пространства циклов (каждый подграф четной степени может быть образован ровно одним способом как симметричная разность некоторых из этих циклов). За взвешенный по краям плоских графах (с достаточно общими весами, чтобы не было двух циклов с одинаковым весом), базис цикла минимального веса графа двойственен Дерево Гомори – Ху двойного графа, набор вложенных разрезов, которые вместе включают минимальный разрез разделяя каждую пару вершин в графе. Каждый цикл в базисе цикла минимального веса имеет набор ребер, двойственных ребрам одного из разрезов в дереве Гомори – Ху. Когда веса цикла могут быть связаны, базис цикла минимального веса может быть не уникальным, но в этом случае все еще верно, что дерево Гомори – Ху дуального графа соответствует одному из базисов цикла минимального веса графа.[19]

В ориентированных планарных графах простые ориентированные циклы двойственны направленным разрезам (разбиения вершин на два подмножества, так что все ребра идут в одном направлении, от одного подмножества к другому). Сильно ориентированные плоские графы (графы, основной неориентированный граф которых связан и в которых каждое ребро принадлежит циклу) двойственны ориентированные ациклические графы в котором ни одно ребро не принадлежит циклу. Другими словами, сильные ориентации связного плоского графа (назначения направлений ребрам графа, которые приводят к сильно связный граф ) двойственны ациклические ориентации (присвоение направлений, которые производят ориентированный ациклический граф ).[20]

Остовные деревья

Простой лабиринт, в котором стены лабиринта и свободное пространство между стенами образуют два пересекающихся дерева.

А остовное дерево можно определить как набор ребер, которые вместе со всеми вершинами графа образуют связный ациклический подграф. Но в силу двойственности цикла отсечений, если множество S ребер в плоском графе грамм ациклично (не имеет циклов), то множество ребер, двойственных к S не имеет разрезов, из чего следует, что дополнительный набор двойственных ребер (двойников ребер, не лежащих в S) образует связный подграф. Симметрично, если S связно, то дуальные ребра дополнению к S образуют ациклический подграф. Следовательно, когда S имеет оба свойства - связность и ацикличность - то же самое верно и для дополнительного множества в дуальном графе. То есть каждое остовное дерево грамм является дополнительным к остовному дереву двойственного графа, и наоборот. Таким образом, ребра любого плоского графа и его двойственного могут быть вместе (несколькими разными способами) разделены на два остовных дерева, одно в прямом и одно в двойственном, которые вместе простираются на все вершины и грани графа, но никогда скрестить друг друга. В частности, минимальное остовное дерево из грамм является дополнительным к максимальному остовному дереву двойственного графа.[21] Однако это не работает для деревья кратчайшего пути, даже приблизительно: существуют такие плоские графы, что для каждой пары остовного дерева в графе и дополнительного остовного дерева в двойственном графе по крайней мере одно из двух деревьев имеет расстояния, которые значительно больше, чем расстояния в его графе. .[22]

Пример такого типа разложения на встречные деревья можно увидеть в некоторых простых типах лабиринты, с единым входом и без отключенных элементов его стен. В этом случае и стены лабиринта, и пространство между стенами имеют форму математического дерева. Если свободное пространство лабиринта разделено на простые ячейки (например, квадраты сетки), то эту систему ячеек можно рассматривать как вложение плоского графа, в котором древовидная структура стен образует остовное дерево граф и древовидная структура свободного пространства образуют остовное дерево двойственного графа.[23] Подобные пары пересекающихся деревьев также можно увидеть в древовидной структуре ручьев и рек внутри водосборный бассейн и двойной древовидный узор из линий хребта, разделяющих ручьи.[24]

Это разбиение ребер и их двойников на два дерева приводит к простому доказательству Формула Эйлера V − E + F = 2 для плоских графов с V вершины, E края и F лица. Любое остовное дерево и его дополнительное дуальное остовное дерево делят ребра на два подмножества V − 1 и F − 1 рёбер соответственно, а сложение размеров двух подмножеств дает уравнение

E = (V − 1) + (F − 1)

которая может быть преобразована в формулу Эйлера. В соответствии с Дункан Соммервилл, это доказательство формулы Эйлера связано с К. Г. К. фон Штаудт Geometrie der Lage (Нюрнберг, 1847).[25]

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

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

Любая формула подсчета, включающая вершины и грани, которая действительна для всех плоских графов, может быть преобразована с помощью плоской двойственности в эквивалентную формулу, в которой роли вершин и граней поменялись местами. Формула Эйлера, которая является самодуальной, является одним из примеров. Другой предоставлен Harary включает лемма о рукопожатии, согласно которому сумма градусы вершин любого графа равно удвоенному количеству ребер. В двойственной форме эта лемма утверждает, что в плоском графе сумма количества сторон граней графа равна удвоенному количеству ребер.[27]

В медиальный график плоского графа изоморфный к медиальному графику его двойника. Два плоских графа могут иметь изоморфные медиальные графы, только если они двойственны друг другу.[28]

Планарный граф с четырьмя или более вершинами является максимальным (никакие ребра не могут быть добавлены при сохранении планарности) тогда и только тогда, когда его дуальный граф является как 3-вершинно-связным, так и 3-регулярный.[29]

Связный планарный граф - это Эйлеров (имеет четную степень в каждой вершине) тогда и только тогда, когда его двойственный граф двудольный.[30] А Гамильтонов цикл в плоском графе грамм соответствует разбиению вершин дуального графа на два подмножества (внутреннее и внешнее цикла), у которых индуцированные подграфы оба дерева. Особенно, Гипотеза Барнетта о гамильтоничности кубических двудольных многогранных графов эквивалентна гипотезе о том, что любой эйлеров максимальный планарный граф можно разбить на два индуцированных дерева.[31]

Если планарный граф грамм имеет Полином Тутте Тграмм(Икс,у), то полином Тутте двойственного графа получается заменой Икс и у. По этой причине, если какое-то конкретное значение полинома Тутте предоставляет информацию об определенных типах структур в грамм, то замена аргументов полиномом Тутте даст соответствующую информацию для двойственных структур. Например, количество сильных ориентаций равно Тграмм(0,2) а количество ациклических ориентаций равно Тграмм(2,0).[32] За без моста планарные графы, раскраски графиков с k цвета соответствуют нигде-нулевые потоки по модулюk на дуальном графе. Например, теорема четырех цветов (существование 4-раскраски для каждого плоского графа) может быть выражено эквивалентно как утверждение, что двойственный к каждому планарному графу без мостов имеет нигде-нулевой 4-поток. Количество k-расцветки подсчитываются (с точностью до легко вычисляемого коэффициента) по значению полинома Тутте Тграмм(1 − k,0) и дважды число нигде-ноль k-потоки подсчитываются Тграмм(0,1 − k).[33]

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

Вариации

Направленные графы

В направленный плоский граф, дуальный граф также можно сделать направленным, ориентируя каждое дуальное ребро на 90 ° по часовой стрелке от соответствующего прямого ребра.[34] Строго говоря, эта конструкция не является двойственностью ориентированных планарных графов, поскольку, начиная с графа грамм и двойное взятие дуала не возвращается к грамм сам, но вместо этого строит граф, изоморфный транспонировать график из грамм, граф, сформированный из грамм перевернув все его края. Четырехкратное повторение двойного возвращает исходный график.

Слабый дуал

В слабый дуал из плоский график это подграф двойственного графа, вершины которого соответствуют ограниченным граням прямого графа. Плоский граф - это внешнепланарный тогда и только тогда, когда его слабый двойник является лес. Для любого плоского графа грамм, позволять грамм+ - плоский мультиграф, образованный добавлением одной новой вершины v перед безграничным лицом грамм, и подключение v к каждой вершине внешней грани (многократно, если вершина многократно появляется на границе внешней грани); тогда, грамм является слабым двойником (плоского) двойственного к грамм+.[35]

Бесконечные графы и мозаики

Концепция двойственности также применима к бесконечные графы вложен в плоскость, как и в конечные графы. Однако необходимо проявлять осторожность, чтобы избежать топологических осложнений, таких как точки на плоскости, которые не являются ни частью открытой области, не пересекающейся с графом, ни частью ребра или вершины графа. Когда все грани являются ограниченными областями, окруженными циклом графа, вложение бесконечного плоского графа также можно рассматривать как мозаика плоскости, покрытие плоскости замкнутыми дисками (плитками мозаики), внутренности которых (грани вложения) представляют собой непересекающиеся открытые диски. Плоская двойственность порождает понятие двойная тесселяция, мозаика, образованная размещением вершины в центре каждой плитки и соединением центров соседних плиток.[36]

Диаграмма Вороного (красный) и триангуляция Делоне (черный) конечного множества точек (черные точки)

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

Непланарные вложения

K7 двойственен График Хивуда в тор
K6 двойственен Граф Петерсена в проективная плоскость

Понятие двойственности можно расширить до вложения графов на двумерном коллекторы кроме самолета. Определение то же: есть двойственная вершина для каждой связный компонент из дополнять графа в многообразии и двойственное ребро для каждого ребра графа, соединяющее две двойственные вершины по обе стороны от ребра. В большинстве применений этой концепции она ограничивается вложениями со свойством, что каждая грань является топологическим диском; это ограничение обобщает требование для плоских графов связности графа. С этим ограничением двойственный к любому графу, вложенному в поверхность, имеет естественное вложение на ту же поверхность, так что двойственный к двойственному графу изоморфен и изоморфно вложен в исходный граф. Например, полный график K7 это тороидальный граф: он не плоский, но может быть вложен в тор, причем каждая грань вложения является треугольником. Это вложение имеет График Хивуда как его дуальный граф.[38]

Та же концепция одинаково хорошо работает для неориентируемые поверхности. Например, K6 может быть встроен в проективная плоскость с десятью треугольными гранями как полуикосаэдр, дуал которого Граф Петерсена встроенный как полудодекаэдр.[39]

Даже планарные графы могут иметь неплоские вложения, причем дуальные, производные от тех вложений, которые отличаются от их плоских двойственных. Например, четыре Полигоны Петри куба (шестиугольники, образованные удалением двух противоположных вершин куба) образуют шестиугольные грани вложения куба в тор. Двойственный граф этого вложения имеет четыре вершины, образующие полный граф K4 с двойными краями. При вложении тора этого двойственного графа шесть ребер, инцидентных каждой вершине, в циклическом порядке вокруг этой вершины, дважды проходят через три другие вершины. В отличие от ситуации на плоскости, это вложение куба и его двойника не единственно; у кубического графа есть несколько других вложений торов с разными двойниками.[38]

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

Еще одна операция над графами, вложенными в поверхность, - это Петри двойной, который использует Полигоны Петри вложения как грани нового вложения. В отличие от обычного дуального графа, он имеет те же вершины, что и исходный граф, но обычно лежит на другой поверхности.[40]Поверхностная дуальность и двойственность Петри - два из шести Уилсон операции, и вместе генерируют группу этих операций.[41]

Матроиды и алгебраические двойники

An алгебраический двойственный связного графа грамм это график грамм★ такой, что грамм и грамм★ одинаковый набор ребер, любые цикл из грамм это резать из грамм★, и любой разрез грамм это цикл грамм★. У каждого плоского графа есть алгебраический двойственный, который, вообще говоря, не уникален (подойдет любой двойственный, определенный вложением плоскости). На самом деле верно обратное, как установлено Хасслер Уитни в Критерий планарности Уитни:[42]

Связный граф грамм плоский тогда и только тогда, когда он имеет алгебраический двойственный.

Тот же факт может быть выражен в теории матроиды. Если M это графический матроид графа грамм, то график грамм★ является алгебраическим двойником грамм тогда и только тогда, когда графический матроид грамм★ это двойной матроид из M. Тогда критерий планарности Уитни можно перефразировать как утверждающий, что двойной матроид графического матроида M сам является графическим матроидом тогда и только тогда, когда лежащий в основе граф грамм из M плоский. Если грамм плоский, двойственный матроид - это графический матроид двойственного графа грамм. В частности, все дуальные графы для всех различных плоских вложений грамм, имеют изоморфные графические матроиды.[43]

Для непланарных вложений поверхности, в отличие от плоских двойственных, двойственный граф, как правило, не является алгебраическим двойственным прямому графу. А для неплоского графа грамм, двойной матроид графического матроида грамм сам по себе не графический матроид. Однако это все еще матроид, схемы которого соответствуют разрезам в грамм, и в этом смысле его можно рассматривать как обобщенный алгебраический двойственныйграмм.[44]

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

Приложения

Наряду с использованием в теории графов двойственность плоских графов имеет приложения в нескольких других областях математических и вычислительных исследований.

В географические информационные системы, проточные сети (например, сети, показывающие, как вода течет в системе ручьев и рек) двойственны сотовым сетям, описывающим дренаж разделяет. Эта двойственность может быть объяснена путем моделирования потоковой сети как связующего дерева на сеточный график соответствующего масштаба и моделирование водоотвода в виде дополнительного остовного дерева линий гребней на графике с двойной сеткой.[45]

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

В вычислительная геометрия, двойственность между Диаграммы Вороного и Триангуляции Делоне означает, что любой алгоритм для построения диаграммы Вороного можно сразу преобразовать в алгоритм триангуляции Делоне, и наоборот.[47] Ту же двойственность можно использовать и в заключительный элемент создание сетки. Алгоритм Ллойда, метод, основанный на диаграммах Вороного для перемещения набора точек на поверхности в более равномерно распределенные положения, обычно используется как способ сглаживания сетки конечных элементов, описываемой двойной триангуляцией Делоне. Этот метод улучшает сетку, делая ее треугольники более однородными по размеру и форме.[48]

в синтез из CMOS схем, синтезируемая функция представлена ​​формулой в Булева алгебра. Затем эта формула переводится на два последовательно-параллельные мультиграфы. Эти графики можно интерпретировать как принципиальные схемы в котором ребра графов представляют транзисторы, стробируемый входами функции. Одна схема вычисляет саму функцию, а другая вычисляет ее дополнение. Одна из двух схем получается путем преобразования конъюнкций и дизъюнкций формулы в последовательные и параллельные композиции графов соответственно. Другая схема меняет эту конструкцию на противоположную, преобразовывая конъюнкции и дизъюнкции формулы в параллельные и последовательные композиции графов.[49] Эти две схемы, дополненные дополнительным ребром, соединяющим вход каждой схемы с ее выходом, представляют собой плоские двойственные графы.[50]

История

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

Примечания

  1. ^ ван Линт, Дж. Х.; Уилсон, Ричард Майкл (1992), Курс комбинаторики, Cambridge University Press, стр. 411, г. ISBN  0-521-42260-4.
  2. ^ Бона, Миклош (2006), Прогулка по комбинаторике (2-е изд.), World Scientific Publishing Co. Pte. Ltd., Хакенсак, Нью-Джерси, стр. 276, г. Дои:10.1142/6177, ISBN  981-256-885-9, МИСТЕР  2361255.
  3. ^ Циглер, Гюнтер М. (1995), «2.3 Полярность», Лекции по многогранникам, Тексты для выпускников по математике, 152, стр. 59–64.
  4. ^ Вайсштейн, Эрик В., «Самодуальный граф», MathWorld
  5. ^ а б Серватиус, Бриджит; Кристофер, Питер Р. (1992), "Построение самодвойственных графов", Американский математический ежемесячник, 99 (2): 153–158, Дои:10.2307/2324184, JSTOR  2324184, МИСТЕР  1144356.
  6. ^ Thulasiraman, K .; Свами, М. Н. С. (2011), Графики: теория и алгоритмы, John Wiley & Sons, Упражнение 7.11, стр. 198, ISBN  978-1-118-03025-7.
  7. ^ См. Доказательство теоремы 5 в Серватиус и Кристофер (1992).
  8. ^ Нишизэки, Такао; Чиба, Norishige (2008), Плоские графы: теория и алгоритмы, Dover Книги по математике, Dover Publications, стр. 16, ISBN  978-0-486-46671-2.
  9. ^ Дженсен, Томми Р .; Тофт, Бьярн (1995), Проблемы с раскраской графиков, Серия Wiley-Interscience по дискретной математике и оптимизации, 39, Wiley, стр. 17, ISBN  978-0-471-02865-9, обратите внимание, что «мост» и «петля» - это двойственные понятия..
  10. ^ Балакришнан, В. К. (1997), Краткое изложение теории графов Шаума, McGraw Hill Professional, проблема 8.64, стр. 229, ISBN  978-0-07-005489-9.
  11. ^ а б Фулдс, Л. Р. (2012), Приложения теории графов, Springer, стр. 66–67, ISBN  978-1-4612-0933-1.
  12. ^ Бонди, Адриан; Мурти, США. (2008), «Планарные графики», Теория графов, Тексты для выпускников по математике, 244, Спрингер, теорема 10.28, с. 267, Дои:10.1007/978-1-84628-970-5, ISBN  978-1-84628-969-9, LCCN  2007923502
  13. ^ Анджелини, Патрицио; Блазиус, Томас; Руттер, Игнац (2014), "Проверка взаимной двойственности плоских графов", Международный журнал вычислительной геометрии и приложений, 24 (4): 325–346, arXiv:1303.1640, Дои:10.1142 / S0218195914600103, МИСТЕР  3349917.
  14. ^ Дистель, Рейнхард (2006), Теория графов, Тексты для выпускников по математике, 173, Springer, стр. 25, ISBN  978-3-540-26183-4.
  15. ^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001) [1990], Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, ISBN  0-262-03293-7
  16. ^ Годсил, Крис; Ройл, Гордон Ф. (2013), Алгебраическая теория графов, Тексты для выпускников по математике, 207, Спрингер, теорема 14.3.1, с. 312, ISBN  978-1-4613-0163-9.
  17. ^ Оксли, Дж. Г. (2006), Матроид Теория, Тексты для выпускников Оксфорда по математике, 3, Oxford University Press, стр. 93, ISBN  978-0-19-920250-8.
  18. ^ а б Чо, Чон Джин; Чен, Юн; Дин Ю (2007), "О (ко) обхвате связного матроида", Дискретная прикладная математика, 155 (18): 2456–2470, Дои:10.1016 / j.dam.2007.06.015, МИСТЕР  2365057.
  19. ^ а б Hartvigsen, D .; Мардон, Р. (1994), "Задача о минимальном разрезе всех пар и задача о базисе минимального цикла на плоских графах", Журнал SIAM по дискретной математике, 7 (3): 403–418, Дои:10.1137 / S0895480190177042.
  20. ^ Ной, Марк (2001), "Ациклические и полностью циклические ориентации в плоских графах", Американский математический ежемесячный журнал, 108 (1): 66–68, Дои:10.2307/2695680, JSTOR  2695680, МИСТЕР  1857074.
  21. ^ Тутте, В. Т. (1984), Теория графов, Энциклопедия математики и ее приложений, 21, Ридинг, Массачусетс: издательство Addison-Wesley Publishing Company, Advanced Book Program, стр.289, ISBN  0-201-13520-5, МИСТЕР  0746795.
  22. ^ Riley, T. R .; Терстон, В. П. (2006), «Отсутствие эффективных двойственных пар остовных деревьев в плоских графах», Электронный журнал комбинаторики, 13 (1): Примечание 13, 7, Дои:10.37236/1151, МИСТЕР  2255413.
  23. ^ Лайонс, Рассел (1998), «Вид с высоты птичьего полета на равнину между деревьями и лесами», Микрообследования с дискретной вероятностью (Принстон, Нью-Джерси, 1997), DIMACS Ser. Дискретная математика. Теорет. Comput. Наук, 41, Амер. Математика. Soc., Providence, RI, стр. 135–162, МИСТЕР  1630412. См. В частности стр. 138–139.
  24. ^ Фламмини, Алессандро (октябрь 1996 г.), Поведение масштабирования для моделей речной сети, Кандидат наук. Тезис, Международная школа перспективных исследований, стр. 40–41.
  25. ^ Соммервилл, Д. М. Я. (1958), Введение в геометрию N измерений, Дувр.
  26. ^ Эппштейн, Дэвид (2003), «Динамические генераторы топологически вложенных графов», Материалы 14-го симпозиума ACM / SIAM по дискретным алгоритмам, стр. 599–608, arXiv:cs.DS / 0207082.
  27. ^ Харари, Фрэнк (1969), Теория графов, Рединг, Массачусетс: Addison-Wesley Publishing Co., теорема 9.4, с. 142, МИСТЕР  0256911.
  28. ^ Гросс, Джонатан Л .; Йеллен, Джей, ред. (2003), Справочник по теории графов, CRC Press, стр. 724, г. ISBN  978-1-58488-090-5.
  29. ^ Хэ, Синь (1999), "План плоских графов", SIAM Журнал по вычислениям, 28 (6): 2150–2167, Дои:10.1137 / s0097539796308874.
  30. ^ а б Валлийский, Д. Дж. А. (1969), «Эйлер и двудольные матроиды», Журнал комбинаторной теории, 6 (4): 375–377, Дои:10.1016 / с0021-9800 (69) 80033-5, МИСТЕР  0237368.
  31. ^ Флорек, Ян (2010), "О гипотезе Барнетта", Дискретная математика, 310 (10–11): 1531–1535, Дои:10.1016 / j.disc.2010.01.018, МИСТЕР  2601261.
  32. ^ Лас Вергнас, Мишель (1980), «Выпуклость в ориентированных матроидах», Журнал комбинаторной теории, Серия B, 29 (2): 231–243, Дои:10.1016/0095-8956(80)90082-9, МИСТЕР  0586435.
  33. ^ Тутте, Уильям Томас (1953), Вклад в теорию хроматических многочленов
  34. ^ а б ди Баттиста, Джузеппе; Идс, Питер; Тамассия, Роберто; Толлис, Иоаннис Г. (1999), Рисование графиков: алгоритмы визуализации графиков, Прентис Холл, стр. 91, ISBN  978-0-13-301615-4.
  35. ^ Fleischner, Herbert J .; Геллер, Д. П .; Харари, Фрэнк (1974), "Внешнепланарные графы и слабые двойники", Журнал Индийского математического общества, 38: 215–219, МИСТЕР  0389672.
  36. ^ Вайсштейн, Эрик В., «Двойная тесселяция», MathWorld
  37. ^ Самет, Ханан (2006), Основы многомерных и метрических структур данных, Морган Кауфманн, стр. 348, ISBN  978-0-12-369446-1.
  38. ^ а б Гагарин, Андрей; Коджай, Уильям; Нейлсон, Дэниел (2003), «Вложения малых графов на торе» (PDF), Cubo, 5: 351–371, архивировано с оригинал (PDF) на 2017-02-01, получено 2015-08-12.
  39. ^ Накамото, Атсухиро; Негами, Сейя (2000), "Полносимметричные вложения графов на замкнутых поверхностях", Воспоминания об университете Осака Кёику, 49 (1): 1–15, МИСТЕР  1833214.
  40. ^ Горини, Екатерина А. (2000), Геометрия в действии, Примечания МАА, 53, Cambridge University Press, стр. 181, ISBN  9780883851647
  41. ^ Jones, G.A .; Торнтон, Дж. С. (1983), "Операции над отображениями и внешние автоморфизмы", Журнал комбинаторной теории, Серия B, 35 (2): 93–103, Дои:10.1016/0095-8956(83)90065-5, МИСТЕР  0733017
  42. ^ Уитни, Хасслер (1932), «Неразделимые и плоские графы», Труды Американского математического общества, 34 (2): 339–362, Дои:10.1090 / S0002-9947-1932-1501641-2.
  43. ^ Оксли, Дж. Г. (2006), «5.2 Двойственность в графических матроидах», Теория матроидов, Оксфордские выпускные тексты по математике, 3, Oxford University Press, стр. 143, ISBN  978-0-19-920250-8.
  44. ^ Тутте, В. Т. (2012), Теория графов, как я ее знал, Оксфордская серия лекций по математике и ее приложениям, 11, Oxford University Press, стр. 87, ISBN  978-0-19-966055-1.
  45. ^ Чорли, Ричард Дж .; Хаггетт, Питер (2013), Интегрированные модели в географии, Рутледж, стр. 646, г. ISBN  978-1-135-12184-6.
  46. ^ Кандел, Авраам; Бунке, Хорст; Последний, Марк (2007), Прикладная теория графов в компьютерном зрении и распознавании образов, Исследования в области вычислительного интеллекта, 52, Springer, стр. 16, ISBN  978-3-540-68020-8.
  47. ^ Девадосс, Сатьян Л.; О'Рурк, Джозеф (2011), Дискретная и вычислительная геометрия, Princeton University Press, стр. 111, ISBN  978-1-4008-3898-1.
  48. ^ Ду, Цян; Гинцбургер, Макс (2002), "Создание и оптимизация сетки на основе центроидных мозаик Вороного", Прикладная математика и вычисления, 133 (2–3): 591–607, Дои:10.1016 / S0096-3003 (01) 00260-0.
  49. ^ Пиге, Кристиан (2004), «7.2.1 Статическая логика CMOS», Дизайн маломощной электроники, CRC Press, стр. 7-1 - 7-2, ISBN  978-1-4200-3955-9.
  50. ^ Кэслин, Хуберт (2008), «8.1.4 Составные или сложные ворота», Проектирование цифровых интегральных схем: от архитектур СБИС до изготовления КМОП, Cambridge University Press, стр. 399, ISBN  978-0-521-88267-5.
  51. ^ Ричсон, Дэвид С. (2012), Драгоценный камень Эйлера: формула многогранника и рождение топологии, Princeton University Press, стр. 58–61, ISBN  978-1-4008-3856-1.
  52. ^ Риппманн, Маттиас (2016), Конструкция оболочки фуникулера: геометрические подходы к поиску форм и изготовлению дискретных фуникулёров, Абилитация диссертация, Дисс. ETH № 23307, ETH Цюрих, стр. 39–40, Дои:10.3929 / ethz-a-010656780, HDL:20.500.11850/116926. Смотрите также Эриксон, Джефф (9 июня 2016 г.), Диаграммы взаимных сил от Nouvelle Méchanique ou Statique Пьера де Вариньона (1725), Является ли это старейшей иллюстрацией двойственности между планарными графами?.
  53. ^ Биггс, Норман; Ллойд, Э. Кейт; Уилсон, Робин Дж. (1998), Теория графов, 1736–1936 гг., Издательство Оксфордского университета, п. 118, ISBN  978-0-19-853916-2.
  54. ^ Уитни, Хасслер (1931), «Теорема о графах», Анналы математики, Вторая серия, 32 (2): 378–390, Дои:10.2307/1968197, JSTOR  1968197, МИСТЕР  1503003.

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