双対グラフとは - わかりやすく解説 Weblio辞書

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

双対グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/10/29 04:05 UTC 版)

原文と比べた結果、この記事には多数の（または内容の大部分に影響ある）誤訳があることが判明しています。情報の利用には注意してください。 正確な表現に改訳できる方を求めています。 (2025年7月)

双対グラフ（そうついグラフ、英: Dual graph）とは、グラフ理論において、ある平面グラフ $G$

A dipole graph

A cycle graph

サイクルの平面埋め込みは、ジョルダン曲線の定理により、平面をサイクルの内側と外側の2つの面のみに分割する。しかしながら、これら2つの領域は、複数の異なる辺によって分離されているため、閉路グラフの双対は、2つの頂点（2つの面に対応する）が、複数のエッジに接続された多重グラフとなる。このようなグラフはダイポールグラフ（英語版）と呼ばれる^[1]。

シュタイニッツの定理（英語版）によると、すべての多面体グラフ（3次元凸多面体の頂点と辺によって形成されるグラフ）は平面で3頂点接続である必要があり、3頂点接続の平面グラフはすべて凸多面体に対応させることができる。すべての3次元凸多面体には双対多面体をもつ。双対多面体は、元の多面体のすべての面に頂点を持ち、2つの面が辺に共有されるとき、対応する2つの頂点の間に辺をもつ。2つの多面体が双対であるときはそのグラフもまた双対となる。たとえば、正多面体において、立方体と正八面体、正二十面体と正十二面体、正四面体とそれ自身は、互いに双対の関係にある^[2]。多面体の双対性はより高次元の多面体の双対性に拡張することもできる^[3]が、三次元の場合とは異なり、グラフ理論的な双対性との明確な関連性を持っていない。

平面グラフの双対グラフがそれ自身と同型のとき、このグラフ自己双対と呼ばれる。車輪グラフは、自己双対多面体（角錐）に対応する自己双対グラフである^[4]^[5]。また、対応する多面体が存在しないような自己双対グラフも存在する。Servatius & Christopher (1992)は、「接着」と「爆発」と2つの操作を使うことで与えられた平面グラフを含む自己双対グラフを構築することが可能であることを述べている。例えば、図の自己双対グラフは四面体とその双対との接着として構成することができる^[5]。

オイラーの公式から、 $n$ 個の頂点を持つすべての自己双対グラフは、厳密に $2 n - 2$ 個の辺を持つ^[6]。すべての単純自己双対平面グラフは、次数3の頂点を少なくとも4つ含み、すべての自己双対グラフの埋め込みは少なくとも4つの三角形面を持つ^[7]。

性質

グラフ理論における多くの自然で重要な概念は、双対グラフにおける他の同様に自然だが異なる概念に対応する。連結な平面グラフの双対の双対は元のグラフと同型であるため^[8]、これらの対応は互いに双方向である。平面グラフの概念 $X$ がその双対の概念 $Y$ に対応する場合、平面グラフの概念 $Y$ はその双対の概念 $X$ に対応する。

単純グラフと多重グラフ

閉路グラフの双対の例から明らかなように、単純グラフの双対は単純であるとは限らず、自己ループ（両方の端点が同じ頂点にある辺）や同じ2つの頂点を結ぶ複数の辺がある場合がある。カット-サイクルの双対性の特別な場合として、平面グラフの橋はその双対グラフの自己ループと一対一に対応している^[9]。同じ理由で、双対多重グラフ内の一対の平行な辺（つまり、長さ2のサイクル）は、主グラフ内の2辺のカットセット（削除されるとグラフが切断される一対の辺）に対応する。したがって、平面グラフ $G$

2つの赤いグラフは青いグラフの双対だが、同型ではない

双対グラフは特定の埋め込みに依存するので、平面グラフの双対グラフは、同じ平面グラフが同型でない異なる双対グラフを持つことができるという意味で一意ではない^[11]。図では、青いグラフは同型だが、その双対の赤いグラフはそうではない。下の赤いグラフはすべての次数が6未満であるのに対し、上のグラフは次数6の頂点を持つ。（青いグラフの外側の面に対応する）。

ハスラー・ホイットニーは、グラフが3頂点連結の場合、埋め込み、つまり双対グラフは一意であることを示した^[12]。Steinitzの定理により、これらのグラフはまさに多面体グラフ、すなわち凸多面体のグラフとなる。平面グラフは、その双対グラフが3頂点連結の場合に限り、3頂点連結になる。より一般的には、（単純な）平面グラフは、それが3頂点連結である場合に限り、一意な（鏡像を同一視した下で）埋め込み、したがって一意な双対を有する。完全2部グラフ $K 2,4$ のように、3頂点連結でない平面グラフの場合、埋め込みは一意ではないが、それらの埋め込みから得られる双対グラフはすべて同形となる。

