流网络的平衡

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
是趣木木呀讨论 | 贡献2021年11月11日 (四) 11:00的版本 (建立内容为“流网络的平衡方法是指将不满足平衡条件: <math> \sum_{j=0}^{N}f_{ji}=\sum_{j=1}^{N+1}f_{ij}, 0\leq i \leq N </math> 的流网络通…”的新页面)
(差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)
跳到导航 跳到搜索

流网络的平衡方法是指将不满足平衡条件:

[math]\displaystyle{ \sum_{j=0}^{N}f_{ji}=\sum_{j=1}^{N+1}f_{ij}, 0\leq i \leq N }[/math]

流网络通过人工调整流量、增加连边的方法,将网络变成平衡的算法。

加边法(Naive Method)

这是一种最简单、直接的平衡流网络的方法。如果某一个节点的出流大于入流,我们就添加从源到该节点的流;否则如果入流大于出流,则添加从该节点到汇的流。其中流量都等于出流与入流的差的绝对值。

具体地,对于任意的节点i,如果:

[math]\displaystyle{ \sum_{j=0}^{N}f_{ji}\gt \sum_{j=1}^{N+1}f_{ij}, 0\leq i \leq N }[/math]

则将流矩阵的0行i列元素改变为:

[math]\displaystyle{ f_{0i}=\sum_{j=0}^{N}f_{ji}-\sum_{j=1}^{N+1}f_{ij} }[/math]

而如果:

[math]\displaystyle{ \sum_{j=0}^{N}f_{ji}\lt \sum_{j=1}^{N+1}f_{ij}, 0\leq i \leq N }[/math]

则将流矩阵的i行N+1列元素改变为:

[math]\displaystyle{ f_{i,N+1}=\sum_{j=1}^{N+1}f_{ij}-\sum_{j=0}^{N}f_{ji} }[/math]

这样,整个流网络就处于平衡了