Loading article…
グラフ理論において、カットとはグラフの頂点を2つの互いに素な部分集合に分割することです。[1]カットはいずれもカットセット、つまり分割の各部分集合に1つの端点を持つ辺の集合を決定します。これらの辺はカットを横切ると言われます。連結グラフでは、各カットセットが一意のカットを決定し、場合によってはカットは頂点分割ではなくカットセットで識別されます。
フロー ネットワークでは、s-t カットはソースとシンクが異なるサブセットに存在する必要があり、そのカット セットはソース側からシンク側に向かうエッジのみで構成されるカットです。s-t カットの容量は、カット セット内の各エッジの容量の合計として定義されます。
意味
カットC = ( S , T )は 、グラフG = ( V , E )のVを2 つの部分集合SとTに分割したものです。カットC = ( S , T )のカットセットは、 1 つの端点がSにあり、もう 1 つの端点が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]
最小カットと最大カットは線形計画法の意味での双対問題ではないことに注意してください。 目的関数の最小値を最大値に変更することで、一方の問題からもう一方の問題に移行できます。最大フロー問題は、最小カット問題の双対問題です。[7]
最もまばらなカット
最も疎なカットの問題は、カットを横切るエッジの数を分割の小さい方の半分の頂点の数で割った比率を最小にするように頂点を二分割することです。この目的関数は、疎 (カットを横切るエッジが少ない) かつバランスの取れた (二分法に近い) 解を優先します。この問題は NP 困難であることが知られており、最もよく知られている近似アルゴリズムは、Arora、Rao、Vazirani (2009) による近似です。[8]
スペースをカット
無向グラフのすべてのカットセットの族は、グラフのカット空間として知られています。これは、2を法とする2要素の有限体算術上のベクトル空間を形成し、 2つのカットセットの対称差をベクトルの加算演算とし、サイクル空間の直交補空間です。[9] [10]グラフの辺に正の重みが与えられている場合、カット空間の最小重み基底は、グラフと同じ頂点集合上の木、ゴモリ・フー木によって記述できます。[11]この木の各辺は元のグラフの結合に関連付けられており、2つのノードsとtの間の最小カットは、木でsからtへのパスに関連付けられている結合の中で最小重みの結合です。
参照
参考文献
- ^ 「NetworkX 2.6.2 ドキュメント」。networkx.algorithms.cuts.cut_size。 2021-11-18 にオリジナルからアーカイブ。2021-12-10に取得。
カットは、グラフのノードを 2 つのセットに分割することです。 カット サイズは、2 つのノード セット間のエッジの重みの合計です。
- ^ コーメン、トーマス H. ;レイザーソン、チャールズ E. ;リベスト、ロナルド L. ;スタイン、クリフォード(2001)、『アルゴリズム入門』（第 2 版）、MIT プレスおよび McGraw-Hill、p. 563,655,1043、ISBN 0-262-03293-7。
- ^ ガリー、マイケル・R. ;ジョンソン、デビッド・S. (1979)、「コンピュータとイントラクタビリティ：NP完全性理論ガイド」、WHフリーマン、A2.2：ND16、p. 210、ISBN 0-7167-1045-5。
- ^ Karp, RM (1972)、「組合せ問題における縮約可能性」、Miller, RE; Thacher, JW (編)、『コンピュータ計算の複雑性』、ニューヨーク: Plenum Press、pp. 85–103。
- ^ Khot, S. ; Kindler, G.; Mossel, E.; O'Donnell, R. (2004)、「MAX-CUT およびその他の 2 変数 CSP の最適な近似不可能性結果?」(PDF)、Proceedings of the 45th IEEE Symposium on Foundations of Computer Science、pp. 146–154、2019-07-15にオリジナルからアーカイブ(PDF) 、2019-08-29に取得。
- ^ Goemans, MX ; Williamson, DP (1995)、「半正定値計画法を用いた最大カットおよび充足可能性問題に対する改良近似アルゴリズム」、Journal of the ACM、42 (6): 1115–1145、doi : 10.1145/227683.227684。
- ^ Vazirani、Vijay V. (2004)、近似アルゴリズム、Springer、97–98 ページ、ISBN 3-540-65367-8。
- ^ Arora, Sanjeev ; Rao, Satish; Vazirani, Umesh (2009)、「Expander flows, geographical embeddeds and graph splitting」、J. ACM、56 (2)、ACM: 1–37、doi :10.1145/1502793.1502794、S2CID 263871111。
- ^ Gross, Jonathan L.; Yellen, Jay (2005)、「4.6 グラフとベクトル空間」、グラフ理論とその応用 (第 2 版)、CRC Press、pp. 197–207、ISBN 9781584885054。
- ^ Diestel, Reinhard (2012)、「1.9 いくつかの線形代数」、グラフ理論、Graduate Texts in Mathematics、vol. 173、Springer、pp. 23–28。
- ^ Korte, BH ; Vygen, Jens (2008)、「8.6 Gomory–Hu Trees」、組み合わせ最適化: 理論とアルゴリズム、アルゴリズムと組み合わせ論、第 21 巻、Springer、pp. 180–186、ISBN 978-3-540-71844-4。