異なる埋め込みは異なる双対グラフをもたらす可能性があるため、あるグラフが他のグラフの双対であるかどうかをテストする問題は自明でないアルゴリズム上の問題となる。2重連結グラフについてはSPQRツリーを用いることで、双対どうしの同値関係の正規の形式を構成することができる。しかし、2重連結ではない平面グラフの場合、そのような同値関係は求まらず、相互双対性をテストする問題はNP完全となる^[13]。

カットとサイクル

任意の連結グラフのカットセットは、グラフの頂点を2つの部分集合に分割したとき、この2つの部分集合どうしをつなぐ辺の集合を指す。グラフからカットセットを取り除くと、必然的にグラフは少なくとも2つの連結成分に分割される。最小カットセット（ボンドとも呼ばれる）は、それ自身がカットセットであり、かつその真の部分集合がカットセットにならないような辺集合である。連結グラフの最小カットセットは、必然的にそのグラフを2つのグラフに分割する^[14]。単純なサイクルは、連結部分グラフのうち、サイクルの各頂点が2つの辺を持つようなものである^[15]。

連結平面グラフ $G$ において、すべての単純サイクルは、 $G$ の双対の最小カットセットとみなすことができ、またその逆も成り立つ^[16]。これは、ジョルダン曲線定理の一種として見ることができる。単純な各サイクルは、 $G$ の面をサイクルの内側の面とサイクルの外側の面に分離し、サイクル辺の双対は内部から外部へと交差する辺となる^[17]。任意の平面グラフの内周（グラフがもつ最小サイズのサイクル）はその双対グラフの辺連結度（グラフがもつ最小サイズのカットセット）に等しい^[18]。

この二重性は個々のカットセットとサイクルから定義されたベクトル空間まで及ぶ。グラフのサイクル空間（英語版）とは、辺集合の部分集合であって、対応する部分グラフにおいてすべての頂点が偶数次数を持つようなものの族（family）である。サイクル空間は2要素有限体上のベクトル空間と見なすことができ、2組の辺の対称差はベクトル空間でのベクトル加算演算として機能する。同様の加算により、グラフのカット空間はすべてのカットセットの集合族として定義される。その場合、任意の平面グラフのサイクル空間とその双対グラフのカット空間は同型なベクトル空間となる^[19] したがって、平面グラフのランク（カットスペースの次元）は、その双対のサイクルランク（サイクル空間の次元）に等しく、その逆も成り立つ^[11]。グラフのサイクル基底はグラフに含まれる単純サイクルのうち、サイクル空間の基底を構成するようなものの集合である（全ての偶数次数の部分グラフがそれらのサイクルの対称差として一意に定まる）辺重み付き平面グラフ（2つのサイクルが同じ重みを持たないような十分に一般的な重みを持つ）の場合、グラフの最小重みサイクル基底は双対グラフのゴモリ・フー木と双対になる。最小重みサイクル基底の各サイクルには、ゴモリ・フー木のいずれかのカットの辺と双対となる辺の集合をもつ。もしサイクルどうしの重みが等しくなる場合、最小重みサイクルの基底は一意でなくなる可能性があるが、双対グラフのゴモリ・フー木が最小重みサイクルの基底に対応することに変わりはない^[19]。

有向平面グラフでは、単純な有向サイクルは有向カット（頂点を2つの部分集合に分割し、すべてのエッジが一方の部分集合から他方の部分集合に向かう）に対して双対となる。連結平面グラフの強い向き（グラフを強連結にするような辺の向き付け）は、その双対グラフにおける非巡回な向き付け（有向非巡回グラフを生成する向き付け）と双対の関係にある^[20]。

全域木

正十二面体の多面体グラフ（青）とその双対（赤）。双対グラフの頂点の一つは無限遠に存在する。

全域木は、グラフのすべての頂点を含む、連結された非巡回部分グラフとして定義できる。ここで、平面グラフ $G$ とその双対 $G*$ を考える。 $G$ の全域木 $S$ に対し、 $G$ のうち $S$ に含まれない辺集合を $~S$ とする。また、 $G*$ のうち $~S$ に対応する辺集合を $~S*$ とする。このとき $~S*$ は $G*$ の全域木となる。これは次のようにして分かる。 $S$ はサイクルを持たないため、 $G$ の各々の面を囲む辺のうち、少なくとも1つは $~S$ に含まれる。このことを双対の世界で言い直すと、 $G*$ の各頂点は必ず $~S*$ がもつ辺により連結されるということになる。ここでもし $~S*$ がサイクルを持つとすると、同様の議論によって、 $G$ の頂点のうち少なくとも1つが $S$ により連結されないことになる。しかし、これは $S$ が全域木であることと相容れないため、 $~S*$ はサイクルを持たない。よって、 $~S*$ は $G*$ の全ての頂点を連結し、サイクルを持たない。すなわち $~S*$ は $G*$ の全域木である。

