Enable JavaScript to interact with content and submit forms on Wolfram websites. Learn how

FindMaximumCut

FindMaximumCut[g]

给出图 g 的最大割.

更多信息和选项

FindMaximumCut 亦称为最大割问题.
通常用于聚类分析、VLSI 设计和统计物理学.
图 g 的最大割是将 g 的顶点分割为两个不相交的子集，使得它们之间的边的数量最大.

FindMaximumCut 返回形式为 {c_min,{c₁,c₂}} 的列表，其中 c_min 是找到的最大割，{c₁,c₂} 是相应的顶点的分割.
对于加权图，FindMaximumCut 给出分割 {c₁,c₂}，使得集合 c_i 之间的边的权重之和最大
可以给出以下选项：
EdgeWeight Automatic 每条边的权重

PerformanceGoal "Speed" 优化的目标

范例

打开所有单元关闭所有单元

基本范例 (1)

求最大割：

突出显示最大割：

范围 (5)

FindMaximumCut 适用于无向边：

有向边：

加权图：

多图：

混合图：

选项 (1)

EdgeWeight (1)

默认情况下，边的权重即为它的 EdgeWeight 属性（如果存在的话），否则为 1：

用 EdgeWeight->weights 设置边的权重：

属性和关系 (1)

用 FindGraphPartition 求使两部分大致相等的分割：

最大割：

顶部