デュアルグラフ

数学の分野であるグラフ理論において、平面グラフGの双対グラフは、 Gの各面を頂点とするグラフである。双対グラフは、辺によって互いに隔てられているG内の面のペアごとに辺を持ち、辺の両側に同じ面が現れる場合は自己ループとなる。したがって、 Gの各辺eには対応する双対辺があり、その端点はeの両側の面に対応する双対頂点である 。双対の定義はグラフGの埋め込みの選択に依存するため、これは平面グラフ (埋め込まれる可能性はあるが、埋め込みがまだわかっていないグラフ) ではなく、平面グラフ(すでに平面に埋め込まれているグラフ) の特性である。一般に平面グラフでは、グラフの平面埋め込みの選択に応じて、複数の双対グラフが存在する可能性がある。

歴史的に、グラフの双対性として最初に認識されたのは、プラトンの立体を双対多面体のペアに関連付けたものでした。グラフの双対性は、双対多面体と双対テッセレーションという幾何学的概念を位相的に一般化したものであって、今度は双対マトロイドの概念によって組み合わせ的に一般化されています。平面グラフの双対性のバリエーションには、有向グラフの双対性のバージョンや、非平面の 2 次元表面に埋め込まれたグラフの双対性などがあります。

これらの双対グラフの概念は、グラフの エッジと頂点の双対グラフや線グラフという別の概念と混同しないでください。

双対グラフという用語が使用されるのは、双対グラフの性質が対称的であるためです。つまり、H が連結グラフ Gの双対である場合、GはHの双対です。グラフGの双対について議論する場合、グラフG自体は「主グラフ」と呼ばれることがあります。他の多くのグラフの性質と構造は、双対の他の自然な性質と構造に変換できます。たとえば、サイクルはカットと双対であり、全域木は全域木の補グラフと双対であり、単純グラフ (平行辺や自己ループがない) は3 辺連結グラフと双対です。

グラフの双対性は、迷路や流域の構造を説明するのに役立ちます。また、双対グラフは、コンピューター ビジョン、計算幾何学、メッシュ生成、集積回路の設計にも応用されています。

サイクルグラフの唯一の平面埋め込みは、ジョルダン曲線定理によって、平面をサイクルの内側と外側の2つの領域にのみ分割します。ただし、nサイクルでは、これらの2つの領域はnつの異なるエッジによって互いに分離されています。したがって、 nサイクルのデュアルグラフは、 2つの頂点（領域に対してデュアル）を持ち、 nデュアルエッジで互いに接続されたマルチグラフです。このようなグラフは、多重エッジ、リンク、または双極子グラフと呼ばれることがあります。逆に、 nエッジの双極子グラフの双対はnサイクルです。 ^[1]

シュタイニッツの定理によれば、すべての多面体グラフ(3 次元の凸多面体の頂点と辺によって形成されるグラフ) は平面かつ3 頂点連結でなければならず、3 頂点連結の平面グラフはすべて、このようにして凸多面体から派生します。すべての 3 次元の凸多面体には 双対多面体があります。双対多面体は、元の多面体のすべての面に対して頂点を持ち、対応する 2 つの面が辺を共有する場合は常に 2 つの双対頂点が隣接します。2 つの多面体が双対である場合は、常にそのグラフも双対です。たとえば、プラトンの立体は双対のペアになっており、正八面体は立方体と双対、正十二面体は正二十面体と双対、正四面体はそれ自身と双対です。^{[2]多面体の双対性は高次元}多面体の双対性にも拡張できるが、^[3]この幾何学的双対性の拡張はグラフ理論的双対性と明確なつながりを持っていない。

平面グラフは、その双対グラフと同型である場合に自己双対であると言われる。ホイールグラフは、自己双対多面体（ピラミッド）から派生した自己双対グラフの無限族を提供する。^{[4] [5]}しかし、示されているような多面体ではない自己双対グラフも存在する。ServatiusとChristopher（1992）は、与えられた平面グラフを含む自己双対グラフを構築するために使用できる2つの操作、接着と爆発について説明している。たとえば、示されている自己双対グラフは、四面体とその双対の接着として構築することができる。^[5]

