[發(fā)明專利]一種基于相互關系表求解復雜網(wǎng)絡最大流的方法

在審

• 申請?zhí)枺?/td>: 201410368344.8
• 申請日: 2014-07-30
• 公開（公告）號: CN104217101A
• 公開（公告）日: 2014-12-17
• 發(fā)明（設計）人: 侯開虎;朱栩穎;楊維平;陳婷;張飛;曹麗銀
• 申請（專利權）人: 昆明理工大學
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于相互關系表求解復雜網(wǎng)絡最大流的方法，其特征在于：首先通過網(wǎng)絡圖轉換出唯一對應確定關系的相互關系表；然后根據(jù)相互關系表依次尋求相應的一條通路；接著將得到的相應通路上的每一個流量減去相應通路上的基流量，得到新的相互關系表；再根據(jù)得到的新相互關系表，重復尋求相應的通路，直到不能尋找到通路為止；最后把所有通路的基流量進行累加操作，則得到對應網(wǎng)絡圖的最大流量。

2.根據(jù)權利要求1所述的基于相互關系表求解復雜網(wǎng)絡最大流的方法，其特征在于：所述方法的具體步驟如下：

Step1、通過網(wǎng)絡圖轉換出唯一對應確定關系的相互關系表；其中，相互關系表為根據(jù)網(wǎng)絡圖中n個可達點構建n-1行、n-1列的二維對應關系表，二維對應關系表以可達點起始點處開始表格數(shù)從1個依次在步長為1的情況下遞增至n-1個，二維對應關系表對應表格中的數(shù)值為任意兩個可達點沿著對應行X_i（i=0,…n-2)以及對應列Y_j(j=1,…n-1)方向的交點處所表示的網(wǎng)絡圖中的流量值????????????????????????????????????????????????；可達點V_l（l=0,…n-2）對應的行為X_i（i=0,…n-2)，Y_j(j=1,…n-1)對應的可達點為V_m（m=1,…n-1）；

Step2、從起始點V₀開始，在它所在的X₀行中找到任意一個；

Step3、從所在的Y_j列對應的可達點V_m出發(fā)，選取V_m對應行X_i中任意一個正的；或者從所在的Y_j列中選取任意一個負的，再接著從所在的X_i行中選取任意一個正的；

Step4、從所在的Y_j列對應的可達點V_m出發(fā)，選取V_m對應行X_i中任意一個負的；或者從所在的Y_j列中選取任意一個負的，再接著從所在的X_i行中選取任意一個正的；

Step5、重復執(zhí)行步驟Step4，直到所在的Y_j列為Y_n-1，則得到相應的一條通路；

Step6、將得到相應通路上的每一個流量減去相應通路上基流量，得到新的相互關系表；

Step7、根據(jù)得到的新相互關系表，重復執(zhí)行步驟2-6，直到不能尋找到通路為止；

Step8、把所有通路的基流量進行累加操作，則得到對應網(wǎng)絡圖的最大流量。

3.根據(jù)權利要求2所述的基于相互關系表求解復雜網(wǎng)絡最大流的方法，其特征在于：所述基流量為相應通路上的最小流量。

4.根據(jù)權利要求3所述的基于相互關系表求解復雜網(wǎng)絡最大流的方法，其特征在于：所述最小流量為相應通路上的每一個流量轉換成絕對值后的比較。