Loading article…
グラフ理論において、カットとはグラフの頂点を互いに素な2つの部分集合に分割することである。[ 1 ]任意のカットはカットセット、すなわち分割の各部分集合に1つの端点を持つ辺の集合を決定する。これらの辺はカットを横切ると言われる。連結グラフでは、各カットセットは一意のカットを決定し、場合によってはカットは頂点の分割ではなくカットセットで識別される。
フローネットワークにおいて、s-tカットとは、ソースとシンクが異なるサブセットに属することを要求し、そのカットセットがソース側からシンク側へ向かうエッジのみで構成されるカットのことである。s -tカットの容量は、カットセット内の各エッジの容量の合計として定義される。
カットC = ( S , T )は 、グラフG = ( V , E )のVを2 つの部分集合SとTに分割したものです。カットC = ( S , T )のカット集合は、一方の端点がSにあり、もう一方の端点がTにあるエッジの集合{( u , v ) ∈ E | u ∈ S , v ∈ T }です。sとt がグラフG の指定された頂点である場合、s – tカットは、 s が集合Sに属し、t が集合Tに属するカットです。
重み付けのない無向グラフでは、カットのサイズまたは重みは、カットを横切るエッジの数です。重み付けのあるグラフでは、値または重みは、カットを横切るエッジの重みの合計によって定義されます。
ボンドとは、他のカットセットを真部分集合として持たないカットセットのことである。
カットのサイズまたは重量が他のどのカットのサイズよりも大きくない場合、そのカットは最小カットとなります。右の図は最小カットを示しています。このカットのサイズは2であり、グラフにブリッジがないため、サイズ1のカットは存在しません。
最大フロー最小カット定理は、最大ネットワークフローと、ソースとシンクを分離する任意の最小カットのカットエッジの重みの合計が等しいことを証明します。最小カット問題を解くための多項式時間法があり、特にエドモンズ・カープアルゴリズムが有名です。[ 2 ]
カットのサイズが他のどのカットのサイズよりも小さくない場合、そのカットは最大カットです。右の図は最大カットを示しています。カットのサイズは 5 であり、グラフが二部グラフではないため(奇数サイクルが存在するため)、サイズ 6 または | E | (エッジの数)のカットは存在しません。
一般に、最大カットを見つけることは計算上困難である。[ 3 ] 最大カット問題は、Karp の 21 個の NP 完全問題の 1 つである。[ 4 ] 最大カット問題はAPX 困難でもある。つまり、 P = NPでない限り、多項式時間近似スキームは存在しない。[ 5 ]ただし、半正定値計画法を使用すれば、定数近似比の範囲 内で近似することができる。[ 6 ]
目的関数で min を max に変更することで一方の問題から他方の問題に移行できるとしても、最小カット問題と最大カット問題は線形計画法の意味で双対問題ではない ことに注意してください。最大フロー問題は最小カット問題の双対問題です。[ 7 ]
最も疎なカット問題は、カットを横切るエッジの数と、分割された小さい方の半分の頂点の数の比を最小化するように頂点を二分割することです。この目的関数は、疎（カットを横切るエッジが少ない）かつバランスが取れている（二分法に近い）解を好みます。この問題はNP困難であることが知られており、最もよく知られている近似アルゴリズムは、Arora、Rao 、 Vazirani (2009)による近似。[ 8 ]
無向グラフのすべてのカットセットの族は、グラフのカット空間として知られています。これは、2 つのカットセットの対称差をベクトル加算演算として、 2 元有限算術法体上のベクトル空間を形成し、サイクル空間の直交補空間です。[ 9 ] [ 10 ]グラフのエッジに正の重みが与えられると、カット空間の最小重み基底は、グラフと同じ頂点集合上の木で記述でき、これはGomory–Hu 木と呼ばれます。[ 11 ]この木の各エッジは、元のグラフの結合に関連付けられており、2 つのノードsとtの間の最小カットは、木内のsからtへのパスに関連付けられている結合の中で最小の重みを持つ結合です。
とは、グラフのノードを 2 つのセットに分割することです。カット サイズは、2 つのノード セット「間」のエッジの重みの合計です。