このことから、平面グラフの全ての辺は全域木と、グラフの双対の全域木に対応する辺に分解することができる。

このタイプの分解の例は、単純な格子の辺の一部を壁としたようなタイプの迷路で見ることが出きる。このような迷路では壁とその間の空間は互いに入れ子になった木構造を形成する。この木構造は元の格子が形成するグラフの全域木とみなせる。このとき空間が構成する木構造は、元のグラフの双対の全域木となる^[21]。

このような2つの木構造への分解は、オイラーの公式の単純な証明を与える。木構造において、頂点の数 $V$ と辺の数 $E$ は、 $E = (V - 1)$ という関係をもつ。このことは次のようにして分かる。木構造は一つの頂点（このとき $E = 0$ , $V = 1$ ）から初めて、新しい頂点を既存の頂点に一つの辺で接続していくことで作ることができる。頂点を1つ追加するごとに辺も1つ追加されるため、常に $E=V-1$

有限点集合（黒点）のボロノイ図（赤）とドロネー三角分割（黒）

双対平面充填の概念は、平面を有限の領域に分割する場合にも適用することができる。これは平面グラフ双対性と非常に類似しているが、まったく同じではない。たとえば、ボロノイ図とドロネー三角分割は双対の関係にあるが、これらを平面グラフの双対として厳密に扱うには、点集合の凸包の外側（無限遠）に対応する頂点や面を考慮に入れる必要がある。

非平面埋め込み

K 7

はトーラス上のヒーウッドグラフの双対である。

K 6

はprojective plane上のピーターセングラフの双対である。

双対性の概念は、平面以外の二次元多様体上の埋め込みに拡張することができる。ほとんどの場合、埋め込みは各面が位相円板であるという性質を持つ場合に制限されている。この制約は、グラフが接続されているという平面グラフの要件を一般化したものである。この制約により、任意の埋め込みグラフの双対グラフは、同じ曲面に自然に埋め込まれることができる。例えば、完全グラフ $K 7$ の双対グラフはヒーウッドグラフである^[34]。

平面グラフも非平面埋め込みを持つことがあり、その場合の双対は平面双対とは異なる。たとえば、立方体の4つのペトリー多角形（立方体の2つの対向する頂点を削除することによって形成された六角形）は、トーラスに立方体を埋め込むときの六角形の面を形成する。この埋め込みの双対グラフは、二重エッジを持つ完全なグラフ $K 4$ を形成する4つの頂点を持つ。この双対グラフのトーラス埋め込みでは、各頂点が持つ6つの辺は、その頂点の周囲を巡回する順序で、他の3つの頂点を2回巡回する。平面内の状況とは対照的に、この立方体とその双対の埋め込みは一意ではない。立方体グラフの双対は、他のいくつかのトーラス埋め込みを持つ^[34]。

平面グラフの主グラフと双対グラフの性質の間の等価性の多くは、非平面埋め込みの場合に一般化できないか、追加の注意を必要とする。

表面埋め込みグラフに対するもう1つの操作はPetrie双対である。これは、埋め込みのPetrieポリゴンを新しい埋め込みの面として使用する。このグラフは通常の双対グラフとは異なり、元のグラフと同じ頂点を持つが、一般に異なる面に属する^[35]。面双対性とPetrie双対性は6つのウィルソン演算のうちの2つであり、これらの演算による群を生成する^[36]。

マトロイドと代数双対

この節の文章は日本語として不自然な表現、または文意がつかみづらい状態になっています。文意をわかりやすくするよう、修正が必要とされています。（2019年8月）

連結グラフ $G$ の代数的双対 $G^{*}$ は、 $G$ および $G^{*}$ が同じ辺の組を持っていて、 $G$ の全てのサイクルは、 $G^{*}$ のカットであり、 $G$ の全てのカットは $G^{*}$ のサイクルであるようなグラフである。すべての平面グラフは代数双対を持ち、これは一般的に一意ではない（特定の平面埋め込みによって定義される双対は、その埋め込みに対しては一意に定まるが、埋め込み自体が一意でない場合があるため、代数双対は一般に一意ではない）。Hassler WhitneyによるWhitneyの平面性基準で示されたように、この逆もまた真である^[37]。

連結グラフ

G

は代数双対をもつ場合に限り、平面グラフである。

