拾人花卉，系之一束；他供鮮花，我獻彩帶。
Montaigne

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

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