カット（グラフ理論）

グラフのノードを2つの互いに素なサブセットに分割する

グラフ理論において、カットとはグラフの頂点を互いに素な2つの部分集合に分割することである。^[1]任意のカットはカットセットを決定する。カットセットとは、分割された各部分集合にそれぞれ1つの端点を持つ辺の集合である。これらの辺はカットを横切ると言われる。連結グラフでは、各カットセットは一意のカットを決定し、場合によってはカットは頂点分割ではなくカットセットによって識別される。

フローネットワークにおいて、s-tカットとは、ソースとシンクが異なるサブセットに属するカットであり、そのカットセットはソース側からシンク側に向かうエッジのみで構成される。s-tカットのキャパシティは、カットセット内の各エッジのキャパシティの合計として定義される。

意味

カット $C$ $= ($ $S$ $,$ $T$ $)は$ 、グラフ $G$ $= ($ $V$ $,$ $E$ $)の$ $V$ を2つの部分集合 $S$ と $T$ に分割したものです。カット $C$ $= ($ $S$ $,$ $T$ $)の$ カットセットは、 S に一方の端点があり $T$ にもう一方の端点がある辺の集合 ${($ $u$ $,$ $v$ $) \in$ $E$ $|$ $u$ $\in$ $S$ $,$ $v$ $\in$ $T$ $}です。$ $s$ と $t が$ グラフ $G$ の指定された頂点である場合、 $s$ – $t$ カットは $s が$ $集合$ S に属し $、$ t が $集合$ T に属する $カット$ です。

重みのない無向グラフでは、カットの大きさまたは重みは、カットを横切る辺の数で表されます。重みのあるグラフでは、値または重みは、カットを横切る辺の重みの合計で定義されます。

結合とは、他のカットセットを適切なサブセットとして持たないカットセットです。

最小カット

カットのサイズまたは重量が他のカットのサイズよりも大きくない場合、そのカットは最小カットです。右の図は最小カットを示しています。このカットのサイズは2で、グラフにはブリッジがないため、サイズ1のカットは存在しません。

最大フロー最小カット定理は、ネットワークの最大フローと、ソースとシンクを分ける任意の最小カットにおけるカットエッジの重みの合計が等しいことを証明する。最小カット問題を解く多項式時間法があり、特にエドモンズ・カープアルゴリズムが有名である。^[2]

最大カット

カットのサイズが他のカットのサイズよりも小さくない場合、そのカットは最大カットとなります。右の図は最大カットを示しています。カットのサイズは5で、サイズ6、つまり| E |（辺の数）のカットは存在しません。これは、グラフが二部グラフではない（奇数サイクルが存在する）ためです。

一般的に、最大カットを見つけることは計算的に困難です。^[3] 最大カット問題は、カープの21のNP完全問題のうちの1つです。^[4] 最大カット問題はAPX困難でもあり、 P = NPでない限り多項式時間近似スキームは存在しません。^{[5]しかし、}半正定値計画法を使用して一定の近似比内で近似することができます。^[6]

最小カット問題と最大カット問題は、目的関数の最小値を最大値に変更することで一方の問題から他方の問題へ遷移できるものの、線形計画法の意味で双対問題ではないことに注意されたい。最大フロー問題は最小カット問題の双対問題である。^[7]

最もまばらなカット

最も疎なカット問題とは、カットを横切る辺の数を分割の小さい方の半分に含まれる頂点の数で割った比率が最小となるように頂点を二分割する問題である。この目的関数は、疎（カットを横切る辺が少ない）かつ均衡（二分法に近い）な解を優先する。この問題はNP困難であることが知られており、最もよく知られている近似アルゴリズムはArora、Rao、Vazirani (2009)による近似である。^[8] $O({\sqrt {\log n}})$

スペースをカット

無向グラフのすべてのカットセットの族は、グラフのカット空間として知られている。これは、 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プレスおよびマグロウヒル、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年7月15日にオリジナルからアーカイブ(PDF) 、 2019年8月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, geometric embeddings and graph partitioning」、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、第173巻、Springer、pp. 23– 28。
^ Korte, BH ; Vygen, Jens (2008)、「8.6 Gomory–Hu Trees」、Combinatorial Optimization: Theory and Algorithms、Algorithms and Combinatorics、第21巻、Springer、pp. 180– 186、ISBN 978-3-540-71844-4。

[networkx.algorithms.cuts.cut_size-1] “NetworkX 2.6.2 ドキュメント”. networkx.algorithms.cuts.cut_size . オリジナルから2021年11月18日にアーカイブ。 2021年12月10日閲覧。カットとは、グラフのノードを2つの集合に分割することです。カットサイズは、2つのノード集合「間」のエッジの重みの合計です。

[2] コーメン、トーマス・H. ;レイサーソン、チャールズ・E. ;リベスト、ロナルド・L. ;スタイン、クリフォード（2001年）、アルゴリズム入門（第2版）、MITプレスおよびマグロウヒル、p.563、655、1043、ISBN 0-262-03293-7。

[3] ガリー、マイケル・R. ;ジョンソン、デビッド・S. (1979)、「コンピュータとイントラクタビリティ：NP完全性理論へのガイド」、WHフリーマン、A2.2：ND16、p.210、ISBN 0-7167-1045-5。

[4] Karp, RM (1972)、「組合せ問題における縮約可能性」、Miller, RE; Thacher, JW (編)、『コンピュータ計算の複雑性』、ニューヨーク：Plenum Press、pp. 85– 103。

[5] 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年7月15日にオリジナルからアーカイブ(PDF) 、 2019年8月29日取得。

[6] Goemans, MX ; Williamson, DP (1995)、「半正定値計画法を用いた最大カット問題と充足可能性問題に対する改良近似アルゴリズム」、Journal of the ACM、42 (6): 1115– 1145、doi : 10.1145/227683.227684 。

[7] Vazirani、Vijay V. (2004)、近似アルゴリズム、Springer、 97–98ページ、ISBN 3-540-65367-8。

[8] Arora, Sanjeev ; Rao, Satish ; Vazirani, Umesh (2009)、「Expander flows, geometric embeddings and graph partitioning」、J. ACM、56 (2)、ACM: 1– 37、doi :10.1145/1502793.1502794、S2CID 263871111 。

[gy-9] Gross, Jonathan L.; Yellen, Jay (2005)、「4.6 グラフとベクトル空間」、グラフ理論とその応用（第2版）、CRC Press、pp. 197– 207、ISBN 9781584885054。

[diestel-10] Diestel, Reinhard (2012)、「1.9 いくつかの線形代数」、グラフ理論、Graduate Texts in Mathematics、第173巻、Springer、pp. 23– 28。

[11] Korte, BH ; Vygen, Jens (2008)、「8.6 Gomory–Hu Trees」、Combinatorial Optimization: Theory and Algorithms、Algorithms and Combinatorics、第21巻、Springer、pp. 180– 186、ISBN 978-3-540-71844-4。