同じ事実はマトロイドの理論でも表現できる。 $M$ がグラフ $G$ のグラフィックマトロイドである場合、 $G$ の代数双対 $G ★$ が存在し、かつ $G ★$ のグラフィックマトロイドが $M$ の双対マトロイドである場合にのみ、 $M$ の双対マトロイドはグラフィックマトロイドとなる。その場合、Whitneyの平面性基準は、グラフィックマトロイド $M$ 双対マトロイドは、それ自体が $M$ 基礎となるグラフ $G$ が平面である場合に限り、それ自体がグラフィックマトロイドであると述べると言い換えることができる。 $G$ が平面ならば、双対マトロイドは $G$ の双対グラフのグラフィックマトロイドである。特に、 $G$ すべての異なる平面埋め込みに対して、すべての双対グラフは同型グラフィックマトロイドを持つ^[38]。

非平面曲面埋め込みの場合、平面双対とは異なり、双対グラフは一般に主グラフの代数双対ではない。そして、非平面グラフ $G$ について、 $G$ のグラフィックマトロイドの双対マトロイドは、グラフィックマトロイドそのものではない。しかし、それは依然として、サイクルが $G$ のカットに対応するマトロイドであり、この意味では代数双対の一般化として考えることができる^[39]。

オイラー平面グラフと2部平面グラフの双対性は、二項マトロイド（平面グラフから派生したグラフィックマトロイドを含む）に拡張できる。二項マトロイドがオイラー的であるのは、その双対マトロイドが2部である場合に限る^[27]。ガースとエッジ接続性という2つの双対概念は、マトロイドガースによってマトロイド理論に統一される。平面グラフのグラフィックマトロイドのガースは、グラフのガースと同じである。また、双対マトロイドガース（双対のグラフィックマトロイド）はグラフのエッジ連結性である^[18]。

アプリケーション

グラフ理論におけるその使用と共に、平面グラフの双対性は、数学的および計算的研究の他のいくつかの分野において用途を有する。

地理情報システムでは、フローネットワーク（河川や河川のシステム内で水がどのように流れるかを示すネットワークなど）は、分水界を表すセルラーネットワークと双対である。この双対性は、適切な規模のグリッドグラフ上の全域木としてフローネットワークをモデル化することで、分水界を双対全域木としてモデル化することができることを意味する^[40]。

コンピュータビジョンでは、デジタル画像はそれぞれが独自の色を持っている小さな正方形のピクセルに分割される。この正方形への細分化の双対グラフは、ピクセルごとに頂点を持ち、辺を共有するピクセルのペアに対応する辺を持つ。これは、類似色が連結した領域へのピクセルのクラスタリングなどの用途に役立つ^[41]。

計算幾何学において、ボロノイ図とドローネ三角形分割との間の双対性は、ボロノイ図を構築するための任意のアルゴリズムが直ちにドロネー三角形分割のためのアルゴリズムに変換されうることを意味する^[42]。有限要素法におけるメッシュ生成でも同じ双対性を使うことができる。ボロノイ図の各面の点をより均等に離間した位置に移動させるロイドのアルゴリズム（英語版）は、ボロノイ図の双対であるドローネ三角形分割によって得られた有限要素メッシュを平滑化する方法として一般的に使用される。この方法は、三角形のサイズと形状をより均一にすることでメッシュを改善することができる^[43]。

CMOS回路の論理合成において、合成されるべき関数はブール代数における式として表される。それからこの式は2つの直並列多重グラフに変換される。これらのグラフは回路図として解釈することができ、グラフのエッジは関数への入力によってゲートされたトランジスタを表す。一方の回路は関数自体を計算し、もう一方の回路はその補数を計算する。2つの回路のうちの1つは、式の論理積と論理和をそれぞれグラフの直列と並列の合成に変換することによって導き出される。一方の回路はこの構造を逆にして、式の論理積と論理和をグラフの並列と直列の合成に変換する^[44]。これら2つの回路は、入力を出力に接続するエッジを追加すれば、互いに双対の関係にある^[45]。

歴史

凸多面体の双対性は、ヨハネス・ケプラーによって彼の1619年の本Harmonices Mundi で述べられている^[46]。多面体の文脈を離れた平面双対グラフは、1725年Pierre Varignonの死後公開された Nouvelle Méchanique ou Statique において現れている。これはレオンハルト・オイラーがケーニヒスベルクの7つの橋に関する論文を発表した1736年の前であり、しばしばグラフ理論に関する最初の論文とされる。Varignonは、ストラットの静的システムにかかる力を分析するため、ストラットの力に比例したエッジ長でストラットの双対グラフを描いた。この双対グラフはクレモナ図（英語版）の一種である^[47]。4色定理に関連して、地図の双対グラフは1879年にAlfred Kempeによって言及され、1891年 Lothar Heffter（ドイツ語版）により非平面上の地図に拡張された^[48]。抽象平面グラフ上の演算としての双対性は、1931年にHassler Whitneyによって導入された^[49]。