关于最小割树的定义和证明
  • 板块学术版
  • 楼主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,求一遍 sstt 的最小割,同时需要对集合外的点缩点(防止割掉 VV 外的点之间的边),可以证明这样求出来的最小割和全局最小割相等,然后求出 sstt 所在的集合 S,TS, T,递归地处理 SVS \cap VTVT \cap V。(具体怎么连边我忘了)
  2. 对于当前待处理的点集 VV,任选其中的两点 s,ts, t,求一遍 sstt 的全局最小割,在最小割树上面对应的 sstt 之间连边,边权为最小割。然后求出sstt 所在的集合 S,TS, T,递归地处理 SVS \cap VTVT \cap V

有几个问题:

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