オイラーの公式から、 n頂点を持つすべての自己双対グラフには、ちょうど2 n − 2個の辺があることがわかります。^[6]すべての単純自己双対平面グラフには、少なくとも4つの次数3の頂点が含まれ、すべての自己双対埋め込みには少なくとも4つの三角形の面があります。^[7]

グラフ理論における多くの自然で重要な概念は、双対グラフ内の同様に自然だが別の概念に対応しています。連結平面グラフの双対の双対は主グラフと同型であるため、 ^[8]これらの各ペアリングは双方向です。つまり、平面グラフの概念Xが双対グラフの概念Yに対応する場合、平面グラフの概念Yは双対の 概念Xに対応します。

単純グラフの双対は単純である必要はありません。自己ループ（両端点が同じ頂点にある辺）や、同じ 2 つの頂点を接続する複数の辺を持つ場合があります。これは、双極子マルチグラフがサイクルグラフと双対である例ですでに明らかになっています。以下で説明するカットサイクル双対性の特殊なケースとして、平面グラフGのブリッジは、双対グラフの自己ループと 1 対 1 で対応しています。^[9]同じ理由で、双対マルチグラフ（つまり、長さ 2 のサイクル）内の平行な辺のペアは、主グラフの 2 辺のカットセット（削除するとグラフが切断される辺のペア）に対応します。したがって、平面グラフが単純であるのは、その双対に 1 辺または 2 辺のカットセットがない場合、つまり3 辺接続されている場合に限ります。双対が単純な単純平面グラフは、まさに 3 辺接続されている単純平面グラフです。^{[10]このクラスのグラフには、} 3頂点連結の単純平面グラフのクラスが含まれますが、同じではありません。たとえば、自己双対グラフを示す図は3辺連結（したがってその双対は単純）ですが、3頂点連結ではありません。

双対グラフは特定の埋め込みに依存するため、平面グラフの双対グラフは、同じ平面グラフが非同型双対グラフを持つことができるという意味で一意ではありません。^[11]図では、青いグラフは同型ですが、その双対である赤いグラフは同型ではありません。上部の赤い双対には次数 6 の頂点 (青いグラフの外面に対応) がありますが、下部の赤いグラフでは次数はすべて 6 未満です。

ハスラー・ホイットニーは、グラフが3頂点連結であれば埋め込み、したがって双対グラフは一意であることを示した。^[12]シュタイニッツの定理によれば、これらのグラフはまさに多面体グラフ、つまり凸多面体のグラフである。平面グラフが3頂点連結であるためには、その双対グラフが3頂点連結である必要がある。さらに、平面2頂点連結グラフは、3頂点連結平面グラフ（3頂点連結平面グラフの辺の一部をパスに置き換えて形成されたグラフ）の細分である場合に限り、一意の埋め込み、したがって一意の双対を持つことができる。 ^[13]完全2部グラフ K _2,4 など、3頂点連結ではない一部の平面グラフでは、埋め込みは一意ではないが、すべての埋め込みは同型である。これが起こると、それに応じて、すべての双対グラフは同型になります。

異なる埋め込みは異なる双対グラフにつながる可能性があるため、あるグラフが別のグラフの双対であるかどうかをテストすることは（それらの埋め込みを事前に知らなくても）、重要なアルゴリズムの問​​題です。2 重連結グラフの場合、グラフのSPQR 木を使用して、相互双対を共有する同値関係の標準形を構築することで、多項式時間で解決できます。たとえば、図の 2 つの赤いグラフはこの関係によれば同値です。ただし、2 重連結でない平面グラフの場合、この関係は同値関係ではなく、相互双対性をテストする問題はNP 完全です。^[14]

任意の連結グラフのカットセットは、頂点を 2 つのサブセットに分割して定義されるエッジのサブセットです。このサブセットには、分割の各側に 1 つのエンドポイントがあるエッジが含まれます。カットセットのエッジを削除すると、グラフは必然的に少なくとも 2 つの連結コンポーネントに分割されます。最小カットセット (ボンドとも呼ばれる) は、カットセットのすべての適切なサブセットがそれ自体カットではないという特性を持つカットセットです。連結グラフの最小カットセットは、必然的にグラフを 2 つのコンポーネントに分割し、各コンポーネントに 1 つのエンドポイントがあるエッジの集合で構成されます。^[15]単純サイクルは、サイクルの各頂点がサイクルの 2 つのエッジに接続されている連結サブグラフです。^[16]

