網(wǎng)絡(luò)最大流算法與應(yīng)用研究.pdf

1、網(wǎng)絡(luò)最大流問題在科學(xué)和工程等領(lǐng)域應(yīng)用廣泛，許多線性規(guī)劃的實(shí)際問題都可轉(zhuǎn)化為網(wǎng)絡(luò)最大流的模型來求解，密切了圖論與線性規(guī)劃問題，開辟了圖論應(yīng)用的新途徑。隨著交通、電力、物流等大規(guī)模發(fā)展以及計(jì)算機(jī)技術(shù)的廣泛應(yīng)用，人們對(duì)最大流問題的研究越來越深入，逐漸建立了較為完善的理論，提出了一系列的算法。本文針對(duì)現(xiàn)有的求解網(wǎng)絡(luò)最大流算法存在的步驟繁復(fù)、計(jì)算量大、由于增廣鏈選取的順序不當(dāng)而無法得到理想的最大流等問題，主要做了如下工作：
　　（1）提出了

2、一種基于深度優(yōu)先的網(wǎng)絡(luò)最大流算法，該算法的基本思想就是利用分層網(wǎng)絡(luò)的概念和DFS原理，并加入終止符的概念，在一個(gè)網(wǎng)絡(luò)圖上就可以完成整個(gè)求解最大流的過程，改進(jìn)后的方法有效的提高了算法的效率，最后通過具體實(shí)例驗(yàn)證了該方法的性能與實(shí)用性。
　?。?）引入頂點(diǎn)度的概念提出了一種基于頂點(diǎn)度的網(wǎng)絡(luò)最大流算法。算法的主要思想就是在增廣鏈算法的基礎(chǔ)上，引入頂點(diǎn)度的概念來選擇增廣鏈。改進(jìn)后的方法更加直觀，計(jì)算方便，穩(wěn)定性更強(qiáng)。
　?。?）深入