Loading article…
グラフ理論において、無向グラフの分割とは、そのカット集合が完全二部グラフを形成するカットのことである。グラフが分割を持たない場合、そのグラフは素グラフと呼ばれる。グラフの分割は、分割分解または結合分解と呼ばれる木構造にまとめることができ、これは線形時間で構築できる。この分解は、円グラフや距離遺伝グラフの高速認識、およびグラフアルゴリズムにおけるその他の問題に利用されてきた。
分割と分割分解は、カニンガム（1982）によって初めて導入され、彼は有向グラフについても同じ概念の変種を研究した。[ 1 ]
無向グラフのカットとは、頂点を2つの空でない部分集合（カットの辺）に分割することです。各辺に1つの端点を持つ辺の部分集合をカットセットと呼びます。カットセットが完全二部グラフを形成する場合、そのカットはスプリットと呼ばれます。したがって、スプリットは、グラフの頂点を2つの部分集合XとYに分割し、Y内のXのすべての隣接点がX内のYのすべての隣接点に隣接するように記述できます。[ 2 ]
カットまたは分割は、その2つの辺のうちの1つに頂点が1つしかない場合に自明である。すべての自明なカットは分割である。グラフは、非自明な分割を持たない場合に（分割に関して）素数であると言われる。[ 2 ]
2 つの分割は、一方の分割の各側が他方の分割の各側と空でない共通部分を持つ場合に交差すると言われます。分割は、他のどの分割とも交差しない場合に強い分割と呼ばれます。特別な場合として、すべての自明な分割は強い分割です。グラフの強い分割は、グラフの分割分解または結合分解と呼ばれる構造を生み出します。この分解は、葉が与えられたグラフと 1 対 1 に対応し、エッジがグラフの強い分割と 1 対 1 に対応する木で表すことができ、木から任意のエッジを削除して形成される葉の分割は、関連する強い分割によって与えられる頂点の分割と同じです。[ 2 ]
グラフGの分割分解木の各内部ノードi は、ノードiの商グラフと呼ばれるグラフG iに関連付けられています。商グラフは、木からi を削除し、結果として得られる各部分木の葉に対応するGの頂点の部分集合を形成し、これらの頂点集合をそれぞれ単一の頂点に縮約することによって形成できます。すべての商グラフは、プライムグラフ、完全グラフ、またはスターの 3 つの形式のいずれかになります。[ 2 ]
グラフには指数関数的に多くの異なる分割が存在する可能性があるが、それらはすべて分割分解木に表現され、木の辺として（強い分割の場合）、または完全グラフもしくはスター商グラフの任意の分割として（強くない分割の場合）表現される。[ 2 ]
完全グラフまたは完全二部グラフでは、すべてのカットは分割です。
長さが4のサイクルグラフでは、サイクルを2色で彩色することによって得られる頂点の分割は非自明な分割であるが、それより長いサイクルでは非自明な分割は存在しない。
2辺連結でないグラフのブリッジは分割に対応し、分割の両側はブリッジの片側の頂点によって形成されます。分割のカットセットは単一のブリッジエッジであり、これは完全二部グラフの特殊なケースです。同様に、vが2頂点連結でないグラフの関節点である場合、グラフには複数の分割があり、vとその削除によって形成されるコンポーネントの一部（すべてではない）が片側にあり、残りのコンポーネントがもう一方の側にあります。これらの例では、分割のカットセットは星形を形成します。
カニンガム（1982）は、分割分解を多項式時間で見つけることが可能であることを既に示しました。[ 1 ]その後、アルゴリズムが改良され、[ 3 ] [ 4 ]線形時間アルゴリズムがダールハウス（2000）[ 5 ]とシャルビット、ド・モンゴルフィエ、ラフィノ（2012）によって発見されました。[ 2 ]
分割分解は、いくつかの重要なグラフクラスの認識に適用されてきた。
分割分解は、任意のグラフ上でNP困難な問題の解決を簡略化するためにも使用されてきました。[ 9 ]
これらの手法は、各商グラフが単純な構造を持ち、その部分問題を効率的に計算できるグラフに対して、多項式時間アルゴリズムにつながる可能性がある。例えば、各商グラフのサイズが一定であるグラフでは、これが当てはまる。[ 9 ]