关于最小割树的定义和证明
  • 板块学术版
  • 楼主Emertyst
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/3/6 22:16
  • 上次更新2023/10/23 22:49:11
查看原帖
关于最小割树的定义和证明
241100
Emertyst楼主2023/3/6 22:16

有一种说法,说最小割树有两种实现方式:

  1. 对于当前待处理的点集 VV,任选其中的两点 s,ts, t,求一遍 ss 到 tt 的最小割,同时需要对集合外的点缩点(防止割掉 VV 外的点之间的边),可以证明这样求出来的最小割和全局最小割相等,然后求出 ss 和 tt 所在的集合 S,TS, T,递归地处理 S∩VS \cap V 和 T∩VT \cap V。(具体怎么连边我忘了)
  2. 对于当前待处理的点集 VV,任选其中的两点 s,ts, t,求一遍 ss 到 tt 的全局最小割,在最小割树上面对应的 ss 和 tt 之间连边,边权为最小割。然后求出ss 和 tt 所在的集合 S,TS, T,递归地处理 S∩VS \cap V 和 T∩VT \cap V。

有几个问题:

  1. 这两种建树方式的正确性证明?
  2. 这两种树是等价的吗?怎么证明?
2023/3/6 22:16
加载中...