FindMinimumCut

FindMinimumCut[g]

グラフ g の最小カットを与える．

FindMinimumCut[{vw,…}]

規則 vw を使ってグラフ g を指定する．

詳細とオプション

  • グラフ g の最小 k-カットは，g の頂点を頂点間の辺の数が最小となる k 個の非連結部分集合へ分割することである．
  • FindMinimumCutは{cmin,{c1,c2,…}}の形のリストを返す．ただし，cminは求まる最小カットの値で{c1,c2,…}は求まった頂点分割である．
  • 重み付きグラフの場合は，FindMinimumCutは，集合 ci間で可能な辺重みの最小の和を持つ分割{c1,c2,…}を与える．
  • 使用可能なオプション
  • EdgeWeight Automatic各辺の辺重み

例題

すべて開くすべて閉じる

例  (1)

最小カットを求める：

カットをハイライトする：

スコープ  (7)

FindMinimumCutは無向グラフに使うことができる：

有向グラフに使う：

重み付きグラフ：

多重グラフ：

混合グラフ：

規則を使ってグラフを指定する：

FindMinimumCutは大きいグラフに使うことができる：

オプション  (1)

EdgeWeight  (1)

デフォルトで，辺の重みは可能な場合はそのEdgeWeight特性であり，その他の場合は1であるとみなされる：

EdgeWeight->weights を使って辺重みを設定する：

特性と関係  (3)

FindGraphPartitionを使ってほぼ同じ大きさの部分になるカットを求める：

最小カット：

EdgeConnectivityは最小カットの値に等しい：

FindEdgeCutを使ってカット集合間の辺を求める：

辺とカット集合をハイライトする：

Wolfram Research (2012), FindMinimumCut, Wolfram言語関数， https://reference.wolfram.com/language/ref/FindMinimumCut.html （2015年に更新）.

テキスト

Wolfram Research (2012), FindMinimumCut, Wolfram言語関数， https://reference.wolfram.com/language/ref/FindMinimumCut.html （2015年に更新）.

CMS

Wolfram Language. 2012. "FindMinimumCut." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindMinimumCut.html.

APA

Wolfram Language. (2012). FindMinimumCut. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindMinimumCut.html

BibTeX

@misc{reference.wolfram_2024_findminimumcut, author="Wolfram Research", title="{FindMinimumCut}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindMinimumCut.html}", note=[Accessed: 18-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_findminimumcut, organization={Wolfram Research}, title={FindMinimumCut}, year={2015}, url={https://reference.wolfram.com/language/ref/FindMinimumCut.html}, note=[Accessed: 18-November-2024 ]}