拾人花卉，系之一束；他供鮮花，我獻(xiàn)彩帶。
Montaigne

網(wǎng)絡(luò)流方面的任何新書似乎都應(yīng)說明其存在的合理性，因?yàn)樵擃I(lǐng)域的權(quán)威著作早已出版。我所參考的書籍《網(wǎng)絡(luò)流：理論、算法和應(yīng)用》(Network Flows: Theory, Algorithms, and Applications) 已于 1993 年出版。該書作者為 Ahuja、Magnanti 和 Orlin[4]，他們是網(wǎng)絡(luò)流算法領(lǐng)域理論研究和實(shí)踐應(yīng)用的先驅(qū)。我用該書作者姓名的首字母 AMO 來代表此書。20 世紀(jì) 80 年代末至 90 年代初是研究網(wǎng)絡(luò)流問題的組合算法和多項(xiàng)式算法的黃金時(shí)期。AMO 不僅討論了當(dāng)時(shí)已完成的大部分研究，還給出了網(wǎng)絡(luò)流領(lǐng)域的廣泛綜述，其內(nèi)容貫穿網(wǎng)絡(luò)流理論研究和實(shí)際應(yīng)用。既然如此，為何還需寫此書？我有下面三方面的理由。
：關(guān)注點(diǎn)問題。我在寫另一領(lǐng)域的嚴(yán)謹(jǐn)性書籍 [206] 時(shí)意識(shí)到，書籍內(nèi)容很難兼顧準(zhǔn)確嚴(yán)謹(jǐn) 和 簡(jiǎn)潔明了。AMO 無疑是前者，本書的目標(biāo)是后者。本書主要關(guān)注網(wǎng)絡(luò)流問題的組合算法、多項(xiàng)式算法及其分析。在康奈爾大學(xué)運(yùn)籌學(xué)和信息工程學(xué)院任教期間，我教過幾次網(wǎng)絡(luò)流算法方面的研究生課程，本書內(nèi)容源于對(duì)這些課程內(nèi)容的提煉。該課程主要面向運(yùn)籌學(xué)和計(jì)算機(jī)科學(xué)系的學(xué)生，也有電氣和土木工程系的部分學(xué)生。從教學(xué)觀點(diǎn)來看，需做點(diǎn)取舍，以保證本書的大部分內(nèi)容可在一學(xué)期內(nèi)講完。
此外，由于本書是課堂教學(xué)的成果，其涵蓋的知識(shí)點(diǎn)是一次授課所能講完的內(nèi)容。因此，太長(zhǎng)或太復(fù)雜而無法在一次授課中講完的知識(shí)點(diǎn)，本書都不涵蓋。我不太關(guān)注網(wǎng)絡(luò)流理論中的某些領(lǐng)域，比如沒有多項(xiàng)式運(yùn)行時(shí)間的網(wǎng)絡(luò)流應(yīng)用和算法等。對(duì)于本書未涉及的某些網(wǎng)絡(luò)流理論部分，感興趣的讀者可參閱 AMO。
第二：提供一些 AMO 沒有涉及的知識(shí)。對(duì)流問題和小代價(jià)環(huán)流問題，雖然本書所提的算法 AMO 也有涉及，但本書給出了一些重要的特殊情形。如前所述，雖然 20 世紀(jì) 80 年代末至 90 年代初是研究網(wǎng)絡(luò)流算法的黃金時(shí)代，但該領(lǐng)域在過去 25 年里的研究成果是 AMO 無法涵蓋的。
1998 年，Goldberg 和 Rao 所發(fā)表的論文 [98] 就是一個(gè)著名的研究成果。對(duì)流問題，他們給出了至今為止在理論上仍被認(rèn)為快的算法。1991 年，Wallacher[201] 關(guān)于小代價(jià)環(huán)流問題的算法是另一個(gè)研究成果，該算法具有相當(dāng)簡(jiǎn)單的分析。此外，AMO 出版時(shí)，針對(duì)某些流問題，一些多項(xiàng)式算法正好脫穎而出。顯然，AMO 無法涵蓋這些算法。
我主要思考的是全局小割集、廣義流和多物流等問題的算法。近年來，內(nèi)點(diǎn)方法在網(wǎng)絡(luò)流問題的特殊應(yīng)用中產(chǎn)生了一些快速算法，但這些算法不是組合算法，因此，它們不在本書的選取范圍內(nèi)。本書還包含了一些與電流經(jīng)典主題相關(guān)的成果。
第三：情不自禁。我的主要研究興趣是組合算法和多項(xiàng)式算法，但在網(wǎng)絡(luò)流領(lǐng)域，除有一項(xiàng)研究成果外 [173]，幾乎一無所獲。所以，作為一位公正的旁觀者，我可以說，該領(lǐng)域是一個(gè)優(yōu)美且存在一些有用算法思想的領(lǐng)域，這些算法思想以一種令人愉悅的方式相互支持著。
用前面引述的 Montaigne 的話來說，寫本書的目的就是做選擇和重組，盡我所能地展現(xiàn)一些算法及其分析的美妙之處。希望讀者和我一樣欣賞這終呈現(xiàn)的花束。

David P. Williamson
紐約，伊薩卡
2019 年 1 月