双対グラフ

グラフ理論において平面グラフGの双対グラフ（そうたいグラフ、英: Dual graph）とはすべての頂点がGの各面に対応するグラフである。Gの双対はGの面どうしをつなぐ辺があるとき、それに対応する辺を持ち、辺の両側が同一面である場合、する。Gの各辺eは対応する双対辺をもち、この辺はGの面に対応する双対頂点どうしをつなぐ。双対は平面グラフ（すでに平面への埋めこまれているグラフ）についての性質である。平面的グラフ（平面へ埋め込みが可能だが定まっていないグラフ）については、グラフGの埋め込みの選択により、異なる双対グラフになりえる。 歴史的に、双対グラフの概念は正多面体を双対多面体の組とみなすことができるという発見から始まった。グラフの双対性は、双対多面体を位相幾何学的な視点から一般化したものである。またこれはの概念によって代数的に一般化される。双対グラフは有向グラフや平面以外の二次元曲面についても一般化できる。 「双対」という語のとおり、GがHの双対であるとき、HもGの双対となる。面と頂点という対応だけでなく、グラフに関する他の多くの特性および構造は、双対グラフについてその対応物をもつ。例えばサイクルはカットの双対であり、全域木は全域木の補集合の双対である。単純グラフ（または自己ループなし ）の双対は3辺連結グラフである。 グラフの双対性は、迷路や排水盆地の構造を説明するのに便利である。双対グラフは、コンピュータビジョン、計算幾何学、メッシュ生成、および集積回路の設計にも適用されてきた。 サイクルの平面埋め込みは、ジョルダン曲線の定理により、平面をサイクルの内側と外側の2つの面のみに分割する。しかしながら、これら2つの領域は、複数の異なる辺によって分離されているため、閉路グラフの双対は、2つの頂点（2つの面に対応する）が、複数のエッジに接続されたマルチグラフとなる。このようなグラフはと呼ばれる。 によると、すべての多面体グラフ（3次元凸ポリトープの頂点と辺によって形成されるグラフ）は平面で3頂点接続である必要があり、3頂点接続の平面グラフはすべて凸多面体に対応させることができる。すべての3次元凸多面体には双対多面体をもつ。双対多面体は、元の多面体のすべての面に頂点を持ち、2つの面が辺に共有されるとき、対応する2つの頂点の間に辺をもつ。2つの多面体が双対であるときはそのグラフもまた双対となる。たとえば、正多面体において、立方体と正八面体、正二十面体と正十二面体、正四面体とそれ自身は、互いに双対の関係にある。多面体の双対性は、より高次元のポリトープの双対性に拡張することもできるが、三次元の場合とは異なり、グラフ理論的な双対性との明確な関連性を持っていない。 平面グラフの双対グラフがそれ自身と同型のとき、このグラフ自己双対と呼ばれる。車輪グラフは、自己双対多面体（角錐）に対応する自己双対グラフである。また、対応する多面体が存在しないような自己双対グラフも存在する。は、「接着」と「爆発」と2つの操作を使うことで与えられた平面グラフを含む自己双対グラフを構築することが可能であることを述べている。例えば、図の自己双対グラフは四面体とその双対との接着として構成することができる。 オイラーの公式から、n個の頂点を持つすべての自己双対グラフは、厳密に2n − 2個の辺を持つ。すべての単純自己双対平面グラフは、次数3の頂点を少なくとも4つ含み、すべての自己双対グラフの埋め込みは少なくとも4つの三角形面を持つ。