カットとサイクル

ウィキペディア小見出し辞書

カットとサイクル

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/11 14:38 UTC 版)

「双対グラフ」の記事における「カットとサイクル」の解説

任意の連結グラフのカットセットは、グラフの頂点を2つのサブセットに分けたとき、この2つのサブセットどうしをつなぐ辺の集合である。グラフからカットセットを取り除くと、必然的にグラフは少なくとも2つの連結成分に分割される。最小カットセット（ボンドとも呼ばれる）は、カットセットのすべてのサブセットがそれ自体カットではないという特性を持つカットセットである。連結グラフの最小カットセットは、必然的にそのグラフを2つのグラフに分割する。単純なサイクルは、連結サブグラフのうち、サイクルの各頂点が2つの辺を持つようなものである。 接続平面グラフGはGのすべての単純サイクルは、Gの双対の最小カットセットとみなすことができ、またその逆も成り立つ。これは、ジョルダン曲線定理の一種として見ることができる。単純な各サイクルは、Gの面をサイクルの内側の面とサイクルの外側の面に分離し、サイクル辺の双対は内部から外部へと交差する辺となる。任意の平面グラフの内周（グラフがもつ最小サイズのサイクル）はその双対グラフの辺連結度（グラフがもつ最小サイズのカットセット）に等しい。 この二重性は個々のカットセットとサイクルから定義されたベクトル空間まで及ぶ。グラフのサイクル空間（英語版）とは の集合であるすべての頂点が偶数の次数を持っているようなサブグラフ（オイラーグラフ）の集合である。サイクル空間は2要素有限体上のベクトル空間と見なすことができ、2組の辺の対称差はベクトル空間でのベクトル加算演算として機能する。同様の加算により、グラフのカット空間はすべてのカットセットのファミリーとして定義される。その場合、任意の平面グラフのサイクル空間とその双対グラフのカット空間は同型なベクトル空間となる したがって、平面グラフのランク（カットスペースの次元）は、その双対のサイクルランク（サイクル空間の次元）に等しく、その逆も成り立つ。グラフのサイクル基底はグラフに含まれる単純サイクルのうち、サイクル空間の基底を構成するようなものの集合である（全ての偶数次数の部分グラフがそれらのサイクルの対称差として一意に定まる）辺重み付き平面グラフ（2つのサイクルが同じ重みを持たないような十分に一般的な重みを持つ）の場合、グラフの最小重みサイクル基底は双対グラフのゴモリ・フー木と双対になる。最小重みサイクル基底の各サイクルには、ゴモリ・フー木のいずれかのカットの辺と双対となる辺の集合をもつ。もしサイクルどうしの重みが等しくなる場合、最小重みサイクルの基底は一意でなくなる可能性があるが、双対グラフのゴモリ・フー木が最小重みサイクルの基底に対応することに変わりはない。 有向平面グラフでは、単純な有向サイクルは有向カット（頂点を2つの部分集合に分割し、すべてのエッジが一方の部分集合から他方の部分集合に向かう）に対して双対となる。強く方向付けられた平面グラフ（含まれる無向グラフの全ての辺が1つのサイクルに属しているグラフ）は、辺が1つのサイクルに属していない有向非巡回グラフに対して双対となる。別の言い方をすると、連結平面グラフの強い向き（強い連結グラフとなるグラフのエッジへの方向の割り当て）は、非巡回方向（有向非巡回グラフを生成する方向の割り当て）に対して双対となる。