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

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

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

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

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

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

Примеры [ править ]

Циклы и диполи [ править ]

Цикл графа

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

Двойные многогранники [ править ]

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

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

Самодуальные графики [ править ]

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

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

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

Свойства [ править ]

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

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

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

Уникальность [ править ]

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

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

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

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

Порезы и циклы [ править ]

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

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

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

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

Связующие деревья [ править ]

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

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

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

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

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

которая может быть преобразована в формулу Эйлера. Согласно Дункану Соммервиллю , это доказательство формулы Эйлера получено благодаря работе KGC Von Staudt Geometrie der Lage (Nürnberg, 1847). [25]

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

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

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

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

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

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

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

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

Варианты [ править ]

Направленные графики [ править ]

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

Слабый дуал [ править ]

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

Бесконечные графики и мозаики [ править ]

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

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

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

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

K 7 двойственен графу Хивуда в торе
K 6 двойственен графу Петерсена в проективной плоскости

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

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

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

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

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

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

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

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

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

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

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

Приложения [ править ]

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

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

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

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

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

История [ править ]

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

Заметки [ править ]

  1. ^ ван Линт, JH ; Уилсон, Ричард Майкл (1992), Курс комбинаторики , Cambridge University Press, стр. 411, ISBN 0-521-42260-4.
  2. ^ Bona, Миклош (2006), Прогулка по комбинаторике (2 - е изд.), World Scientific Publishing Co. Pte. Ltd., Хакенсак, Нью-Джерси, стр. 276, DOI : 10,1142 / 6177 , ISBN 981-256-885-9, Руководство по ремонту  2361255.
  3. ↑ Ziegler, Günter M. (1995), «2.3 Полярность», Лекции по многогранникам , Тексты для выпускников по математике , 152 , стр. 59–64.
  4. ^ Вайсштейн, Эрик В. , «Автодуальный граф» , MathWorld
  5. ^ a b Серватиус, Бриджит ; Кристофер, Питер Р. (1992), "Построение самодуальных графов", Американский Математический Месячный , 99 (2): 153-158, DOI : 10,2307 / 2324184 , JSTOR 2324184 , MR 1144356  .
  6. ^ Туласираман, К .; Свами, MNS (2011), Графы: теория и алгоритмы , John Wiley & Sons, Упражнение 7.11, стр. 198, ISBN 978-1-118-03025-7.
  7. ^ См. Доказательство теоремы 5 в Servatius & Christopher (1992) .
  8. ^ Нишизэки, Такао; Чиба, Норишиге (2008), Планарные графы: теория и алгоритмы , Dover Books on Mathematics, Dover Publications, стр. 16, ISBN 978-0-486-46671-2.
  9. ^ Дженсен, Томми Р .; Тофт, Бьярн (1995), Проблемы раскраски графов , Серия Wiley-Interscience по дискретной математике и оптимизации, 39 , Wiley, p. 17, ISBN 978-0-471-02865-9, Обратите внимание , что «мост» и «петля» являются двойными понятиями.
  10. ^ Balakrishnan, В. К. (1997), Outline Schaum по теории графов , McGraw Hill Professional, проблема 8,64, стр. 229, ISBN 978-0-07-005489-9.
  11. ^ a b Фулдс, Л. Р. (2012), Приложения теории графов , Springer, стр. 66–67, ISBN 978-1-4612-0933-1.
  12. ^ Бонди, Адриан ; Мурти, USR (2008), «Плоские графы» , теория графов , тексты для выпускников по математике, 244 , Springer, теорема 10.28, с. 267, DOI : 10.1007 / 978-1-84628-970-5 , ISBN 978-1-84628-969-9, LCCN  2007923502
  13. ^ Анджелини, Патрицио; Блазиус, Томас; Раттер, Игнац (2014), "Проверка взаимной двойственности плоских графов", Международный журнал вычислительной геометрии и приложений , 24 (4): 325-346, Arxiv : 1303,1640 , DOI : 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. ^ Oxley, JG (2006), Теория матроидов , Тексты для выпускников Оксфорда по математике, 3 , Oxford University Press, стр. 93, ISBN 978-0-19-920250-8.
  18. ^ a b Чо, Юнг Джин; Чен, Юн; Дин, Ю. (2007), "О (со) обхватом связной матроиды", Дискретная прикладная математика , 155 (18): 2456-2470, DOI : 10.1016 / j.dam.2007.06.015 , МР 2365057 .
  19. ^ a b Hartvigsen, D .; Мардон, Р. (1994), «все-пар проблема мин крой и минимальный цикл основа задача о плоских графов», SIAM журнал по дискретной математике , 7 (3): 403-418, DOI : 10,1137 / S0895480190177042.
  20. ^ Noy, Марк (2001), "ациклические и циклические полностью ориентации в плоских графах", American Mathematical Monthly , 108 (1): 66-68, DOI : 10,2307 / 2695680 , JSTOR 2695680 , MR 1857074  .
  21. ^ Tutte, WT (1984), теория графов , Энциклопедия математики и ее применения, 21 , Reading, MA: Addison-Wesley Publishing Company, Advanced Program Book, стр. 289 , ISBN 0-201-13520-5, Руководство по ремонту  0746795.
  22. ^ Райли, TR; Thurston, WP (2006), "Отсутствие эффективных двойственных пар остовных деревьев в плоских графах" , Электронный журнал комбинаторике , 13 (1): Примечание 13, 7, DOI : 10,37236 / 1151 , MR 2255413 .
  23. ^ Лайонс, Рассел (1998), "Вид с высоты птичьего полета на равномерные покрывающие деревья и леса" , Микрообследования с дискретной вероятностью (Принстон, Нью-Джерси, 1997) , DIMACS Ser. Дискретная математика. Теорет. Comput. Наук, 41 , амер. Математика. Soc., Providence, RI, стр. 135–162, MR 1630412 . См., В частности, стр. 138–139 .
  24. ^ Фламмини, Алессандро (октябрь 1996 г.), Масштабирование моделей речной сети , доктор философии. дипломная работа Международной школы перспективных исследований , стр. 40–41..
  25. ^ Соммервилл, DMY (1958), Введение в геометрию N измерений , Dover.
  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, DOI : 10,1137 / s0097539796308874.
  30. ^ Б Валлийский, DJA (1969), "Эйлер и двудольные матроиды", Журнал комбинаторной теории , 6 (4): 375-377, DOI : 10.1016 / s0021-9800 (69) 80033-5 , МР 0237368 .
  31. ^ Florek Ян (2010), "О гипотезе Барнетта в" Discrete Mathematics , 310 (10-11): 1531-1535, DOI : 10.1016 / j.disc.2010.01.018 , MR 2601261 .
  32. ^ Лас Vergnas, Мишель (1980), "Выпуклость в ориентированных матроидах", Журнал комбинаторной теории , Series B, 29 (2): 231-243, DOI : 10,1016 / 0095-8956 (80) 90082-9 , МР 0586435 .
  33. ^ Тутте, Уильям Томас (1953), вклад в теорию хроматических многочленов
  34. ^ а б ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1999), Рисование графиков: алгоритмы визуализации графиков , Прентис Холл, стр. 91, ISBN 978-0-13-301615-4.
  35. ^ Флейшнер, Герберт Дж .; Геллер, Д.П .; Харари, Франк (1974), «Внешнепланарные графы и слабые двойники», Журнал Индийского математического общества , 38 : 215–219, MR 0389672 .
  36. Перейти ↑ Weisstein, Eric W. , «Dual Tessellation» , MathWorld
  37. ^ Самет, Ханан (2006), Основы многомерных и метрических структур данных , Морган Кауфманн, стр. 348, ISBN 978-0-12-369446-1.
  38. ^ a b Гагарин, Андрей; Коджай, Уильям ; Нейлсон, Дэниел (2003), «Вложения малых графов на торе» (PDF) , Cubo , 5 : 351–371, заархивировано из оригинала (PDF) 01 февраля 2017 г. , получено 12 августа 2015 г. .
  39. ^ Накамото, Atsuhiro; Негами, Сейя (2000), «Полносимметричные вложения графов на замкнутых поверхностях», Мемуары Университета Осаки Кёику , 49 (1): 1–15, MR 1833214 .
  40. ^ Горини, Кэтрин А. (2000), Геометрия в действии, Примечания МАА, 53 , Cambridge University Press, стр. 181, ISBN 9780883851647
  41. ^ Джонс, Джорджия; Торнтон, Дж. С. (1983), «Операции над отображениями и внешние автоморфизмы», Журнал комбинаторной теории , серия B, 35 (2): 93–103, DOI : 10.1016 / 0095-8956 (83) 90065-5 , MR 0733017 
  42. ^ Уитни, Hassler (1932), "Несепарабельные и плоские графы", Труды Американского математического общества , 34 (2): 339-362, DOI : 10,1090 / S0002-9947-1932-1501641-2.
  43. ^ Oxley, JG (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), Интегрированные модели в географии , Routledge, стр. 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. ^ Ду, Цян; Gunzburger, Макс (2002), "генерация и оптимизация сетки на основе центроидального Вороного мозаика", Прикладная математика и вычисление , 133 (2-3): 591-607, DOI : 10.1016 / S0096-3003 (01) 00260-0.
  49. ^ Piguet, Кристиан (2004), "7.2.1 Статическая CMOS логика", Low-Power Electronics Design , CRC Press, стр 7-1. - 7-2, ISBN 978-1-4200-3955-9.
  50. ^ Kaeslin, Hubert (2008), "8.1.4 Композитный или сложные ворота", Digital Integrated Circuit Design: С VLSI архитектурами CMOS Fabrication , Cambridge University Press, стр. 399, ISBN 978-0-521-88267-5.
  51. ^ Ричсон, Дэвид С. (2012), Драгоценный камень Эйлера: формула многогранника и рождение топологии , Princeton University Press, стр. 58–61, ISBN 978-1-4008-3856-1.
  52. ^ Rippmann, Матиас (2016), Фуникулер Shell Дизайн: геометрические подходы к Форме Обретения и изготовление дискретных Фуникулер структур , Habilitation диссертации, Дис. ETH No. 23307, ETH Zurich , стр. 39–40, doi : 10.3929 / ethz-a-010656780 , hdl : 20.500.11850 / 116926. Смотрите также Erickson, Джефф (9 июня 2016), Взаимные силовые схемы из Nouvelle Mechanique OU Statique Пьера де Varignon (1725) , Это самая старая иллюстрация двойственности между планарными графами?.
  53. ^ Биггс, Норман ; Ллойд, Э. Кейт; Уилсон, Робин Дж. (1998), Теория графов, 1736–1936 , Oxford University Press, стр. 118 , ISBN 978-0-19-853916-2.
  54. ^ Уитни, Hassler (1931), "Теорема о графах", Анналы математики , второй серии 32 (2): 378-390, DOI : 10,2307 / 1968197 , JSTOR 1968197 , MR 1503003  .

Внешние ссылки [ править ]

  • Вайсштейн, Эрик В. , «Двойной граф» , MathWorld