587
个编辑
更改
建立内容为“流网络的平衡方法是指将不满足平衡条件： <math> \sum_{j=0}^{N}f_{ji}=\sum_{j=1}^{N+1}f_{ij}, 0\leq i \leq N </math> 的流网络通…”的新页面
[[流网络]]的平衡方法是指将不满足平衡条件：
<math>
\sum_{j=0}^{N}f_{ji}=\sum_{j=1}^{N+1}f_{ij}, 0\leq i \leq N
</math>
的[[流网络]]通过人工调整流量、增加连边的方法，将网络变成平衡的算法。
==加边法（Naive Method）==
这是一种最简单、直接的平衡流网络的方法。如果某一个节点的出流大于入流，我们就添加从源到该节点的流；否则如果入流大于出流，则添加从该节点到汇的流。其中流量都等于出流与入流的差的绝对值。
具体地，对于任意的节点i，如果：
<math>
\sum_{j=0}^{N}f_{ji}>\sum_{j=1}^{N+1}f_{ij}, 0\leq i \leq N
</math>
则将流矩阵的0行i列元素改变为：
<math>
f_{0i}=\sum_{j=0}^{N}f_{ji}-\sum_{j=1}^{N+1}f_{ij}
</math>
而如果：
<math>
\sum_{j=0}^{N}f_{ji}<\sum_{j=1}^{N+1}f_{ij}, 0\leq i \leq N
</math>
则将流矩阵的i行N+1列元素改变为：
<math>
f_{i,N+1}=\sum_{j=1}^{N+1}f_{ij}-\sum_{j=0}^{N}f_{ji}
</math>
这样，整个流网络就处于平衡了
<math>
\sum_{j=0}^{N}f_{ji}=\sum_{j=1}^{N+1}f_{ij}, 0\leq i \leq N
</math>
的[[流网络]]通过人工调整流量、增加连边的方法，将网络变成平衡的算法。
==加边法（Naive Method）==
这是一种最简单、直接的平衡流网络的方法。如果某一个节点的出流大于入流，我们就添加从源到该节点的流；否则如果入流大于出流，则添加从该节点到汇的流。其中流量都等于出流与入流的差的绝对值。
具体地，对于任意的节点i，如果：
<math>
\sum_{j=0}^{N}f_{ji}>\sum_{j=1}^{N+1}f_{ij}, 0\leq i \leq N
</math>
则将流矩阵的0行i列元素改变为：
<math>
f_{0i}=\sum_{j=0}^{N}f_{ji}-\sum_{j=1}^{N+1}f_{ij}
</math>
而如果：
<math>
\sum_{j=0}^{N}f_{ji}<\sum_{j=1}^{N+1}f_{ij}, 0\leq i \leq N
</math>
则将流矩阵的i行N+1列元素改变为：
<math>
f_{i,N+1}=\sum_{j=1}^{N+1}f_{ij}-\sum_{j=0}^{N}f_{ji}
</math>
这样，整个流网络就处于平衡了