About: 双対グラフ

グラフ理論において平面グラフGの双対グラフ（そうたいグラフ、英: Dual graph）とはすべての頂点がGの各面に対応するグラフである。Gの双対はGの面どうしをつなぐ辺があるとき、それに対応する辺を持ち、辺の両側が同一面である場合、する。Gの各辺eは対応する双対辺をもち、この辺はGの面に対応する双対頂点どうしをつなぐ。双対は平面グラフ（すでに平面への埋めこまれているグラフ）についての性質である。平面的グラフ（平面へ埋め込みが可能だが定まっていないグラフ）については、グラフGの埋め込みの選択により、異なる双対グラフになりえる。 歴史的に、双対グラフの概念は正多面体を双対多面体の組とみなすことができるという発見から始まった。グラフの双対性は、双対多面体を位相幾何学的な視点から一般化したものである。またこれはの概念によって代数的に一般化される。双対グラフは有向グラフや平面以外の二次元曲面についても一般化できる。 「双対」という語のとおり、GがHの双対であるとき、HもGの双対となる。面と頂点という対応だけでなく、グラフに関する他の多くの特性および構造は、双対グラフについてその対応物をもつ。例えばサイクルはカットの双対であり、全域木は全域木の補集合の双対である。単純グラフ（または自己ループなし ）の双対は3辺連結グラフである。