FindMaximumCut

FindMaximumCut[g]

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

詳細とオプション

  • FindMaximumCutは最大カット問題としても知られている．
  • クラスタ分析，VLSI設計，統計力学でよく使われる．
  • グラフ g の最大カットは，g の頂点を，間の辺の数が最大である互いに素な2つの部分集合に分割することである．
  • FindMaximumCutは{cmin,{c1,c2}}の形式のリストを返す．cminは求まった最大カットの値，{c1,c2}は求まった頂点分割である．
  • FindMaximumCutは，重み付きグラフについては，ciの集合間で可能な辺重みの最大合計を持つ分割{c1,c2}を与える．
  • 次は使用可能なオプションである．
  • EdgeWeight Automatic各辺の辺重み
    PerformanceGoal"Speed"パフォーマンスのどの面について最適化するか

例題

すべて開くすべて閉じる

例  (1)

最大カットを求める：

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

スコープ  (5)

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

有向グラフにも使うことができる：

重み付きグラフ：

多重グラフ：

混合グラフ：

オプション  (1)

EdgeWeight  (1)

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

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

特性と関係  (1)

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

最大カット：

Wolfram Research (2020), FindMaximumCut, Wolfram言語関数， https://reference.wolfram.com/language/ref/FindMaximumCut.html.

テキスト

Wolfram Research (2020), FindMaximumCut, Wolfram言語関数， https://reference.wolfram.com/language/ref/FindMaximumCut.html.

CMS

Wolfram Language. 2020. "FindMaximumCut." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/FindMaximumCut.html.

APA

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

BibTeX

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

BibLaTeX

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