連結平面グラフGでは、Gのすべての単純サイクルはGの双対の最小カットセットに対応し、その逆も同様である。^{[17]これは、}ジョルダン曲線定理の一種と見ることができる。つまり、各単純サイクルはGの面をサイクルの内部の面とサイクルの外部の面に分割し、サイクルの辺の双対は内部から外部に渡る辺とまったく同じである。^{[18]平面グラフの}内周（最小サイクルのサイズ）は、その双対グラフの辺の接続性（最小カットセットのサイズ）に等しい。^[19]

この双対性は、個々のカットセットとサイクルから、それらから定義されるベクトル空間にまで及ぶ。グラフのサイクル空間は、各頂点で偶数次数を持つすべてのサブグラフの族として定義される。これは、2 要素の有限体上のベクトル空間と見なすことができ、2 セットのエッジの対称差は、ベクトル空間でのベクトルの加算演算として機能します。同様に、グラフのカット空間は、すべてのカットセットの族として定義され、ベクトルの加算は同じ方法で定義されます。すると、任意の平面グラフのサイクル空間とその双対グラフのカット空間は、ベクトル空間として同型になります。^[20]したがって、平面グラフのランク(カット空間の次元) は、その双対の円分数(サイクル空間の次元) に等しく、その逆も同様です。^[11]グラフのサイクル基底は、サイクル空間の基底を形成する単純なサイクルの集合です(すべての偶数次数サブグラフは、これらのサイクルのいくつかの対称差として正確に 1 つの方法で形成できます)。辺重み付き平面グラフ（十分に一般的な重みを持ち、2 つのサイクルが同じ重みを持たないグラフ）の場合、グラフの最小重みサイクル基底は、双対グラフのGomory-Hu 木と双対です。これは、グラフ内の各頂点のペアを分離する最小カットを含むネストされたカットのコレクションです。最小重みサイクル基底の各サイクルには、Gomory-Hu 木のカットの 1 つと双対であるエッジのセットがあります。サイクルの重みが同点の場合、最小重みサイクル基底は一意ではない可能性がありますが、この場合も、双対グラフの Gomory-Hu 木がグラフの最小重みサイクル基底の 1 つに対応していることは変わりません。^[20]

有向平面グラフでは、単純な有向サイクルは有向カット（すべての辺が一方のサブセットから他方のサブセットへ一方向に進むように頂点を 2 つのサブセットに分割する）と双対である。強く有向な平面グラフ（基になる無向グラフが接続され、すべての辺がサイクルに属するグラフ）は、どの辺もサイクルに属していない有向非巡回グラフと双対である。言い換えれば、接続された平面グラフの強い配向（強く接続されたグラフになるグラフの辺への方向の割り当て）は、非巡回配向（有向非巡回グラフを生成する方向の割り当て）と双対である。^[21]同様に、ダイジョイン（各有向カットからの辺を含む辺の集合）は、フィードバックアーク集合（各サイクルからの辺を含む辺の集合）と双対である。^[22]

スパニング ツリーは、グラフのすべての頂点と一緒になって、接続された非巡回サブグラフを形成するエッジの集合として定義できます。ただし、カット サイクル双対性により、平面グラフGのエッジの集合Sが非巡回 (サイクルがない) である場合、Sと双対なエッジの集合にはカットがないため、双対エッジの補集合 ( Sにないエッジの双対) は接続されたサブグラフを形成することになります。対称的に、Sが接続されている場合、 Sの補集合と双対なエッジは非巡回サブグラフを形成します。したがって、 S が両方の特性 (接続されていて非巡回である) を持つ場合、双対グラフの補集合についても同じことが当てはまります。つまり、Gの各スパニング ツリーは双対グラフのスパニング ツリーと補完的であり、その逆も同様です。したがって、任意の平面グラフとその双対の辺は、（複数の異なる方法で）2つの全域木に分割することができ、1つは主全域木、もう1つは双対であり、これらはグラフのすべての頂点と面に広がりますが、互いに交差することはありません。特に、Gの最小全域木は、双対グラフの最大全域木と補完的です。^{[23]しかし、これは}最短経路木には近似的にも機能しません。グラフ内の全域木と双対グラフ内の補完全域木のすべてのペアについて、2つの木のうち少なくとも1つの距離がそのグラフ内の距離よりも大幅に長い平面グラフが存在します。^[24]

