如何找到流网络中每个汇的最终存储量？

Question

我有一个单源多汇流网络。如果我从源头流出 1 加仑的水，那么所有的水都会在节点处分裂，最后储存在不同的水槽中。这里每个边权重 c(u,v) 表示来自 u 的水分裂率。如何找到每个水槽的最终储水量？

手动计算的例子：

Answer 1

这是 absorbing Markov chain 的示例。

设 Q[j,i] 为从第 j^th 个非汇聚节点到第 i^th 个非汇聚节点的流量比例。

令 R[j,i] 为从第 j^th 个非汇聚节点到第 i^th 个汇聚节点的流量比例。

则设矩阵N=inv(I-Q)，矩阵B=N*R。

第i^个sink节点的最终流量由B[0,i]给出。

Python 第一个案例的示例：

import numpy as np

# Rows are proportion of flow out of each non-sink vertex
Q = np.zeros((3,3))
Q[0,:] = 0,0.3,0.7 # Flow out of S
Q[1,:] = 0,0,0     # Flow out of a
Q[2,:] = 0,0.5,0   # Flow out of b
# Rows are flow from non-sink to sink nodes
R = np.zeros((3,2))
R[1,:] = 0.1,0.9
R[2,:] = 0,0.5 
N = np.matrix(np.identity(len(Q)) - Q).I
B = N*R
print B[0,:]

打印

[[ 0.065  0.935]]

说明

一旦我们设置了矩阵，我们就可以通过包含 [1,0,0]（表示开始时的一加仑）和一个空行向量的行向量 v 开始模拟一个时间步长的流量e（代表水槽中的水量）。

在每个时间步我们计算：

e += v * R # This works out the amount of flow that has reached the end
v = v * Q # This works out the amount of flow that is still in the network

如果我们模拟这个足够长的时间，我们最终将 v 接近 0，而 e 接近答案。

但是我们可以将 e 的值写为：

e = v*R + v*Q*R + v*Q*Q*R + v*Q*Q*Q*R +...
  = v * (I + Q + Q*Q + Q*Q*Q + ...) * R
  = v * inv(I-Q) * R
  = v * N * R
  = v * B
  = [1,0,0] * B
  = first row of B

如何找到流网络中每个汇的最终存储量？

How to find final stored amount in each sink in a flow network?

algorithm

graph-theory

max-flow

说明