保存帖子
发现
索引
热门
陶片放逐
关于
关于最小割树的定义和证明
板块
学术版
楼主
Emertyst
当前回复
5
已保存回复
5
发布时间
2023/3/6 22:16
上次更新
2023/10/23 22:49:11
查看原帖
更新帖子
被骇客
银
狼
阻止的越权访问
保存失败
关于最小割树的定义和证明
Emertyst
楼主
2023/3/6 22:16
有一种说法,说最小割树有两种实现方式:
对于当前待处理的点集
V
V
V
,任选其中的两点
s
,
t
s, t
s
,
t
,求一遍
s
s
s
到
t
t
t
的最小割,同时需要对集合外的点缩点(防止割掉
V
V
V
外的点之间的边),可以证明这样求出来的最小割和全局最小割相等,然后求出
s
s
s
和
t
t
t
所在的集合
S
,
T
S, T
S
,
T
,递归地处理
S
∩
V
S \cap V
S
∩
V
和
T
∩
V
T \cap V
T
∩
V
。(具体怎么连边我忘了)
对于当前待处理的点集
V
V
V
,任选其中的两点
s
,
t
s, t
s
,
t
,求一遍
s
s
s
到
t
t
t
的全局最小割,在最小割树上面对应的
s
s
s
和
t
t
t
之间连边,边权为最小割。然后求出
s
s
s
和
t
t
t
所在的集合
S
,
T
S, T
S
,
T
,递归地处理
S
∩
V
S \cap V
S
∩
V
和
T
∩
V
T \cap V
T
∩
V
。
有几个问题:
这两种建树方式的正确性证明?
这两种树是等价的吗?怎么证明?
2023/3/6 22:16
加载中...