右|サムネイル|赤グラフと青グラフは互いに双対の関係にある。 双対グラフ（そうついグラフ、）とは、グラフ理論において、ある平面グラフ の面に対応する頂点を持ち、 の辺に対応する辺を持つグラフ のことである。
より具体的には、 が平面に埋め込まれているとき、その双対グラフ は以下のように構築される。 の各面 （外界（無限面）を含む）の内部に、 の頂点 を配置する。 の各辺 が二つの面 と に隣接している（ と を隔てている）場合、 において、 と に対応する頂点 と との間に辺 （ の双対辺）を引く。 の辺 が両側で同じ面 に接している（すなわち がである）場合、 においては に対応する頂点 に自己ループ（） を追加する。 この定義から、 の各辺 は、双対グラフ の辺 と一対一に対応する。
双対は平面グラフ（すでに平面への埋めこまれているグラフ）についての性質である。平面的グラフ（平面へ埋め込みが可能だが、特定の埋め込み方が定まっていないグラフ）については、グラフ の埋め込み方（どの面を外界とするかなど）の選択により、異なる（同型でない）双対グラフが導かれうる。
歴史的に、双対グラフの概念は正多面体を双対多面体の組とみなすことができるという発見から始まった。グラフの双対性は、双対多面体を位相幾何学的な視点から一般化したものである。またこれはの概念によって代数的に一般化される。双対グラフは有向グラフや平面以外の二次元曲面についても一般化できる。
「双対」という語のとおり、連結な平面グラフの双対をとするとき、の双対 は元のと同型である。面と頂点という対応だけでなく、グラフに関する他の多くの特性および構造は、双対グラフについてそれに対応する概念を持つ。例えば閉路はカットに、全域木は双対グラフにおける全域木の補集合（の辺に対応する双対辺）に対応する。また、平面グラフの双対グラフが単純グラフ（自己ループや平行辺を持たないグラフ）であるのは、元のグラフが3辺連結である場合に限る。
グラフの双対性は、迷路や排水盆地の構造を説明するのに便利である。双対グラフは、コンピュータビジョン、計算幾何学、メッシュ生成、および集積回路の設計にも適用されてきた。 サイクルの平面埋め込みは、ジョルダン曲線の定理により、平面をサイクルの内側と外側の2つの面のみに分割する。しかしながら、これら2つの領域は、複数の異なる辺によって分離されているため、閉路グラフの双対は、2つの頂点（2つの面に対応する）が、複数のエッジに接続された多重グラフとなる。このようなグラフはと呼ばれる。 サムネイル| 立方体と正八面体は双対の関係にある によると、すべての多面体グラフ（3次元凸多面体の頂点と辺によって形成されるグラフ）は平面で3頂点接続である必要があり、3頂点接続の平面グラフはすべて凸多面体に対応させることができる。すべての3次元凸多面体には双対多面体をもつ。双対多面体は、元の多面体のすべての面に頂点を持ち、2つの面が辺に共有されるとき、対応する2つの頂点の間に辺をもつ。2つの多面体が双対であるときはそのグラフもまた双対となる。たとえば、正多面体において、立方体と正八面体、正二十面体と正十二面体、正四面体とそれ自身は、互いに双対の関係にある。多面体の双対性はより高次元の多面体の双対性に拡張することもできるが、三次元の場合とは異なり、グラフ理論的な双対性との明確な関連性を持っていない。 サムネイル| 自己双対グラフ 平面グラフの双対グラフがそれ自身と同型のとき、このグラフ自己双対と呼ばれる。車輪グラフは、自己双対多面体（角錐）に対応する自己双対グラフである。また、対応する多面体が存在しないような自己双対グラフも存在する。は、「接着」と「爆発」と2つの操作を使うことで与えられた平面グラフを含む自己双対グラフを構築することが可能であることを述べている。例えば、図の自己双対グラフは四面体とその双対との接着として構成することができる。
オイラーの公式から、個の頂点を持つすべての自己双対グラフは、厳密に個の辺を持つ。すべての単純自己双対平面グラフは、次数3の頂点を少なくとも4つ含み、すべての自己双対グラフの埋め込みは少なくとも4つの三角形面を持つSee the proof of Theorem 5 in 。
性質 グラフ理論における多くの自然で重要な概念は、双対グラフにおける他の同様に自然だが異なる概念に対応する。連結な平面グラフの双対の双対は元のグラフと同型であるため、これらの対応は互いに双方向である。平面グラフの概念がその双対の概念に対応する場合、平面グラフの概念はその双対の概念に対応する。
単純グラフと多重グラフ 閉路グラフの双対の例から明らかなように、単純グラフの双対は単純であるとは限らず、自己ループ（両方の端点が同じ頂点にある辺）や同じ2つの頂点を結ぶ複数の辺がある場合がある。カット-サイクルの双対性の特別な場合として、平面グラフの橋はその双対グラフの自己ループと一対一に対応している。同じ理由で、双対多重グラフ内の一対の平行な辺（つまり、長さ2のサイクル）は、主グラフ内の2辺のカットセット（削除されるとグラフが切断される一対の辺）に対応する。したがって、平面グラフ の双対グラフ が単純であるための必要十分条件は、 が（橋や2辺カットセットを持たない）3辺連結であることである。単純平面グラフ の双対 も単純である場合、 と は共に3辺連結な単純グラフである。このクラスのグラフは、3頂点結合単純平面グラフを含むが、必ずしもそうではなく、たとえば、自己双対グラフを示す図は3辺接続だが（したがって、その双対は単純である）が、3頂点接続ではない。
一意性 サムネイル| 2つの赤いグラフは青いグラフの双対だが、同型ではない 双対グラフは特定の埋め込みに依存するので、平面グラフの双対グラフは、同じ平面グラフが同型でない異なる双対グラフを持つことができるという意味で一意ではない。図では、青いグラフは同型だが、その双対の赤いグラフはそうではない。下の赤いグラフはすべての次数が6未満であるのに対し、上のグラフは次数6の頂点を持つ。（青いグラフの外側の面に対応する）。
ハスラー・ホイットニーは、グラフが3頂点連結の場合、埋め込み、つまり双対グラフは一意であることを示した。Steinitzの定理により、これらのグラフはまさに多面体グラフ、すなわち凸多面体のグラフとなる。平面グラフは、その双対グラフが3頂点連結の場合に限り、3頂点連結になる。より一般的には、（単純な）平面グラフは、それが3頂点連結である場合に限り、一意な（鏡像を同一視した下で）埋め込み、したがって一意な双対を有する。完全2部グラフのように、3頂点連結でない平面グラフの場合、埋め込みは一意ではないが、それらの埋め込みから得られる双対グラフはすべて同形となる。
異なる埋め込みは異なる双対グラフをもたらす可能性があるため、あるグラフが他のグラフの双対であるかどうかをテストする問題は自明でないアルゴリズム上の問題となる。2重連結グラフについてはSPQRツリーを用いることで、双対どうしの同値関係の正規の形式を構成することができる。しかし、2重連結ではない平面グラフの場合、そのような同値関係は求まらず、相互双対性をテストする問題はNP完全となる。
カットとサイクル 任意の連結グラフのカットセットは、グラフの頂点を2つの部分集合に分割したとき、この2つの部分集合どうしをつなぐ辺の集合を指す。グラフからカットセットを取り除くと、必然的にグラフは少なくとも2つの連結成分に分割される。最小カットセット（ボンドとも呼ばれる）は、それ自身がカットセットであり、かつその真の部分集合がカットセットにならないような辺集合である。連結グラフの最小カットセットは、必然的にそのグラフを2つのグラフに分割する。単純なサイクルは、連結部分グラフのうち、サイクルの各頂点が2つの辺を持つようなものである。
連結平面グラフ において、すべての単純サイクルは、 の双対の最小カットセットとみなすことができ、またその逆も成り立つ。これは、ジョルダン曲線定理の一種として見ることができる。単純な各サイクルは、の面をサイクルの内側の面とサイクルの外側の面に分離し、サイクル辺の双対は内部から外部へと交差する辺となる。任意の平面グラフの内周（グラフがもつ最小サイズのサイクル）はその双対グラフの辺連結度（グラフがもつ最小サイズのカットセット）に等しい。
この二重性は個々のカットセットとサイクルから定義されたベクトル空間まで及ぶ。グラフのとは、辺集合の部分集合であって、対応する部分グラフにおいてすべての頂点が偶数次数を持つようなものの族（family）である。サイクル空間は2要素有限体上のベクトル空間と見なすことができ、2組の辺の対称差はベクトル空間でのベクトル加算演算として機能する。同様の加算により、グラフのカット空間はすべてのカットセットの集合族として定義される。その場合、任意の平面グラフのサイクル空間とその双対グラフのカット空間は同型なベクトル空間となる したがって、平面グラフのランク（カットスペースの次元）は、その双対のサイクルランク（サイクル空間の次元）に等しく、その逆も成り立つ。グラフのサイクル基底はグラフに含まれる単純サイクルのうち、サイクル空間の基底を構成するようなものの集合である（全ての偶数次数の部分グラフがそれらのサイクルの対称差として一意に定まる）辺重み付き平面グラフ（2つのサイクルが同じ重みを持たないような十分に一般的な重みを持つ）の場合、グラフの最小重みサイクル基底は双対グラフのゴモリ・フー木と双対になる。最小重みサイクル基底の各サイクルには、ゴモリ・フー木のいずれかのカットの辺と双対となる辺の集合をもつ。もしサイクルどうしの重みが等しくなる場合、最小重みサイクルの基底は一意でなくなる可能性があるが、双対グラフのゴモリ・フー木が最小重みサイクルの基底に対応することに変わりはない。
有向平面グラフでは、単純な有向サイクルは有向カット（頂点を2つの部分集合に分割し、すべてのエッジが一方の部分集合から他方の部分集合に向かう）に対して双対となる。連結平面グラフの強い向き（グラフを強連結にするような辺の向き付け）は、その双対グラフにおける非巡回な向き付け（有向非巡回グラフを生成する向き付け）と双対の関係にある。
全域木 サムネイル| 正十二面体の多面体グラフ（青）とその双対（赤）。双対グラフの頂点の一つは無限遠に存在する。 サムネイル|正十二面体の多面体グラフの全域木（青）とその双対（赤）。グラフの全域木とその双対が持つ関係からオイラーの多面体定理が導かれる。
全域木は、グラフのすべての頂点を含む、連結された非巡回部分グラフとして定義できる。ここで、平面グラフとその双対を考える。の全域木に対し、のうち に含まれない辺集合をとする。また、のうちに対応する辺集合をとする。このときはの全域木となる。これは次のようにして分かる。はサイクルを持たないため、の各々の面を囲む辺のうち、少なくとも1つはに含まれる。このことを双対の世界で言い直すと、の各頂点は必ずがもつ辺により連結されるということになる。ここでもしがサイクルを持つとすると、同様の議論によって、の頂点のうち少なくとも1つがにより連結されないことになる。しかし、これはが全域木であることと相容れないため、はサイクルを持たない。よって、はの全ての頂点を連結し、サイクルを持たない。すなわちはの全域木である。
このことから、平面グラフの全ての辺は全域木と、グラフの双対の全域木に対応する辺に分解することができる。
このタイプの分解の例は、単純な格子の辺の一部を壁としたようなタイプの迷路で見ることが出きる。このような迷路では壁とその間の空間は互いに入れ子になった木構造を形成する。この木構造は元の格子が形成するグラフの全域木とみなせる。このとき空間が構成する木構造は、元のグラフの双対の全域木となる. See in particular pp. 138–139。
このような2つの木構造への分解は、オイラーの公式の単純な証明を与える。木構造において、頂点の数と辺の数は、 という関係をもつ。このことは次のようにして分かる。木構造は一つの頂点（このとき ,）から初めて、新しい頂点を既存の頂点に一つの辺で接続していくことで作ることができる。頂点を1つ追加するごとに辺も1つ追加されるため、常に という関係が保たれる。
いま、グラフについてその全域木が与えられたとする。の辺の数をとすると、 が成り立つ。またの辺の数をとすると、は の全域木であるため、の頂点の数、すなわちの面の数について同様な関係 が成り立つ。の辺の数との辺の数を足すとの辺の数に等しく、またの各辺はの各辺に一対一に対応するため、
が成り立つ。これはオイラーの公式に他ならない。Sommerville によると、オイラーの公式のこの証明はカール・フォン・シュタウトの Geometrie der Lage（Nürnberg, 1847）による。
非平面表面埋め込みでは、全域木と相補的な双対辺は元のグラフの全域木とはならない。そのかわり、これらは元のグラフの双対の全域木と少数の余分な辺を合わせた集合となる。このとき、余分な辺の数は、グラフが埋め込まれている曲面の種数によって決まる。この余分な辺は全域木に含まれる経路と合わせて用いることで、曲面の基本群を生成できる。
他の性質 すべての平面グラフに有効な頂点や面の数え上げ公式は、双対性によって、頂点と面の役割が入れ替わった同等の式に変換することができる。自己双対的であるオイラーの公式はその一例である。また別の例ではHararyによる握手補題がある。これによると、平面グラフの各頂点の次数の合計は、グラフの辺の数の2倍に等しい。この補題の双対形式は、平面グラフの各面を囲む辺の数を全ての面について合計した数は、グラフの辺の数の2倍に等しいことを示す。
平面グラフの中間グラフは元のグラフの双対の中間グラフと同型となる。また、2つの平面グラフは、それらが互いに双対である場合にのみ同形の中間グラフを持つことができる。
4つ以上の頂点を持つ平面グラフは、その双対グラフが3頂点連結かつ3正則（立方体グラフ）の両方である場合に限り、最大（平面性を保ちながらそれ以上の辺を追加することができない）となる。
連結平面グラフは、その双対グラフが2部グラフである場合に限り、オイラー路（すべての頂点の次数が偶数）となる。平面グラフにおけるハミルトン閉路は、双対グラフの頂点を2つの部分集合（サイクルの内側と外側）に分割することに対応し、その誘導部分グラフは両方とも木となる。特に、3次2部多面体グラフのハミルトン性に関するBarnette予想は、すべてのオイラー路最大平面グラフを2つの誘導木に分割できるという推測と同等である。
平面グラフがTutte多項式を持つ場合、その双対グラフのTutte多項式はと交換することによって得られる。このため、Tutte多項式がの特定の構造に関する情報を持つ場合、Tutte多項式の引数を交換すると、の双対についてそれに対応する情報が得られる。例えば、の強い配向の数はあり、非閉路配向の数は である。ブリッジレス平面グラフの場合、色のグラフの色付けは剰余kのゼロフローに対応する。4色定理は、すべてのブリッジレス平面グラフの双対は全て剰余4のゼロフローがあることと同等である。色付けの数はTutte多項式の値によって数えられ、その双対である剰余kのゼロフローの数はによって数えられる。
st-平面グラフとは双極配向をもつグラフである。双極配向とは、一対のソースとシンクによる、循環なしの方向付けで、ソースとシンクが同一の面に属しているようなものである。このようなグラフは、ソースとシンクを結ぶもう一つの辺を加えることで強い結合をもつグラフにすることができる。この補完されたグラフの双対はそれ自身、別のst-平面グラフの補完となる。
派生概念 有向グラフ 有向平面グラフの双対グラフは、各双対辺を対応する主辺から時計回りに90°回転させることによって、同様に指向させることができる。ただしこれは厳密に言えば双対ではない。なぜならば、グラフから出発し、双対を二回とったとき、自体に戻らず、の転置グラフ（の全てのエッジを反転させたグラフ）と同型なグラフになるからである。この定義の双対では、双対を4回取ると元のグラフに戻る。
弱双対 平面グラフの弱双対は、双対グラフの部分グラフで、その頂点は主グラフの有界な面に対応する。平面グラフは、その弱い双対が森である場合に限り、外平面グラフになる。任意の平面グラフについて、の外面に一つの新しい頂点を追加し、との外面に属する全ての点を辺で結んだグラフをとするとき、は の双対の弱双対である。
無限グラフと平面充填 双対性の概念は、有限グラフの場合と同様に、平面に埋め込まれた無限グラフも適用することができる。しかしながら、開放領域の一部ではなく、グラフの辺または頂点の一部でもない点のような位相的な複雑さを避けるために注意が必要である。全ての面が、グラフのサイクルで囲まれている場合、無限平面グラフは平面充填とみなすことができる。平面双対性は、双対平面充填、つまり各タイルの中心に頂点を置き、隣接するタイルの中心を結ぶことによって形成される平面充填の概念を生み出す。 サムネイル| 有限点集合（黒点）のボロノイ図（赤）とドロネー三角分割（黒） 双対平面充填の概念は、平面を有限の領域に分割する場合にも適用することができる。これは平面グラフ双対性と非常に類似しているが、まったく同じではない。たとえば、ボロノイ図とドロネー三角分割は双対の関係にあるが、これらを平面グラフの双対として厳密に扱うには、点集合の凸包の外側（無限遠）に対応する頂点や面を考慮に入れる必要がある。
非平面埋め込み
双対性の概念は、平面以外の二次元多様体上の埋め込みに拡張することができる。ほとんどの場合、埋め込みは各面が位相円板であるという性質を持つ場合に制限されている。この制約は、グラフが接続されているという平面グラフの要件を一般化したものである。この制約により、任意の埋め込みグラフの双対グラフは、同じ曲面に自然に埋め込まれることができる。例えば、完全グラフの双対グラフはヒーウッドグラフである。
平面グラフも非平面埋め込みを持つことがあり、その場合の双対は平面双対とは異なる。たとえば、立方体の4つのペトリー多角形（立方体の2つの対向する頂点を削除することによって形成された六角形）は、トーラスに立方体を埋め込むときの六角形の面を形成する。この埋め込みの双対グラフは、二重エッジを持つ完全なグラフを形成する4つの頂点を持つ。この双対グラフのトーラス埋め込みでは、各頂点が持つ6つの辺は、その頂点の周囲を巡回する順序で、他の3つの頂点を2回巡回する。平面内の状況とは対照的に、この立方体とその双対の埋め込みは一意ではない。立方体グラフの双対は、他のいくつかのトーラス埋め込みを持つ。
平面グラフの主グラフと双対グラフの性質の間の等価性の多くは、非平面埋め込みの場合に一般化できないか、追加の注意を必要とする。
表面埋め込みグラフに対するもう1つの操作はPetrie双対である 。これは、埋め込みのPetrieポリゴンを新しい埋め込みの面として使用する。このグラフは通常の双対グラフとは異なり、元のグラフと同じ頂点を持つが、一般に異なる面に属する。面双対性とPetrie双対性は6つのウィルソン演算のうちの2つであり、これらの演算による群を生成する。
マトロイドと代数双対
連結グラフ の代数的双対 は、 および が同じ辺の組を持っていて、 の全てのサイクルは、 のカットであり、 の全てのカットは のサイクルであるようなグラフである。すべての平面グラフは代数双対を持ち、これは一般的に一意ではない（特定の平面埋め込みによって定義される双対は、その埋め込みに対しては一意に定まるが、埋め込み自体が一意でない場合があるため、代数双対は一般に一意ではない）。Hassler WhitneyによるWhitneyの平面性基準で示されたように、この逆もまた真である。
連結グラフは代数双対をもつ場合に限り、平面グラフである。
同じ事実はマトロイドの理論でも表現できる。がグラフのグラフィックマトロイドである場合、の代数双対が存在し、かつのグラフィックマトロイドがの双対マトロイドである場合にのみ、の双対マトロイドはグラフィックマトロイドとなる。その場合、Whitneyの平面性基準は、グラフィックマトロイド 双対マトロイドは、それ自体が基礎となるグラフが平面である場合に限り、それ自体がグラフィックマトロイドであると述べると言い換えることができる。が平面ならば、双対マトロイドはの双対グラフのグラフィックマトロイドである。特に、すべての異なる平面埋め込みに対して、すべての双対グラフは同型グラフィックマトロイドを持つ。
非平面曲面埋め込みの場合、平面双対とは異なり、双対グラフは一般に主グラフの代数双対ではない。そして、非平面グラフについて、のグラフィックマトロイドの双対マトロイドは、グラフィックマトロイドそのものではない。しかし、それは依然として、サイクルがのカットに対応するマトロイドであり、この意味では代数双対の一般化として考えることができる。
オイラー平面グラフと2部平面グラフの双対性は、二項マトロイド（平面グラフから派生したグラフィックマトロイドを含む）に拡張できる。二項マトロイドがオイラー的であるのは、その双対マトロイドが2部である場合に限る。ガースとエッジ接続性という2つの双対概念は、マトロイドガースによってマトロイド理論に統一される。平面グラフのグラフィックマトロイドのガースは、グラフのガースと同じである。また、双対マトロイドガース（双対のグラフィックマトロイド）はグラフのエッジ連結性である。
アプリケーション グラフ理論におけるその使用と共に、平面グラフの双対性は、数学的および計算的研究の他のいくつかの分野において用途を有する。
地理情報システムでは 、フローネットワーク（河川や河川のシステム内で水がどのように流れるかを示すネットワークなど）は、分水界を表すセルラーネットワークと双対である。この双対性は、適切な規模のグリッドグラフ上の全域木としてフローネットワークをモデル化することで、分水界を双対全域木としてモデル化することができることを意味する。
コンピュータビジョンでは 、デジタル画像はそれぞれが独自の色を持っている小さな正方形のピクセルに分割される。この正方形への細分化の双対グラフは、ピクセルごとに頂点を持ち、辺を共有するピクセルのペアに対応する辺を持つ。これは、類似色が連結した領域へのピクセルのクラスタリングなどの用途に役立つ。
計算幾何学において、ボロノイ図とドローネ三角形分割との間の双対性は、ボロノイ図を構築するための任意のアルゴリズムが直ちにドロネー三角形分割のためのアルゴリズムに変換されうることを意味する。有限要素法におけるメッシュ生成でも同じ双対性を使うことができる。ボロノイ図の各面の点をより均等に離間した位置に移動させるは、ボロノイ図の双対であるドローネ三角形分割によって得られた有限要素メッシュを平滑化する方法として一般的に使用される。この方法は、三角形のサイズと形状をより均一にすることでメッシュを改善することができる。
CMOS回路の論理合成において、合成されるべき関数はブール代数における式として表される。それからこの式は2つの直並列多重グラフに変換される。これらのグラフは回路図として解釈することができ、グラフのエッジは関数への入力によってゲートされたトランジスタを表す。一方の回路は関数自体を計算し、もう一方の回路はその補数を計算する。2つの回路のうちの1つは、式の論理積と論理和をそれぞれグラフの直列と並列の合成に変換することによって導き出される。一方の回路はこの構造を逆にして、式の論理積と論理和をグラフの並列と直列の合成に変換する。これら2つの回路は、入力を出力に接続するエッジを追加すれば、互いに双対の関係にある。
歴史 凸多面体の双対性は、ヨハネス・ケプラーによって彼の1619年の本Harmonices Mundi で述べられている。多面体の文脈を離れた平面双対グラフは、1725年Pierre Varignonの死後公開された Nouvelle Méchanique ou Statique において現れている。これはレオンハルト・オイラーがケーニヒスベルクの7つの橋に関する論文を発表した1736年の前であり、しばしばグラフ理論に関する最初の論文とされる 。Varignonは、ストラットの静的システムにかかる力を分析するため、ストラットの力に比例したエッジ長でストラットの双対グラフを描いた。この双対グラフはの一種である. See also 。4色定理に関連して、地図の双対グラフは1879年にAlfred Kempeによって言及され、1891年 により非平面上の地図に拡張された。抽象平面グラフ上の演算としての双対性は、1931年にHassler Whitneyによって導入された。
脚注