カット (グラフ理論)

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

グラフ理論におけるカット: Cut)は、グラフの頂点を2つの部分集合に分割することである。G(V, E) がグラフを表すとする。カットとは、頂点の集合 V を2つの集合 ST に分割することを指す。任意のエッジ (u,v) \in E について u \in S でかつ v \in T(有向グラフの場合 u \in T でかつ v \in S の場合もある)のとき、このエッジを「カットをまたいでいる」あるいは「カットエッジ」と呼ぶ。

「カットの大きさ」は、カットをまたいでいるエッジの総数で表される。重み付けされたグラフでは、カットの大きさはカットをまたいでいるエッジの重み付けの総和で定義される。フローネットワークでは、カットの大きさは始点側から終点側へ向かうエッジの重み付けの総和で定義される(逆方向のエッジは加算されない)。

頂点集合のべき集合を定義域としたカットの大きさを返す集合関数は「カット関数」と呼ばれ、 劣モジュラ関数、かつ、正モジュラ関数である。

最小カットと最大カット[編集]

最小カット[編集]

最小カット
最大カット

カットが最小であるとは、カットの大きさが他のいかなるカットよりも大きくないことを指す。最大フロー最小カット定理は、最大フロー(流量)が始点と終点を別々の部分集合とするカットのうちで最小なものの大きさ(カットエッジの重み付けの総和)と等しいことを意味する。最小カットを求める問題には多項式時間アルゴリズムが存在し、フォード・ファルカーソンのアルゴリズムが有名である。 最小カットの大きさは辺連結度とも呼ばれる。

無向グラフのすべての最小カットはカクタスと呼ばれるグラフで表現でき、 アルゴリズムにおけるデータ構造としての利用を含め様々な応用が存在する。

最小カット問題と双対をなすのは最大フロー問題である。線形計画的意味では、(たとえ、目的関数の最大と最小を入れ替えて解が得られたとしても)最小カット問題と最大カット問題は双対問題ではない。

最大カット[編集]

カットが最大であるとは、カットの大きさが他のいかなるカットよりも小さくないことを指す。あるカットが最大であるかを判定する問題は、NP完全問題である。つまり、効率的に近似解を求めるメタヒューリスティックな探索手法は存在するが、多項式時間で最大カットを求めるアルゴリズムは存在しないと広く信じられている。最大カット問題がNP完全であることの証明は、最大充足可能性問題からの変換で得られる。

平面グラフでの最大カットを求める多項式時間アルゴリズムは存在する。純粋な乱択アルゴリズムである 0.5近似アルゴリズムが存在する。最もよく知られている最大カットアルゴリズムは、Goemans と Williamson が半正定値計画とランダム化丸め算法を使って考案した 0.878近似アルゴリズムである(日本語解説記事には [1] がある)。unique games conjecture が真である限りにおいて、このアルゴリズムは最適な近似アルゴリズムと言える。

関連項目[編集]

参考文献[編集]

脚注[編集]

[ヘルプ]
  1. ^ 松井知己 (2000), “半正定値計画を用いた最大カット問題の.878近似解法”, オペレーションズ・リサーチ 45 (3): 140-145