双対グラフ
 双対グラフ（そうついグラフ、英: Dual graph）とは、グラフ理論において平面グラフ G のすべての頂点がGの各面に対応するグラフである。G の双対はGの面どうしをつなぐ辺があるとき、それに対応する辺を持ち、辺の両側が同一面である場合、自己ループする。G の各辺 e は対応する双対辺をもち、この辺はGの面に対応する双対頂点どうしをつなぐ。双対は平面グラフ（すでに平面への埋めこまれているグラフ）についての性質である。平面的グラフ（平面へ埋め込みが可能だが定まっていないグラフ）については、グラフGの埋め込みの選択により、異なる双対グラフになりえる。 歴史的に、双対グラフの概念は正多面体を双対多面体の組とみなすことができるという発見から始まった。グラフの双対性は、双対多面体を位相幾何学的な視点から一般化したものである。またこれは双対マトロイドの概念によって代数的に一般化される。双対グラフは有向グラフや平面以外の二次元曲面についても一般化できる。 「双対」という語のとおり、GがHの双対であるとき、HもGの双対となる。面と頂点という対応だけでなく、グラフに関する他の多くの特性および構造は、双対グラフについてその対応物をもつ。例えば閉路はカットの双対であり、全域木は全域木の補集合の双対である。単純グラフ（平行エッジまたは自己ループなし ）の双対は3辺連結グラフである。 グラフの双対性は、迷路や排水盆地の構造を説明するのに便利である。双対グラフは、コンピュータビジョン、計算幾何学、メッシュ生成、および集積回路の設計にも適用されてきた。 サイクルの平面埋め込みは、ジョルダン曲線の定理により、平面をサイクルの内側と外側の2つの面のみに分割する。しかしながら、これら2つの領域は、複数の異なる辺によって分離されているため、閉路グラフの双対は、2つの頂点（2つの面に対応する）が、複数のエッジに接続された多重グラフとなる。このようなグラフはダイポールグラフと呼ばれる[1]。  シュタイニッツの定理によると、すべての多面体グラフ（3次元凸多面体の頂点と辺によって形成されるグラフ）は平面で3頂点接続である必要があり、3頂点接続の平面グラフはすべて凸多面体に対応させることができる。すべての3次元凸多面体には双対多面体をもつ。双対多面体は、元の多面体のすべての面に頂点を持ち、2つの面が辺に共有されるとき、対応する2つの頂点の間に辺をもつ。2つの多面体が双対であるときはそのグラフもまた双対となる。たとえば、正多面体において、立方体と正八面体、正二十面体と正十二面体、正四面体とそれ自身は、互いに双対の関係にある[2]。多面体の双対性はより高次元の多面体の双対性に拡張することもできる[3]が、三次元の場合とは異なり、グラフ理論的な双対性との明確な関連性を持っていない。  平面グラフの双対グラフがそれ自身と同型のとき、このグラフ自己双対と呼ばれる。車輪グラフは、自己双対多面体（角錐）に対応する自己双対グラフである[4][5]。また、対応する多面体が存在しないような自己双対グラフも存在する。Servatius & Christopher (1992)は、「接着」と「爆発」と2つの操作を使うことで与えられた平面グラフを含む自己双対グラフを構築することが可能であることを述べている。例えば、図の自己双対グラフは四面体とその双対との接着として構成することができる[5]。 オイラーの公式から、n個の頂点を持つすべての自己双対グラフは、厳密に2n − 2個の辺を持つ[6]。すべての単純自己双対平面グラフは、次数3の頂点を少なくとも4つ含み、すべての自己双対グラフの埋め込みは少なくとも4つの三角形面を持つ[7]。 性質グラフ理論における多くの自然で重要な概念は、双対グラフにおける他の同様に自然だが異なる概念に対応する。グラフの双対の双対は主グラフと同型であるため[8]、これらの対応は互いに双方向である。平面グラフの概念Xがその双対の概念Yに対応する場合、平面グラフの概念Yはその双対の概念Xに対応する。 単純グラフと多重グラフ閉路グラフの双対の例から明らかなように、単純グラフの双対は単純であるとは限らず、自己ループ（両方の端点が同じ頂点にある辺）や同じ2つの頂点を結ぶ複数の辺がある場合がる。カット-サイクルの双対性の特別な場合として、平面グラフの橋はその双対グラフの自己ループと一対一に対応している[9]。同じ理由で、双対多重グラフ内の一対の平行な辺（つまり、長さ2のサイクル）は、主グラフ内の2辺のカットセット（削除されるとグラフが切断される一対の辺）に対応する。したがって、平面グラフが単純である条件はその双対が1辺または2辺のカットセットを持たない場合に限る。つまり、3辺接続となる。単純平面グラフの双対が単純な場合、これは3辺連結単純グラフとなる[10]。このクラスのグラフは、3頂点結合単純平面グラフを含むが、必ずしもそうではなく、たとえば、自己双対グラフを示す図は3辺接続だが（したがって、その双対は単純である）が、3頂点接続ではない。 一意性 双対グラフは特定の埋め込みに依存するので、平面グラフの双対グラフは、同じ平面グラフが同型でない異なる双対グラフを持つことができるという意味で一意ではない[11]。図では、青いグラフは同型だが、その双対の赤いグラフはそうではない。下の赤いグラフはすべての次数が6未満であるのに対し、上のグラフは次数6の頂点を持つ。（青いグラフの外側の面に対応する）。 ハスラー・ホイットニーは、グラフが3頂点連結の場合、埋め込み、つまり双対グラフは一意であることを示した[12]。Steinitzの定理により、これらのグラフはまさに多面体グラフ、すなわち凸多面体のグラフとなる。平面グラフは、その双対グラフが3頂点接続の場合に限り、3頂点接続になる。より一般的には、平面グラフは、それが3頂点接続平面グラフの細分である場合に限り、固有の埋め込み、したがって固有の双対を有する。完全2部グラフK2,4ように、3頂点接続されていない平面グラフの場合、埋め込みは一意ではないが、埋め込みはすべて同形となる。この場合、すべての双対グラフは同形になる。 異なる埋め込みは異なる双対グラフをもたらす可能性があるため、あるグラフが他のグラフの双対であるかどうかをテストする問題は自明でないアルゴリズム上の問題となる。2重連結グラフについてはSPQRツリーを用いることで、双対どうしの同値関係の正規の形式を構成することができる。しかし、2重連結ではない平面グラフの場合、そのような同値関係は求まらず、相互双対性をテストする問題はNP完全となる[13]。 カットとサイクル任意の連結グラフのカットセットは、グラフの頂点を2つの部分集合に分割したとき、この2つの部分集合どうしをつなぐ辺の集合を指す。グラフからカットセットを取り除くと、必然的にグラフは少なくとも2つの連結成分に分割される。最小カットセット（ボンドとも呼ばれる）は、カットセットのすべての部分集合がそれ自体カットではないという特性を持つカットセットである。連結グラフの最小カットセットは、必然的にそのグラフを2つのグラフに分割する[14]。単純なサイクルは、連結部分グラフのうち、サイクルの各頂点が2つの辺を持つようなものである[15]。 接続平面グラフGはGのすべての単純サイクルは、Gの双対の最小カットセットとみなすことができ、またその逆も成り立つ[16]。これは、ジョルダン曲線定理の一種として見ることができる。単純な各サイクルは、Gの面をサイクルの内側の面とサイクルの外側の面に分離し、サイクル辺の双対は内部から外部へと交差する辺となる[17]。任意の平面グラフの内周（グラフがもつ最小サイズのサイクル）はその双対グラフの辺連結度（グラフがもつ最小サイズのカットセット）に等しい[18]。 この二重性は個々のカットセットとサイクルから定義されたベクトル空間まで及ぶ。グラフのサイクル空間とは の集合であるすべての頂点が偶数の次数を持っているような部分グラフ（オイラーグラフ）の集合である。サイクル空間は2要素有限体上のベクトル空間と見なすことができ、2組の辺の対称差はベクトル空間でのベクトル加算演算として機能する。同様の加算により、グラフのカット空間はすべてのカットセットの集合族として定義される。その場合、任意の平面グラフのサイクル空間とその双対グラフのカット空間は同型なベクトル空間となる[19] したがって、平面グラフのランク（カットスペースの次元）は、その双対のサイクルランク（サイクル空間の次元）に等しく、その逆も成り立つ[11]。グラフのサイクル基底はグラフに含まれる単純サイクルのうち、サイクル空間の基底を構成するようなものの集合である（全ての偶数次数の部分グラフがそれらのサイクルの対称差として一意に定まる）辺重み付き平面グラフ（2つのサイクルが同じ重みを持たないような十分に一般的な重みを持つ）の場合、グラフの最小重みサイクル基底は双対グラフのゴモリ・フー木と双対になる。最小重みサイクル基底の各サイクルには、ゴモリ・フー木のいずれかのカットの辺と双対となる辺の集合をもつ。もしサイクルどうしの重みが等しくなる場合、最小重みサイクルの基底は一意でなくなる可能性があるが、双対グラフのゴモリ・フー木が最小重みサイクルの基底に対応することに変わりはない[19]。 有向平面グラフでは、単純な有向サイクルは有向カット（頂点を2つの部分集合に分割し、すべてのエッジが一方の部分集合から他方の部分集合に向かう）に対して双対となる。強く方向付けられた平面グラフ（含まれる無向グラフの全ての辺が1つのサイクルに属しているグラフ）は、辺が1つのサイクルに属していない有向非巡回グラフに対して双対となる。別の言い方をすると、連結平面グラフの強い向き（強い連結グラフとなるグラフのエッジへの方向の割り当て）は、非巡回方向（有向非巡回グラフを生成する方向の割り当て）に対して双対となる[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であり、その後E,Vが同数ずつ増えていく。このことから上式が成り立つことがわかる。 いま、グラフGについてその全域木Sが与えられたとする。Sの辺の数をESとすると、ES = (V − 1) が成り立つ。また~S*の辺の数をE~S*とすると、~S*はG* の全域木であるため、G*の頂点の数、すなわちGの面の数Fについて同様な関係 E~S* = (F − 1)が成り立つ。Sの辺の数と~Sの辺の数を足すとGの辺の数に等しく、また~Sの各辺は~S*の各辺に一対一に対応するため、
が成り立つ。これはオイラーの公式に他ならない。Sommerville (Duncan Sommerville) によると、オイラーの公式のこの証明はカール・フォン・シュタウトの Geometrie der Lage（Nürnberg, 1847）による[22]。 非平面表面埋め込みでは、全域木と相補的な双対辺は元のグラフの全域木とはならない。そのかわり、これらは元のグラフの双対の全域木と少数の余分な辺を合わせた集合となる。このとき、余分な辺の数は、グラフが埋め込まれている曲面の種数によって決まる。この余分な辺は全域木に含まれる経路と合わせて用いることで、曲面の基本群を生成できる[23]。 他の性質すべての平面グラフに有効な頂点や面の数え上げ公式は、双対性によって、頂点と面の役割が入れ替わった同等の式に変換することができる。自己双対的であるオイラーの公式はその一例である。また別の例ではHararyによる握手補題がある。これによると、平面グラフの各頂点の次数の合計は、グラフの辺の数の2倍に等しい。この補題の双対形式は、平面グラフの各面を囲む辺の数を全ての面について合計した数は、グラフの辺の数の2倍に等しいことを示す[24]。 平面グラフの中間グラフは元のグラフの双対の中間グラフと同型となる。また、2つの平面グラフは、それらが互いに双対である場合にのみ同形の中間グラフを持つことができる[25]。 4つ以上の頂点を持つ平面グラフは、その双対グラフが3頂点接続と3正規の両方である場合に限り、最大（平面性を保ちながらそれ以上の辺を追加することができない）となる[26]。 連結平面グラフは、その双対グラフが2部グラフである場合に限り、オイラー路（すべての頂点の次数が偶数）となる[27]。平面グラフGにおけるハミルトン路は、双対グラフの頂点を2つの部分集合（サイクルの内側と外側）に分割することに対応し、その誘導部分グラフは両方とも木となる。特に、3次2部多面体グラフのハミルトン性に関するBarnette予想は、すべてのオイラー路最大平面グラフを2つの誘導木に分割できるという推測と同等である[28]。 平面グラフGがTutte多項式TG(x,y)を持つ場合、その双対グラフのTutte多項式はxとy交換することによって得られる。このため、Tutte多項式がGの特定の構造に関する情報を持つ場合、Tutte多項式の引数を交換すると、Gの双対についてそれに対応する情報が得られる。例えば、Gの強い配向の数はTG(0,2)あり、非閉路配向の数はTG(2,0) である[29]。ブリッジレス平面グラフの場合、k色のグラフの色付けは剰余kのゼロフローに対応する。4色定理は、すべてのブリッジレス平面グラフの双対は全て剰余4のゼロフローがあることと同等である。k色付けの数はTutte多項式の値TG(1 − k,0)によって数えられ、その双対である剰余kのゼロフローの数はTG(0,1 − k)によって数えられる[30]。 st-平面グラフとは双極配向をもつグラフである。双極配向とは、一対のソースとシンクによる、循環なしの方向付けで、ソースとシンクが同一の面に属しているようなものである。このようなグラフは、ソースとシンクを結ぶもう一つの辺を加えることで強い結合をもつグラフにすることができる。この補完されたグラフの双対はそれ自身、別のst-平面グラフの補完となる。 派生概念有向グラフ有向平面グラフの双対グラフは、各双対辺を対応する主辺から時計回りに90°回転させることによって、同様に指向させることができる[31]。ただしこれは厳密に言えば双対ではない。なぜならば、グラフGから出発し、双対を二回とったとき、G自体に戻らず、Gの転置グラフ（Gの全てのエッジを反転させたグラフ）と同型なグラフになるからである。この定義の双対では、双対を4回取ると元のグラフに戻る。 弱双対平面グラフの弱双対は、双対グラフの部分グラフで、その頂点は主グラフの面に対応する。平面グラフは、その弱い双対が森である場合に限り、外平面グラフになる。任意の平面グラフGについて、Gの外面に一つの新しい頂点vを追加し、vとGの外面に属する全ての点を辺で結んだグラフをG+とするとき、GはG+ の双対の弱双対である[32]。 無限グラフと平面充填双対性の概念は、有限グラフの場合と同様に、平面に埋め込まれた無限グラフも適用することができる。しかしながら、開放領域の一部ではなく、グラフの辺または頂点の一部でもない点のような位相的な複雑さを避けるために注意が必要である。全ての面が、グラフのサイクルで囲まれている場合、無限平面グラフは平面充填とみなすことができる。平面双対性は、双対平面充填 、つまり各タイルの中心に頂点を置き、隣接するタイルの中心を結ぶことによって形成される平面充填の概念を生み出す[33]。  双対平面充填の概念は、平面を有限の領域に分割する場合にも適用することができる。これは平面グラフ双対性と非常に類似しているが、まったく同じではない。たとえば、ボロノイ図とドロネー三角分割は双対の関係にあるが、平面グラフとしての双対として考えるためには、無限遠に位置する頂点である。 非平面埋め込み 双対性の概念は、平面以外の二次元多様体上の埋め込みに拡張することができる。ほとんどの場合、埋め込みは各面が位相円板であるという性質を持つ場合に制限されている。この制約は、グラフが接続されているという平面グラフの要件を一般化したものである。この制約により、任意の埋め込みグラフは、同じ曲面に自然に埋め込まれることができる。例えば、完全グラフK7の双対グラフはヒーウッドグラフである[34]。 平面グラフも非平面埋め込みを持つことがあり、その場合の双対は平面双対とは異なる。たとえば、立方体の4つのペトリー多角形（立方体の2つの対向する頂点を削除することによって形成された六角形）は、トーラスに立方体を埋め込むときの六角形の面を形成する。この埋め込みの双対グラフは、二重エッジを持つ完全なグラフK4を形成する4つの頂点を持つ。この双対グラフのトーラス埋め込みでは、各頂点が持つ6つの辺は、その頂点の周囲を巡回する順序で、他の3つの頂点を2回巡回する。平面内の状況とは対照的に、この立方体とその双対の埋め込みは一意ではない。立方体グラフの双対は、他のいくつかのトーラス埋め込みを持つ[34]。 平面グラフの主グラフと双対グラフの性質の間の等価性の多くは、非平面埋め込みの場合に一般化できないか、追加の注意を必要とする。 表面埋め込みグラフに対するもう1つの操作はPetrie双対である 。これは、埋め込みのPetrieポリゴンを新しい埋め込みの面として使用する。このグラフは通常の双対グラフとは異なり、元のグラフと同じ頂点を持つが、一般に異なる面に属する[35]。面双対性とPetrie双対性は6つのウィルソン演算のうちの2つであり、これらの演算による群を生成する[36]。 マトロイドと代数双対
連結グラフGの代数的双対G★は、GおよびG★が同じ辺の組を持っていて、Gの全てのサイクル Gは、G★のカットであり、Gの全てのカットはG★のサイクルであるようなグラフである。すべての平面グラフは代数双対を持ち、これは一般的に一意ではない（平面埋め込みによって定義される双対は一意となる）。Hassler Whitneyによる Whitneyの平面性の基準で解決されたように、この逆もまた真である[37]。
同じ事実はマトロイドの理論でも表現できる。MがグラフGのグラフィックマトロイドである場合、グラフG★もしGの代数デュアルでありG★のグラフィックマトロイドがある場合にのみ、デュアルマトロイド 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]。 脚注
|
Portal di Ensiklopedia Dunia
