В математической дисциплине теории графов двойственный граф планарного графа G — это граф, имеющий вершину для каждой грани G. Двойственный граф имеет ребро для каждой пары граней в G , которые отделены друг от друга ребром, и самопетлю, когда одна и та же грань появляется по обе стороны ребра. Таким образом, каждое ребро e графа G имеет соответствующее двойственное ребро, конечные точки которого являются двойственными вершинами, соответствующими граням по обе стороны e . Определение двойственности зависит от выбора вложения графа G , поэтому это свойство плоских графов (графов, которые уже вложены в плоскость), а не плоских графов (графов, которые могут быть вложены, но для которых вложение еще неизвестно). Для плоских графов, как правило, может быть несколько двойственных графов, в зависимости от выбора планарного вложения графа.
Исторически первой формой дуальности графов , которая была признана, было объединение Платоновых тел в пары дуальных многогранников . Дуальность графов является топологическим обобщением геометрических концепций дуальных многогранников и дуальных мозаик и, в свою очередь, обобщается комбинаторно концепцией дуального матроида . Вариации дуальности планарных графов включают версию дуальности для ориентированных графов и дуальность для графов, встроенных в неплоские двумерные поверхности.
Эти понятия дуальных графов не следует путать с другим понятием — дуальным графом графа от ребра к вершине или линейным графом графа.
Термин «дуальный» используется, поскольку свойство быть дуальным графом симметрично , что означает, что если H является дуальным связному графу 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-реберному разрезу в первичном графе (паре ребер, удаление которых разъединяет граф). Следовательно, планарный граф является простым тогда и только тогда, когда его двойственный граф не имеет 1- или 2-реберных разрезов; то есть, если он 3-ребро-связан . Простые планарные графы, двойственные графы которых являются простыми, являются в точности 3-ребро-связанными простыми планарными графами. [10] Этот класс графов включает в себя, но не является тем же самым, классом 3-вершинно-связанных простых планарных графов. Например, рисунок, показывающий самодвойственный граф, является 3-рёберно-связанным (и, следовательно, его двойственный граф является простым), но не является 3-вершинно-связанным.
Поскольку дуальный граф зависит от конкретного вложения, дуальный граф планарного графа не является уникальным, в том смысле, что один и тот же планарный граф может иметь неизоморфные дуальные графы. [11] На рисунке синие графы изоморфны, но их дуальные красные графы — нет. Верхний красный дуальный граф имеет вершину со степенью 6 (соответствующую внешней грани синего графа), тогда как в нижнем красном графе все степени меньше 6.
Хасслер Уитни показал, что если граф 3-связен , то вложение, а значит и двойственный граф, являются единственными. [12] По теореме Штейница эти графы являются в точности полиэдральными графами , графами выпуклых многогранников. Планарный граф 3-вершинно связен тогда и только тогда, когда его двойственный граф 3-вершинно связен. Более того, планарный двусвязный граф имеет единственное вложение, а значит и единственное двойственное, тогда и только тогда, когда он является подразделением 3-вершинно связного планарного графа (графа, образованного из 3-вершинно связного планарного графа путем замены некоторых его ребер путями). [13] Для некоторых планарных графов, которые не являются 3-вершинно связными, таких как полный двудольный граф K 2,4 , вложение не является единственным, но все вложения изоморфны. При этом, соответственно, все двойственные графы изоморфны.
Поскольку различные вложения могут приводить к различным дуальным графам, проверка того, является ли один граф дуальным другому (без знания их вложений), является нетривиальной алгоритмической задачей. Для двусвязных графов ее можно решить за полиномиальное время, используя деревья SPQR графов для построения канонической формы для отношения эквивалентности наличия общего взаимного дуального. Например, два красных графа на иллюстрации эквивалентны согласно этому отношению. Однако для планарных графов, которые не являются двусвязными, это отношение не является отношением эквивалентности, и задача проверки взаимной дуальности является NP-полной . [14]
Сечение в произвольном связном графе — это подмножество ребер, определенное из разбиения вершин на два подмножества, путем включения ребра в подмножество, когда оно имеет одну конечную точку на каждой стороне разбиения. Удаление ребер из сечения обязательно разбивает граф по крайней мере на два связных компонента. Минимальное сечение (также называемое связью) — это сечение со свойством, что каждое собственное подмножество сечения само по себе не является разрезом. Минимальное сечение связного графа обязательно разделяет его граф ровно на два компонента и состоит из множества ребер, которые имеют одну конечную точку в каждом компоненте. [15] Простой цикл — это связный подграф , в котором каждая вершина цикла инцидентна ровно двум ребрам цикла. [16]
В связном плоском графе G каждый простой цикл графа G соответствует минимальному сечению в двойственном графе G , и наоборот. [17] Это можно рассматривать как форму теоремы о кривой Жордана : каждый простой цикл разделяет грани графа G на грани внутри цикла и грани вне цикла, а двойственные ребра цикла — это в точности ребра, которые пересекают внутреннюю часть во внешнюю. [18] Обхват любого плоского графа ( размер его наименьшего цикла) равен реберной связности его двойственного графа (размер его наименьшего сечений). [19]
Эта двойственность распространяется от отдельных сечений и циклов до векторных пространств, определяемых из них. Пространство циклов графа определяется как семейство всех подграфов, имеющих четную степень в каждой вершине; его можно рассматривать как векторное пространство над конечным полем из двух элементов , с симметрической разностью двух наборов ребер, действующей как операция сложения векторов в векторном пространстве. Аналогично, пространство сечений графа определяется как семейство всех сечений, с сложением векторов, определенным таким же образом. Тогда пространство циклов любого планарного графа и пространство сечений его двойственного графа изоморфны как векторные пространства. [20] Таким образом, ранг планарного графа ( размерность его пространства сечений) равен циклотомическому числу его двойственного (размерности его пространства циклов) и наоборот. [11] Базис циклов графа — это набор простых циклов, которые образуют базис пространства циклов (каждый подграф четной степени может быть образован ровно одним способом как симметрическая разность некоторых из этих циклов). Для рёберно-взвешенных планарных графов (с достаточно общими весами, так что никакие два цикла не имеют одинакового веса) базис цикла минимального веса графа является двойственным дереву Гомори–Ху двойственного графа, набору вложенных разрезов, которые вместе включают минимальный разрез , разделяющий каждую пару вершин в графе. Каждый цикл в базисе цикла минимального веса имеет набор рёбер, которые являются двойственными рёбрам одного из разрезов в дереве Гомори–Ху. Когда веса циклов могут быть связаны, базис цикла минимального веса может быть не уникальным, но в этом случае всё ещё верно, что дерево Гомори–Ху двойственного графа соответствует одному из базисов цикла минимального веса графа. [20]
В ориентированных планарных графах простые ориентированные циклы являются двойственными направленным разрезам (разбиениям вершин на два подмножества таким образом, что все ребра идут в одном направлении, из одного подмножества в другое). Сильно ориентированные планарные графы (графы, базовый неориентированный граф которых связен, и в которых каждое ребро принадлежит циклу) являются двойственными направленным ациклическим графам , в которых ни одно ребро не принадлежит циклу. Другими словами, сильные ориентации связного планарного графа (назначения направлений ребрам графа, которые приводят к сильно связанному графу ) являются двойственными ациклическим ориентациям (назначениям направлений, которые производят направленный ациклический граф ). [21] Таким же образом диджоины (наборы ребер, которые включают ребро из каждого направленного разреза) являются двойственными наборам дуг обратной связи (наборам ребер, которые включают ребро из каждого цикла). [22]
Связующее дерево можно определить как набор ребер, который вместе со всеми вершинами графа образует связный и ациклический подграф. Но, по двойственности разреза-цикла, если набор S ребер в плоском графе G является ациклическим (не имеет циклов), то набор ребер, двойственных к S, не имеет разрезов, из чего следует, что дополнительный набор двойственных ребер (двойственных ребрам, которые не находятся в S ) образует связный подграф. Симметрично, если S связен, то ребра, двойственные дополнению к S, образуют ациклический подграф. Следовательно, когда S обладает обоими свойствами — он связен и ацикличен — то же самое верно для дополнительного набора в двойственном графе. То есть, каждое остовное дерево G является дополнительным к остовному дереву двойственного графа, и наоборот. Таким образом, ребра любого планарного графа и его двойственного графа могут быть вместе разделены (несколькими различными способами) на два остовных дерева, одно в основном и одно в двойственном, которые вместе простираются на все вершины и грани графа, но никогда не пересекаются друг с другом. В частности, минимальное остовное дерево графа G является дополнительным к максимальному остовному дереву двойственного графа. [23] Однако это не работает для деревьев кратчайших путей , даже приблизительно: существуют планарные графы, такие что для каждой пары остовного дерева в графе и дополнительного остовного дерева в двойственном графе, по крайней мере одно из двух деревьев имеет расстояния, которые значительно больше расстояний в его графе. [24]
Пример такого типа разложения на интердигитирующие деревья можно увидеть в некоторых простых типах лабиринтов с одним входом и без разъединенных компонентов его стен. В этом случае как стены лабиринта, так и пространство между стенами принимают форму математического дерева. Если свободное пространство лабиринта разбить на простые ячейки (например, квадраты сетки), то эту систему ячеек можно рассматривать как вложение плоского графа, в котором древовидная структура стен образует остовное дерево графа, а древовидная структура свободного пространства образует остовное дерево двойственного графа. [25] Аналогичные пары интердигитирующих деревьев можно также увидеть в древовидной структуре ручьев и рек в пределах водосборного бассейна и в двойном древовидном структуре хребтов, разделяющих ручьи. [26]
Это разбиение ребер и их дуалов на два дерева приводит к простому доказательству формулы Эйлера V − E + F = 2 для планарных графов с V вершинами, E ребрами и F гранями. Любое остовное дерево и его дополнительное дуальное остовное дерево разбивают ребра на два подмножества V − 1 и F − 1 ребер соответственно, а сложение размеров двух подмножеств дает уравнение
которые могут быть переставлены, чтобы сформировать формулу Эйлера. Согласно Дункану Соммервиллю , это доказательство формулы Эйлера принадлежит К. Г. К. Фон Штаудту в его работе Geometrie der Lage (Нюрнберг, 1847). [27]
В непланарных поверхностных вложениях набор двойственных ребер, дополнительных к остовному дереву, не является двойственным остовным деревом. Вместо этого этот набор ребер является объединением двойственного остовного дерева с небольшим набором дополнительных ребер, число которых определяется родом поверхности, на которой граф вложен. Дополнительные ребра в сочетании с путями в остовных деревьях могут быть использованы для генерации фундаментальной группы поверхности. [28]
Любая формула подсчета, включающая вершины и грани, которая действительна для всех планарных графов, может быть преобразована планарной двойственностью в эквивалентную формулу, в которой роли вершин и граней поменялись местами. Формула Эйлера, которая является самодвойственной, является одним из примеров. Другая, данная Харари, включает лемму о рукопожатии , согласно которой сумма степеней вершин любого графа равна удвоенному числу ребер. В своей двойственной форме эта лемма утверждает, что в плоском графе сумма чисел сторон граней графа равна удвоенному числу ребер. [29]
Медиальный граф плоского графа изоморфен медиальному графу его двойственного. Два планарных графа могут иметь изоморфные медиальные графы только в том случае, если они двойственны друг другу. [30]
Планарный граф с четырьмя или более вершинами является максимальным (нельзя добавить больше ребер, сохраняя планарность) тогда и только тогда, когда его двойственный граф является одновременно 3-вершинно-связным и 3-регулярным . [31]
Связный планарный граф является эйлеровым (имеет четную степень в каждой вершине) тогда и только тогда, когда его двойственный граф является двудольным . [32] Гамильтонов цикл в планарном графе G соответствует разбиению вершин двойственного графа на два подмножества (внутреннюю и внешнюю часть цикла), чьи индуцированные подграфы являются деревьями. В частности, гипотеза Барнетта о гамильтоновости кубических двудольных полиэдральных графов эквивалентна гипотезе о том, что каждый эйлеров максимальный планарный граф может быть разложен на два индуцированных дерева. [33]
Если планарный граф G имеет полином Тутта T G ( x , y ) , то полином Тутта его двойственного графа получается путем замены x и y . По этой причине, если некоторое конкретное значение полинома Тутта предоставляет информацию об определенных типах структур в G , то замена аргументов полинома Тутта даст соответствующую информацию для двойственных структур. Например, число сильных ориентаций равно T G (0,2) , а число ациклических ориентаций равно T G (2,0) . [34] Для планарных графов без мостов раскраски графа с k цветами соответствуют потокам, не имеющим нигде нуля, по модулю k на двойственном графе. Например, теорема о четырех цветах (существование 4-раскраски для каждого планарного графа) может быть выражена эквивалентно как утверждение, что двойственный граф каждого планарного графа без мостов имеет 4-поток, не имеющий нигде нуля. Число k -раскрасок подсчитывается (с точностью до легко вычисляемого множителя) по значению полинома Тутта T G (1 − k ,0) и, соответственно, число нигде не нулевых k -потоков подсчитывается по значению T G (0,1 − k ) . [35]
St -планарный граф — это связный планарный граф вместе с биполярной ориентацией этого графа, ориентацией , которая делает его ацикличным с одним источником и одним стоком, оба из которых должны находиться на одной грани друг с другом. Такой граф можно превратить в сильно связный граф, добавив еще одно ребро, от стока обратно к источнику, через внешнюю грань. Двойственный этому расширенному планарному графу сам является расширением другого st -планарного графа. [36]
В ориентированном плоском графе двойственный граф может быть также сделан направленным, ориентируя каждое двойственное ребро на 90° по часовой стрелке от соответствующего первичного ребра. [36] Строго говоря, эта конструкция не является двойственностью ориентированных планарных графов, поскольку, начиная с графа G и дважды беря двойственный, мы не возвращаемся к самому G , а вместо этого создаем граф, изоморфный транспонированному графу G , графу, образованному из G путем обращения всех его ребер. Четыре раза беря двойственный, мы возвращаемся к исходному графу .
Слабое дуальное графа плоского графа — это подграф дуального графа, вершины которого соответствуют ограниченным граням первичного графа. Плоский граф является внешнепланарным тогда и только тогда, когда его слабое дуальное граф является лесом . Для любого плоского графа G пусть G + будет плоским мультиграфом, образованным добавлением одной новой вершины v в неограниченную грань G и соединением v с каждой вершиной внешней грани (несколько раз, если вершина появляется несколько раз на границе внешней грани); тогда G является слабодуальным графом (плоского) дуального графа G + . [37]
Концепция двойственности применима как к бесконечным графам, вложенным в плоскость, так и к конечным графам. Однако необходимо проявлять осторожность, чтобы избежать топологических осложнений, таких как точки плоскости, которые не являются ни частью открытой области, не пересекающейся с графом, ни частью ребра или вершины графа. Когда все грани являются ограниченными областями, окруженными циклом графа, бесконечное планарное вложение графа также можно рассматривать как тесселяцию плоскости, покрытие плоскости замкнутыми дисками (плитками тесселяции), внутренности которых (грани вложения) являются непересекающимися открытыми дисками. Плоская двойственность порождает понятие дуальной тесселяции , тесселяции, образованной путем размещения вершины в центре каждой плитки и соединения центров смежных плиток. [38]
Концепция дуальной мозаики может быть также применена к разбиениям плоскости на конечное число областей. Она тесно связана, но не совсем совпадает с дуальностью планарного графа в этом случае. Например, диаграмма Вороного конечного набора точечных сайтов — это разбиение плоскости на многоугольники, внутри которых один сайт находится ближе, чем любой другой. Сайты на выпуклой оболочке входа порождают неограниченные многоугольники Вороного, две стороны которых являются бесконечными лучами, а не конечными отрезками прямых. Двойственной этой диаграмме является триангуляция Делоне входа, планарный граф, который соединяет два сайта ребром всякий раз, когда существует окружность, содержащая эти два сайта и никаких других сайтов. Ребра выпуклой оболочки входа также являются ребрами триангуляции Делоне, но они соответствуют лучам, а не отрезкам прямых диаграммы Вороного. Эту двойственность между диаграммами Вороного и триангуляциями Делоне можно превратить в двойственность между конечными графами одним из двух способов: добавив искусственную вершину на бесконечности к диаграмме Вороного, чтобы она служила другой конечной точкой для всех ее лучей, [39] или рассматривая ограниченную часть диаграммы Вороного как слабую двойственную триангуляции Делоне. Хотя диаграмма Вороного и триангуляция Делоне являются двойственными, их вложение в плоскость может иметь дополнительные пересечения за пределами пересечений двойственных пар ребер. Каждая вершина треугольника Делоне расположена внутри соответствующей грани диаграммы Вороного. Каждая вершина диаграммы Вороного расположена в центре описанной окружности соответствующего треугольника триангуляции Делоне, но эта точка может лежать вне его треугольника.
Концепция двойственности может быть расширена до вложений графов на двумерных многообразиях , отличных от плоскости. Определение то же самое: существует двойственная вершина для каждого связного компонента дополнения графа в многообразии и двойственное ребро для каждого ребра графа, соединяющего две двойственные вершины по обе стороны ребра. В большинстве приложений этой концепции она ограничена вложениями со свойством, что каждая грань является топологическим диском; это ограничение обобщает требование для планарных графов, что граф должен быть связным. С этим ограничением двойственный граф любого поверхностно вложенного графа имеет естественное вложение на той же поверхности, так что двойственный граф двойственного изоморфен и изоморфно вложен в исходный граф. Например, полный граф K 7 является тороидальным графом : он не является планарным, но может быть вложен в тор, причем каждая грань вложения является треугольником. Это вложение имеет граф Хивуда в качестве своего двойственного графа. [40]
Та же концепция работает одинаково хорошо для неориентируемых поверхностей . Например, K 6 может быть вложен в проективную плоскость с десятью треугольными гранями как полуикосаэдр , чей двойственный граф — граф Петерсена, вложенный как полудодекаэдр . [41]
Даже планарные графы могут иметь непланарные вложения, с дуальными, полученными из тех вложений, которые отличаются от их планарных дуальных. Например, четыре многоугольника Петри куба (шестиугольники, образованные путем удаления двух противоположных вершин куба) образуют шестиугольные грани вложения куба в тор . Двойственный граф этого вложения имеет четыре вершины, образующие полный граф K 4 с удвоенными ребрами. В торическом вложении этого дуального графа шесть ребер, инцидентных каждой вершине, в циклическом порядке вокруг этой вершины, дважды циклически проходят через три другие вершины. В отличие от ситуации на плоскости, это вложение куба и его дуального не является уникальным; кубический граф имеет несколько других вложений тора с различными дуальными. [40]
Многие эквивалентности между свойствами простых и двойственных графов планарных графов не могут быть обобщены на непланарные двойственные графы или требуют дополнительной осторожности при их обобщении.
Другая операция на графах, вложенных в поверхность, — это двойственная Петри , которая использует многоугольники Петри вложения как грани нового вложения. В отличие от обычного двойственного графа, он имеет те же вершины, что и исходный граф, но, как правило, лежит на другой поверхности. [42] Двойственность поверхности и двойственность Петри — две из шести операций Уилсона , и вместе они порождают группу этих операций. [43]
Алгебраический дуальный граф связного графа G — это граф G * такой, что G и G * имеют одинаковое множество ребер, любой цикл графа G является разрезом графа G * , а любой разрез графа G является циклом графа G * . Каждый планарный граф имеет алгебраический дуальный граф, который в общем случае не является единственным (подойдет любой дуальный граф, определенный вложением плоскости). Обратное утверждение на самом деле верно, как установил Хасслер Уитни в критерии планарности Уитни : [44]
Тот же факт может быть выражен в теории матроидов . Если M является графическим матроидом графа G , то граф G * является алгебраическим двойственным к G тогда и только тогда, когда графический матроид G * является двойственным матроидом M. Тогда критерий планарности Уитни можно перефразировать как утверждение, что двойственный матроид графического матроида M сам является графическим матроидом тогда и только тогда, когда базовый граф G графа M является планарным. Если G является планарным, двойственный матроид является графическим матроидом двойственного графа G. В частности, все двойственные графы для всех различных планарных вложений G имеют изоморфные графические матроиды. [45]
Для непланарных поверхностных вложений, в отличие от планарных дуальных, дуальный граф, как правило, не является алгебраическим дуальным графом первичного графа. А для непланарного графа G дуальный матроид графического матроида G сам по себе не является графическим матроидом. Однако он все еще является матроидом, чьи контуры соответствуют разрезам в G , и в этом смысле может рассматриваться как комбинаторно обобщенный алгебраический дуальный граф G. [46 ]
Двойственность между эйлеровыми и двудольными планарными графами может быть распространена на бинарные матроиды (которые включают графические матроиды, полученные из планарных графов): бинарный матроид является эйлеровым тогда и только тогда, когда его двойственный матроид является двудольным . [32]
Две дуальные концепции обхвата и связности ребер объединены в теории матроидов с помощью обхвата матроида : обхват графического матроида планарного графа такой же, как обхват графа, а обхват дуального матроида (графического матроида дуального графа) является связностью ребер графа. [19]
Наряду с использованием в теории графов, двойственность планарных графов имеет приложения в ряде других областей математических и вычислительных исследований.
В географических информационных системах сети потоков (например, сети, показывающие, как вода течет в системе ручьев и рек) являются дуальными ячеистым сетям, описывающим водоразделы . Эту дуальность можно объяснить, смоделировав сеть потоков как связующее дерево на сетке соответствующего масштаба и смоделировав водораздел как дополнительное связующее дерево хребтовых линий на дуальной сетке. [47]
В компьютерном зрении цифровые изображения разбиваются на маленькие квадратные пиксели , каждый из которых имеет свой цвет. Двойственный граф этого разбиения на квадраты имеет вершину на пиксель и ребро между парами пикселей, которые имеют общее ребро; это полезно для приложений, включая кластеризацию пикселей в связанные области схожих цветов. [48]
В вычислительной геометрии двойственность между диаграммами Вороного и триангуляциями Делоне подразумевает, что любой алгоритм построения диаграммы Вороного может быть немедленно преобразован в алгоритм для триангуляции Делоне, и наоборот. [49] Та же двойственность может быть использована и при генерации конечно-элементной сетки . Алгоритм Ллойда , метод, основанный на диаграммах Вороного для перемещения набора точек на поверхности в более равномерно расположенные положения, обычно используется как способ сглаживания конечно-элементной сетки, описанной двойственной триангуляцией Делоне. Этот метод улучшает сетку, делая ее треугольники более однородными по размеру и форме. [50]
При синтезе схем КМОП синтезируемая функция представляется в виде формулы в булевой алгебре . Затем эта формула переводится в два последовательно-параллельных мультиграфа . Эти графы можно интерпретировать как схемы цепей , в которых ребра графов представляют транзисторы , управляемые входами функции. Одна схема вычисляет саму функцию, а другая вычисляет ее дополнение. Одна из двух схем получается путем преобразования конъюнкций и дизъюнкций формулы в последовательные и параллельные композиции графов соответственно. Другая схема обращает эту конструкцию, преобразуя конъюнкции и дизъюнкции формулы в параллельные и последовательные композиции графов. [51] Эти две схемы, дополненные дополнительным ребром, соединяющим вход каждой схемы с ее выходом, являются планарными двойственными графами. [52]
Двойственность выпуклых многогранников была признана Иоганном Кеплером в его книге 1619 года Harmonices Mundi . [53] Узнаваемые планарные двойственные графы, вне контекста многогранников, появились еще в 1725 году в посмертно опубликованной работе Пьера Вариньона Nouvelle Méchanique ou Statique . Это было даже до работы Леонарда Эйлера 1736 года о семи мостах Кёнигсберга , которую часто считают первой работой по теории графов . Вариньон проанализировал силы, действующие на статические системы распорок , нарисовав график, двойственный распоркам, с длинами ребер, пропорциональными силам на распорках; этот двойственный граф является типом диаграммы Кремоны . [54] В связи с теоремой о четырех красках двойственные графы карт (подразделения плоскости на области) были упомянуты Альфредом Кемпе в 1879 году и распространены на карты на неплоских поверхностях Лотаром Хеффтером в 1891 году. [ 55] Двойственность как операция на абстрактных планарных графах была введена Хасслером Уитни в 1931 году. [56]
обратите внимание, что «мост» и «петля» — это двойственные понятия.
Является ли это старейшей иллюстрацией двойственности между планарными графами?.