102
个编辑
更改
无编辑摘要
一个平衡的[[流网络]]可以自然地转变成[[马尔科夫链]]，而[[马尔科夫链]]是数学家们研究得非常深入而透彻的数学对象，因此这为我们更好地分析[[流网络]]提供了便利条件。
一个平衡的[[流网络]]可以自然地转变成[[马尔科夫链]]，而[[马尔科夫链]]是数学家们研究得非常深入而透彻的数学对象，因此这为我们更好地分析[[流网络]]提供了便利条件。
下面给出基本计算简表。
<math>
定义：流矩阵F，对应的马尔科夫链矩阵M
m_{ij}=\frac{f_{ij}}{\sum_{j=1}^{N+1}f_{ij}}
M中的元素为：<math>m_{ij}=\frac{f_{ij}}{\sum_{j=1}^{N+1}f_{ij}}</math>
</math>，
定义基础矩阵：<math>U=I+M+M^2+\cdot\cdot\cdot=(I-M)^{-1}</math>, 其中[math]I[/math]单位阵
U=I+M+M^2+\cdot\cdot\cdot=(I-M)^{-1}
</math>
[math]U[/math]中的元素[math]u_{i,j}[/math]表示i到j所有可能路径的影响，包括直接路径和间接路径。
t_{i,j}=T_0\frac{u_{0,i}u_{i,j}}{u_{i,i}}
而流网络中一些关键的量可以由流矩阵M和基础矩阵U定义出来。
</math>，i到j的首达流：<math>
i到j的总流记为：<math>t_{i,j}=T_0\frac{u_{0,i}u_{i,j}}{u_{i,i}}</math>。
</math>
i到j的首达流记为：<math> \phi_{i,j}=T_0 \frac{u_{0,i}u_{i,j}}{u_{i,i}u_{j,j}}</math>。 其中T<sub>0</sub>为从源输入到整个网络的流量，也就是IS（参看[[流动网络]]）。根据这两个公式，可以计算任意网络任意节点对的总流和首达流。
i到j的平均时间：<math>k_{i,j}=\frac{(MU^2)_{ij}}{(MU)_{ij}}</math>
i到j的平均时间：<math>
i到j的首达平均时间：<math>l_{i,j}=\frac{u_{jj}(M_{-j}U_{-j}^2)_{ij}}{u_{ij}}=\frac{(MU^2)_{ij}}{u_{ij}}-\frac{(MU^2)_{jj}}{u_{jj}}</math>。其中<math>M_{-j}</math>表示将M的第i行全置为0，<math>U_{-j}=I+M_{-j}+M_{-j}^{2}+\cdot\cdot\cdot=(I-M)^{-1}</math>。
k_{i,j}=\frac{(MU^2)_{ij}}{(MU)_{ij}}
</math>，i到j的首达平均时间：<math>l_{i,j}=\frac{u_{jj}(M_{-j}U_{-j}^2)_{ij}}{u_{ij}}=\frac{(MU^2)_{ij}}{u_{ij}}-\frac{(MU^2)_{jj}}{u_{jj}}
</math>