この種の相互嵌合木への分解の例は、入口が 1 つで壁の切断されたコンポーネントがない単純なタイプの迷路で見ることができます。この場合、迷路の壁と壁の間のスペースの両方が数学的な木の形をとります。迷路の自由空間が単純なセル (グリッドの正方形など) に分割されている場合、このセルのシステムは平面グラフの埋め込みとして見ることができ、壁のツリー構造がグラフの全域木を形成し、自由空間のツリー構造がデュアル グラフの全域木を形成します。^{[25]同様の相互嵌合木のペアは、}流域内の小川や川のツリー型パターンや、小川を隔てる尾根線のデュアル ツリー型パターンにも見られます。 ^[26]

辺とその双対を2つの木に分割すると、V頂点、E辺、F面を持つ平面グラフに対してオイラーの公式 V − E + F = 2が簡単に証明される。任意の全域木とその相補的な双対全域木は、辺をそれぞれV − 1辺とF − 1辺の2つの部分集合に分割し、2つの部分集合のサイズを加算すると次の式が得られる。

E = ( V − 1) + ( F − 1)です。

これを変形するとオイラーの公式となる。ダンカン・ソマービルによれば、このオイラーの公式の証明はKGCフォン・シュタウトの 『地の幾何学』（ニュルンベルク、1847年）によるものである。 ^[27]

非平面表面埋め込みでは、全域木に相補的な双対辺の集合は、全域木ではない。その代わり、この辺の集合は、グラフが埋め込まれている表面の種数によって数が決まる少数の追加辺と、双対全域木の和集合である。追加辺は、全域木内のパスと組み合わせて、表面の基本群を生成するために使用できる。 ^[28]

頂点と面を含むあらゆる平面グラフに有効な数え上げ式は、平面双対性によって、頂点と面の役割が入れ替わった同等の式に変換できる。自己双対であるオイラーの公式はその一例である。ハラリーが示した別の式は、握手補題であり、これによれば、任意のグラフの頂点の次数の合計は辺の数の2倍に等しい。この補題の双対形式では、平面グラフでは、グラフの面の辺の数の合計は辺の数の2倍に等しいと述べている。^[29]

平面グラフの中間グラフは、その双対グラフの中間グラフと同型である。2つの平面グラフは、互いに双対である場合にのみ、同型中間グラフを持つことができる。^[30]

4つ以上の頂点を持つ平面グラフが最大（平面性を保ちながらそれ以上の辺を追加できない）となるのは、その双対グラフが3頂点連結かつ3正則である場合に限ります。^[31]

連結平面グラフがオイラーグラフ（各頂点の次数が偶数）であるためには、その双対グラフが二部グラフでなければならない。^[32]平面グラフGのハミルトン閉路は、双対グラフの頂点を 2 つの部分集合（閉路の内部と外部）に分割し、その誘導部分グラフが両方とも木となることに対応する。特に、立方二部多面体グラフのハミルトン性に関するバーネットの予想は、すべてのオイラー極大平面グラフを 2 つの誘導木に分割できるという予想と同等である。^[33]

