最大流算法的仿真與分析.pdf

1、網(wǎng)絡(luò)最大流決定了網(wǎng)絡(luò)的容量，所以研究網(wǎng)絡(luò)最大流具有較大實際意義。關(guān)于最大流的研究通常會涉及到解決最大流問題的方法，最大流問題是指尋找源節(jié)點與匯節(jié)點之間的最多流，在研究這個問題之前，有必要對標(biāo)志網(wǎng)絡(luò)中最大流的值等于是這個網(wǎng)絡(luò)的最小切割流量的一些概念進行解釋，如最小切割和最大流最小切割定理。
　　 本文的主要工作集中在三個最大流算法的理論和實際比較：對于尋找最大瓶頸值和最少邊的增廣路徑非常有用的Edmonds-Karp算法、構(gòu)建于推

2、和重標(biāo)簽這兩個特定操作基礎(chǔ)之上的push-relabel算法，以及分解為成長、增廣和采用三個階段的Kolmogorov算法。
　　 采用四種網(wǎng)絡(luò)仿真許多不同的場景來得到一些結(jié)果，本文揭示了如何計算最大流和最小切割、流守恒定律是如何得到滿足的、如何獲得剩余圖以找到增廣路徑，同樣成功的提供了一個對最大流最小切割定理的實際仿真。本文指出當(dāng)在計算網(wǎng)絡(luò)中的最大流時，每個用于計算最大流的算法之間會產(chǎn)生一些差別，基于這些現(xiàn)象，在某一個算法在計