2,443
个编辑
更改
无编辑摘要
一个平衡的[[流网络]]可以自然地转变成[[马尔科夫链]]，而[[马尔科夫链]]是数学家们研究得非常深入而透彻的数学对象，因此这为我们更好地分析[[流网络]]提供了便利条件。
一个平衡的[[流网络]]可以自然地转变成[[马尔科夫链]]，而[[马尔科夫链]]是数学家们研究得非常深入而透彻的数学对象，因此这为我们更好地分析[[流网络]]提供了便利条件。
下面给出基本计算简表。定义：流矩阵F，对应的马尔科夫链矩阵M
<math>m_{ij}=\frac{f_{ij}}{\sum_{j=1}^{N+1}f_{ij}}</math>
基础矩阵:<math>
U=I+M+M^2+\cdot\cdot\cdot=(I-M)^{-1}
</math>
<math>
m_{ij}=\frac{f_{ij}}{\sum_{j=1}^{N+1}f_{ij}}
</math>，
基础矩阵<math>
U=I+M+M^2+\cdot\cdot\cdot=(I-M)^{-1}
</math>
i到j的总流：<math>
t_{i,j}=T_0\frac{u_{0,i}u_{i,j}}{u_{i,i}}
</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>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>。