平面グラフG がTutte 多項式 T _G ( x , y )を持つ場合、その双対グラフの Tutte 多項式はxとy を入れ替えることで得られます。このため、 Tutte 多項式の特定の値がG内の特定のタイプの構造に関する情報を提供する場合、 Tutte 多項式の引数を入れ替えると、双対構造の対応する情報が得られます。たとえば、強い配向の数はT _G (0,2)であり、非巡回配向の数はT _G (2,0)です。^[34]ブリッジのない平面グラフの場合、 k色のグラフカラーリングは、双対グラフ上のk を法とした nowhere-zero フローに対応します。たとえば、4 色定理(すべての平面グラフに 4 色カラーリングが存在する) は、すべてのブリッジのない平面グラフの双対には nowhere-zero 4 フローが存在すると表現できます。k色付けの数は（簡単に計算できる因数まで）トゥッテ多項式値T _G (1 − k ,0)で数えられ、同様にゼロでないkフローの数はT _G (0,1 − k )で数えられる。^[35]

st平面グラフは、連結された平面グラフであり、そのグラフの双極配向、つまり単一のソースと単一のシンクを持つ非循環的な配向であり、その両方が互いに同じ面上にある必要がある。このようなグラフは、シンクからソースに戻る外面を通るもう 1 つのエッジを追加することで、強く連結されたグラフにすることができます。この拡張された平面グラフの双対は、それ自体が別のst平面グラフの拡張です。^[36]

有向平面グラフでは、各双対辺を対応する主辺から時計回りに 90° 回転させることで、双対グラフも有向にすることができます。^[36]厳密に言えば、この構築は有向平面グラフの双対性ではありません。グラフGから始めて双対を 2 回取ってもG自体には戻らず、代わりにGの転置グラフ、つまりGのすべての辺を反転して形成されたグラフと同型のグラフが構築されるからです。双対を 4 回取ると、元のグラフに戻ります。

平面グラフの弱い双対は、頂点が主グラフの境界面に対応する双対グラフのサブグラフである。平面グラフが外平面グラフであるためには、その弱い双対がフォレストでなければならない。任意の平面グラフGについて、G ^{+ を}、 Gの境界のない面に1 つの新しい頂点v を追加し、v を外面の各頂点に接続して（外面の境界に頂点が複数回現れる場合は、複数回）形成される平面多重グラフとすると、G はG ⁺の（平面）双対の弱い双対となる。^[37]

双対性の概念は、有限グラフと同様に、平面に埋め込まれた無限グラフにも適用されます。ただし、平面上の点がグラフから分離した開領域の一部でもグラフの辺や頂点の一部でもないなどの位相的な複雑さを避けるように注意する必要があります。すべての面がグラフのサイクルによって囲まれた境界領域である場合、無限平面グラフの埋め込みは、平面のモザイク化、つまり、内部 (埋め込みの面) が分離した開ディスクである閉じたディスク (モザイクのタイル) で平面を覆うものとしても見ることができます。平面の双対性から、各タイルの中心に頂点を配置し、隣接するタイルの中心を接続することによって形成されるモザイク化である、デュアルモザイク化の概念が生まれます。[ ^38]

双対テッセレーションの概念は、平面を有限個の領域に分割する場合にも適用できます。この場合、双対テッセレーションは平面グラフの双対性と密接に関連していますが、まったく同じではありません。たとえば、有限の点サイトの集合のボロノイ図は、平面をポリゴンに分割したもので、ポリゴン内では 1 つのサイトが他のサイトよりも近くなります。入力の凸包上のサイトは、境界のないボロノイ多角形を生じ、その 2 つの辺は有限の線分ではなく無限の放射線です。この図の双対は、入力のドロネー三角形分割です。これは、2 つのサイトを含み他のサイトを含まない円が存在する場合は常に、2 つのサイトをエッジで接続する平面グラフです。入力の凸包のエッジはドロネー三角形分割のエッジでもありますが、ボロノイ図の線分ではなく放射線に対応します。ボロノイ図とドロネー三角形分割の間のこの双対性は、2つの方法のいずれかで有限グラフ間の双対性に変換できます。ボロノイ図に無限遠の人工頂点を追加して、そのすべての光線のもう一方の端点として機能するようにするか、^[39]ボロノイ図の境界部分をドロネー三角形分割の弱い双対として扱うかです。ボロノイ図とドロネー三角形分割は双対ですが、平面への埋め込みには、双対の辺の交差以外にも追加の交差がある場合があります。ドロネー三角形の各頂点は、ボロノイ図の対応する面内に配置されます。ボロノイ図の各頂点は、ドロネー三角形分割の対応する三角形の外心に配置されますが、この点は三角形の外側にある場合があります。

