寻找平衡节点值的边权重

Question

我正在处理一个图表，其中节点具有可能为正或负的关联值。我需要为这个图的边分配权重，这样我的网络就是 'balanced.' 例如，如果我有一个有两个节点的图，值为 +10 和 -10，我的邻接矩阵是：

0   1
1   0

我需要弄清楚如何为这些边分配权重，例如：

0   10
0   0

这样生成的传输将 'neutralize' 我节点上的值。

一个更复杂的例子是一个看起来像这样的图表：

-10 -- 0 -- +20
       |
       0
       |
      -10

会在邻接矩阵中描述，如下所示：

0   10  0   0   0
0   0   20  0   0
0   0   0   0   0
0   10  0   0   0
0   0   0   10  0

这个问题有什么众所周知的解决方案吗？

Answer 1

我能够使用最大流量计算来解决这个问题，方法是将所有带负电荷的链接连接到一个 'sink'，链接的最大容量与其电荷相对应，并将所有带正电荷的节点连接到具有与节点电荷相对应的最大容量的链路的源。在计算源和汇之间的最大流量的过程中，邻接矩阵记录了沿链接的流量。

我专门用了Edmonds Karp算法

Finding edge weights that balance node values