最小切入网络

Question

我正在尝试模拟无线传感器节点网络,以研究网络的稳健性.我遇到了以下问题:

我有一个具有一些边缘容量的节点网络.这相当于算法中的网络流问题.有一个源节点(检测某些事件)和一个汇聚节点(我的基站).现在,我想找到网络中的最小st cut,以便最小化源集的大小.此处设置的源是指由包含源的最小切割分隔的节点集.

例如,如果ST切割,C = {S,T},则存在一组可以被移除到网络分成两个边集合,S以及T与所述组S中包含的源和T包含信宿.当所有可能的st切割中切割边缘的容量总和最小时,切割是最小的.可以有几个这样的小切.我需要找到集合中元素数量最少的最小割S

请注意,这不是原始问题,但我已尝试简化它以便根据算法表达它.

Answer 1

我相信您可以通过在略微修改约束的图形中找到最小切割来解决此问题.这个想法如下 - 由于切割的成本等于切割的总容量,我们可以尝试通过在图中的每个节点添加额外边缘来修改图形,使其具有容量1.直观地说,这意味着切割的同一部分中的每个节点都会为切割的总成本贡献一个额外的成本,因为从该节点到t的边缘将越过边缘.当然,由于额外的容量,这肯定会弄乱实际的最小切割.为了解决这个问题,我们应用以下转换 - 首先,将边的容量乘以n,其中n是图中节点的数量.然后在每个边缘添加一个.这里的直觉是,通过将边缘容量乘以n,我们已经使得最小切割的成本(忽略从每个节点到t的新边缘)将是切割的原始成本的n倍.然后,当我们将每个节点的额外单容量边添加到t时,这些边可以对切割成本做出的最大可能贡献是n - 1(如果图中的每个节点除了t在同一侧作为s).因此,旧的最小切割的成本是C,新的最小切割(S,V-S)的成本是nC + | S |,其中| S | 是与s相同的节点数.

更正式的是,施工如下.给定定向的,容量图G和(源,汇)对(s,t),通过执​​行以下操作构造图G':

1. 对于图中的每个边(u,v),将其容量乘以n.
2. 对于图中的每个节点v,添加容量为1的新边(v,t).
3. 计算图表中的最小切割.

我声称图G'中的最小切割对应于图G中的最小切割,切口的同一侧上的节点数最少.证据如下.设(S,V-S)为G'中的最小切割.首先,我们需要证明(S,V - S)是G中的最小切割.这个证明是矛盾的; 为了矛盾而假设有一个st cut(S',V-S'),其成本低于(S,V-S)的成本.让G中的(S',V-S')的成本为C',并将G中的(S,V-S)的成本设为C.现在,让我们考虑G'中这两个削减的成本.通过收缩,C'的成本将是nC'+ | S'| (因为切割的S'侧的每个节点在切口上贡献一个容量)并且C的成本将是nC + | S |.既然我们知道C'<C,那么我们必须得到C'+1≤C

nC + | S | ≥n(C'+ 1)+ | S | = nC'+ n + | S |

现在,请注意0≤| S | <n且0≤| S'| <n,因为切割的同一侧最多可以有n个节点.因此意味着

nC + | S | ≥nC'+ n + | S | > nC'+ | S'| + | S | > nC'+ | S'|

但这意味着G'中(S,V - S)的成本大于G'中(S',V - S')的成本,这与(S,V - S)是min的事实相矛盾在G'切割.这使我们得出结论,G'中的任何最小切割也是G中的最小切割.

现在,我们需要证明,不仅G'中的最小切割也是G中的最小切割,但它对应于G中的最小切割,切割的同一侧上的节点数最少. .再次,这个证据是矛盾的; 假设(S,V - S)是G'中的最小切割但是在G中有一些最小切割,切割的s侧有更少的节点.称之为更好的切割(S',V - S').由于(S,V - S)是G'中的最小切割,因此它也是G中的最小切割,因此G中的(S',V - S')和(S,V - S)的成本是然后,G'中的(S,V-S)和(S',V-S')的成本将是nC + | S |.和nC + | S'|分别.我们知道nC + | S'| <nC + | S |,因为我们选择(S',V - S')作为G中的最小切割,与S在同一侧的节点数最少.但这意味着(S', V - S')的成本低于(S,V - S),这与(S,V - S)是G'中的最小切割相矛盾.因此,我们的假设是错误的,并且(S,V - S)是G中的最小切割,其中与S在同一侧的节点数最少.这样就完成了构造的正确性证明.

希望这可以帮助!