双対性の概念は、平面以外の2 次元多様体上のグラフ埋め込みに拡張できます。定義は同じです。多様体内のグラフの補集合の各連結成分には双対頂点があり、各グラフの辺には、辺の両側にある 2 つの双対頂点を連結する双対辺があります。この概念のほとんどの応用では、各面が位相ディスクであるという特性を持つ埋め込みに制限されます。この制約は、平面グラフの要件である連結グラフを一般化します。この制約により、任意の表面埋め込みグラフの双対は同じ表面上に自然な埋め込みを持ち、双対の双対は元のグラフと同型で同型に埋め込まれます。たとえば、完全グラフK ₇はトーラスグラフです。平面ではありませんが、埋め込みの各面が三角形であるトーラスに埋め込むことができます。この埋め込みの双対グラフはHeawood グラフです。 ^[40]

同じ概念は非有向面にも同様に当てはまります。例えば、K _{6 は}10個の三角形の面を持つ射影平面に半二十面体として埋め込むことができ、その双対は半十二面体として埋め込まれたピーターセングラフです。^[41]

平面グラフであっても、非平面埋め込みを持つことができ、それらの埋め込みから派生した双対は平面双対とは異なる。例えば、立方体の 4 つのペトリ多角形(立方体の 2 つの反対の頂点を削除して形成される六角形) は、立方体をトーラスに埋め込んだときの六角形の面を形成する。この埋め込みの双対グラフには、2 重の辺を持つ完全グラフK ₄を形成する 4 つの頂点がある。この双対グラフのトーラス埋め込みでは、各頂点に接する 6 つの辺は、その頂点の周りを巡回する順序で、他の 3 つの頂点を 2 回循環する。平面内の状況とは対照的に、立方体とその双対のこの埋め込みは一意ではなく、立方体グラフには、異なる双対を持つ他のいくつかのトーラス埋め込みがある。^[40]

平面グラフの主グラフ特性と双対グラフ特性間の同等性の多くは、非平面双対グラフには一般化できないか、一般化には追加の注意が必要です。

表面埋め込みグラフに対する別の演算はペトリー双対であり、これは埋め込みのペトリー多角形を新しい埋め込みの面として使用する。通常の双対グラフとは異なり、元のグラフと同じ頂点を持ちますが、通常は異なる表面上にあります。^{[42]表面双対性とペトリー双対性は、6つの}ウィルソン演算の うちの2つであり、一緒にこれらの演算のグループを生成します。^[43]

連結グラフGの代数的双対とは、GとG ^*が同じ辺の集合を持ち、Gの任意のサイクルがG ^*のカットであり、Gの任意のカットが G *のサイクルであるようなグラフG ^*のことである。すべての平面グラフには代数的双対があり、それは一般に一意ではない（平面埋め込みによって定義される任意の双対でよい）。逆は実際には真であり、これはHassler WhitneyのWhitney の平面性基準で解決されている。^[44]

連結グラフG は、代数的双対を持つ場合にのみ平面グラフとなります。

同じ事実はマトロイドの理論でも表現できる。M がグラフGのグラフィックマトロイドである場合、グラフG ^*がGの代数的双対であるためには、G ^*のグラフィックマトロイドがMの双対マトロイドでなければならない。すると、ホイットニーの平面性基準は、グラフィックマトロイドMの双対マトロイド自体がグラフィックマトロイドであるためには、Mの基礎となるグラフGが平面である必要がある、と言い換えることができる。Gが平面である場合、双対マトロイドはGの双対グラフのグラフィックマトロイドである。特に、 Gの異なる平面埋め込みすべてについて、すべての双対グラフは同型のグラフィックマトロイドを持つ。^[45]

非平面表面埋め込みの場合、平面双対とは異なり、双対グラフは一般に主グラフの代数双対ではない。また、非平面グラフGの場合、 Gのグラフィックマトロイドの双対マトロイド自体はグラフィックマトロイドではない。しかし、それは回路がGのカットに対応するマトロイドであり、この意味ではGの組み合わせ的に一般化された代数双対と考えることができる 。^[46]

