主题
Search

割

给定一个带权重的无向图 G=(V,E) 和一个 图划分 将 V 分成两个集合 A 和 B, G 关于 A 和 B 的割定义为

cut(A,B)=sum_(i in A,j in B)W(i,j),

其中 W(i,j) 表示连接顶点 i 和 j 的边的权重。割的权重是跨越割的边的权重之和。

另请参阅

割点, 分支切割, 边割, 最大割, 最小割, 顶点割

使用 Wolfram|Alpha 探索

参考文献

Demmel, J. "CS 267: Lectures 20 and 21, Mar 21, 1996 and Apr 2, 1999. Graph Partitioning, Part 1." http://www.cs.berkeley.edu/~demmel/cs267/lecture18/lecture18.html.

在 Wolfram|Alpha 上被引用

割

请引用为

Weisstein, Eric W. "Cut." 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Cut.html

主题分类