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

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

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