オイラーグラフと二部平面グラフの双対性は、バイナリマトロイド（平面グラフから派生したグラフィックマトロイドを含む）に拡張することができます。バイナリマトロイドは、その双対マトロイドが二部である場合にのみオイラーグラフとなります。^[32]

内周と辺の接続性という2つの双対概念は、マトロイド理論ではマトロイド内周によって統一されている。平面グラフのグラフィックマトロイドの内周はグラフの内周と同じであり、双対マトロイド（双対グラフのグラフィックマトロイド）の内周はグラフの辺の接続性である。^[19]

平面グラフの双対性は、グラフ理論での使用に加えて、数学や計算研究の他のいくつかの分野にも応用されています。

地理情報システムでは、フローネットワーク（河川や小川のシステムで水がどのように流れるかを示すネットワークなど）は、分水嶺を記述するセルネットワークと双対である。この双対性は、フローネットワークを適切なスケールのグリッドグラフ上のスパニングツリーとしてモデル化し、分水嶺をデュアルグリッドグラフ上の尾根線の補完的なスパニングツリーとしてモデル化することで説明できる。^[47]

コンピュータビジョンでは、デジタル画像は小さな正方形のピクセルに分割され、各ピクセルは独自の色を持っています。この正方形への分割の双対グラフには、ピクセルごとに頂点があり、エッジを共有するピクセルのペアの間にはエッジがあります。これは、ピクセルを同様の色の接続された領域にクラスタリングするなどのアプリケーションに役立ちます。^[48]

計算幾何学では、ボロノイ図とドロネー三角形分割の双対性は、ボロノイ図を作成するためのアルゴリズムはどれもドロネー三角形分割のアルゴリズムに即座に変換できることを意味し、その逆も同様である。 ^{[49]同じ双対性は}有限要素 メッシュ生成にも使用できる。ボロノイ図に基づいて表面上の点の集合をより均等な間隔の位置に移動する方法であるロイドのアルゴリズムは、双対ドロネー三角形分割によって記述される有限要素メッシュを滑らかにする方法としてよく使用される。 この方法は、三角形のサイズと形状をより均一にすることでメッシュを改善する。^[50]

CMOS回路の合成では、合成する関数はブール代数の式として表現される。次に、この式は2つの直列並列マルチグラフに変換される。これらのグラフは、グラフのエッジが関数への入力によってゲートされるトランジスタを表す回路図として解釈できる。1つの回路は関数自体を計算し、もう1つはその補関数を計算する。2つの回路のうち1つは、式の連言と選言をそれぞれグラフの直列および並列構成に変換することによって得られる。もう1つの回路はこの構成を逆にし、式の連言と選言をグラフの並列および直列構成に変換する。^[51]これらの2つの回路は、各回路の入力をその出力に接続する追加のエッジによって拡張され、平面デュアルグラフである。^[52]

凸多面体の双対性は、ヨハネス・ケプラーが1619年の著書『世界の調和』で認識した。^[53] 多面体の文脈以外で認識可能な平面双対グラフは、早くも1725年にピエール・ヴァリニョンの死後に出版された著書『新機械論または静力学』に登場している。これは、グラフ理論に関する最初の著作とされることが多いレオンハルト・オイラーの1736年の『ケーニヒスベルクの七つの橋』よりも前のことである。ヴァリニョンは、支柱の静的システムにかかる力を、支柱の双対グラフを描くことで解析した。このグラフでは、辺の長さが支柱にかかる力に比例している。この双対グラフはクレモナ図の一種である。^[54]四色定理に関連して、地図の双対グラフ（平面を領域に分割したもの）は1879年にアルフレッド・ケンペによって言及され、 1891年にローター・ヘフター [de]によって非平面上の地図に拡張された。^[55]抽象平面グラフ上の演算としての双対性は1931年にハスラー・ホイットニーによって導入された。 ^[56]

• ワイスタイン、エリック W.、「デュアルグラフ」、MathWorld