畢業(yè)設(shè)計---最大流問題及應(yīng)用

1、<p>　　本科畢業(yè)設(shè)計（論文）</p><p>　　題 目 最大流問題以及應(yīng)用 </p><p>　　學 院 名 稱 數(shù)學與系統(tǒng)科學學院 </p><p>　　專業(yè)班級 </p><p>　　學生姓名 <

2、;/p><p>　　學 號 </p><p><b>　　摘要</b></p><p>　　網(wǎng)絡(luò)流問題是運籌學的重要研究課題。最大流問題是網(wǎng)絡(luò)流問題的一個重要的內(nèi)容，應(yīng)用極為廣泛。研究最大流問題并將其應(yīng)用到工業(yè)、工程、商業(yè)、農(nóng)業(yè)，運輸業(yè)等領(lǐng)域可給我們的生活帶來很大方便。 </p>

3、<p>　　本論文討論最大流問題，綜述圖論的歷史背景、基本概念和基本知識；闡述網(wǎng)絡(luò)的基本概念；介紹最大流問題的核心依據(jù)——Ford-Fulkerson最大流最小割定理；綜述解決最大流問題的 幾種算法Ford-Fulkerson標號法、Edmonds-Karp修正算法、Dinic算法，并比較各算法在解決不同問題中的優(yōu)劣。</p><p>　　為了更加明確的展現(xiàn)最大流問題在生產(chǎn)生活中的應(yīng)用，本文例舉了一個實

4、際生活中的問題——鐵路貨運列車的最優(yōu)調(diào)度來突出研究最大流問題的重要意義，此實例需要求解的是在一定的限制條件下，設(shè)計出一個在一晝夜間能通過某段鐵路的最多的貨運列車數(shù)量并列出每 輛列車開出的時刻表。在此實例中，通過從實際問題中抽象出網(wǎng)絡(luò)圖，將實際問題轉(zhuǎn)化為最大流問題并應(yīng)用圖的性質(zhì)和Ford-Fulkerson標號法的算法依據(jù)，最終解決了問題。</p><p>　　本文采用理論與 實例相結(jié)合，重在應(yīng)用理論依據(jù)解決實際問

5、題，具有較強的實踐性，突出的是應(yīng)用。</p><p><b>　　Abstract</b></p><p>　　The network flow problem is an important operational research subject. The maximum flow problem is an important content of networ

6、k flow problem, which has widely applications. The research of maximum flow problem and its applications to industry, engineering，commerce, agriculture, transportation and other areas can bring us great convenience. <

7、/p><p>　　The paper discusses the maximum flow problem, and summarizes the historical background of graph theory, basic concepts, basic knowledge and describes the basic concept of the network. The core basis of

8、 the maximum flow problem -- Ford-Fulkerson maximum flow minimum cut theorem is introduced. Several algorithms for solving maximal-flow problem like Ford-Fulkerson labeling algorithm, Edmonds-Karp correct algorithm, Dini

9、c algorithm are summarized in this paper. It also compares various algorithms t</p><p>　　In order to more clearly show the application of the maximum flow problem in the production life, the paper illustrate

10、s a real-life problem - -The optimal scheduling of railway freight train to highlight the importance of maximum flow. This instance is to be solved under certain constraints , to design the most freight train numbers thr

11、ough the railway in a day and night and to list out the schedules for each train. In this instance, by abstracting the network diagram from the real problems, tra</p><p>　　In this paper, the combination of t

12、heory and examples focus on solving practical problems by applying theoretical basis. It has strong practicality and highlights the applications. 字典</p><p>　　Keywords： Graph Network flow Maximum flow <

13、;/p><p><b>　　目錄</b></p><p><b>　　第一章 緒論1</b></p><p>　　1.1 最大流問題的研究內(nèi)容及背景1</p><p>　　1.2 最大流問題的發(fā)展狀況1</p><p>　　1.3 選題的意義2</p>&l

14、t;p>　　第二章 預(yù)備知識4</p><p><b>　　2.1 圖論4</b></p><p>　　2.2 網(wǎng)絡(luò)的基本概念6</p><p>　　2.3 最大流問題核心依據(jù)——Ford-Fulkerson最大流最小割定理7</p><p>　　第三章 最大流問題的幾種算法9</p>

15、<p>　　3.1 標號法(Ford-Fulkerson算法)9</p><p>　　3.2 Edmonds-Karp修正算法11</p><p>　　3.3 Dinic算法15</p><p>　　第四章 最大流問題的應(yīng)用19</p><p>　　4.1 鐵路貨運列車的最優(yōu)調(diào)度19</p><

16、p>　　第五章 結(jié)論30</p><p>　　參 考 文 獻31</p><p><b>　　致謝辭32</b></p><p>　　附錄1英文原文33</p><p>　　附錄2中文譯文37</p><p><b>　　第一章 緒論 </b></p

17、><p>　　1.1 最大流問題的研究內(nèi)容及背景</p><p>　　最大流問題也就是是指網(wǎng)絡(luò)分析問題的一類，它是在指定的條件下,要求通過網(wǎng)絡(luò)的物流、能量流、信息流等流量為最大的問題。比如交通運輸網(wǎng)絡(luò)中的人流、車流、物流,供水網(wǎng)絡(luò)中的水流、金融系統(tǒng)中的現(xiàn)金流通信系統(tǒng)中的信息流等等，都屬于最大流問題。</p><p>　　圖論是組合數(shù) 學的—個分支與其他的數(shù)學分支如群論、

18、矩陣論、概率論、拓撲學、數(shù)值分析有著密切的聯(lián)系而且其應(yīng)用十分廣泛，是近年來較為活躍的數(shù)學分支之一。它的產(chǎn)生和 發(fā)展歷經(jīng)了二百多年的歷史，瑞士數(shù)學家歐拉(L．Euler)在1736年解決了當時頗為有名的一個數(shù)學難題，即哥尼斯城堡七橋問題，從而使他成了圖論和拓撲學的創(chuàng)始人。早期的圖論與數(shù)學游戲有密切的聯(lián)系，如哈密爾頓 的周游世界問題、迷宮問題、博奕問題以及棋盤上馬的行走路線之類的難題等吸引了許多學者。20世紀后，圖論的應(yīng)用滲透到許多其他學科

19、領(lǐng)域，如物理、化學、信息學、運籌學、博奕論、計算機網(wǎng)絡(luò)、社會學以及集合論、矩陣論等。從20世紀50年代以后，由于計算機的迅速發(fā)展，有力地推動了圖論的發(fā)展，使圖論成為數(shù)學領(lǐng)域中發(fā)展最快的分支之一，也成為現(xiàn)代研究最大流問題的一個重要工具。</p><p>　　1.2 最大流問題的發(fā)展狀況</p><p>　　最大流問題是早期的線性網(wǎng)絡(luò)最優(yōu)化的一個例子。最早研究這類問題的是美國學者希奇柯克（Hi

20、tchcock），1941年他在研究生產(chǎn)組織和鐵路運輸方面的線性規(guī)劃問題時提出運輸問題的基本模 型；后來柯普曼（Koopmans）在1947年獨立地提出運輸問題并詳細地對此問題加以討論；從上世紀40年代早期開始，康脫洛維奇（Kantorovich）圍繞著運輸問題作了大量的研究，因此運輸問題又稱為希奇柯克問題或康脫洛維奇問題。與 一般線性規(guī)劃問題不同，它的約束方程組的系數(shù)矩陣具有特殊的結(jié)構(gòu)，這就需要采用不同的甚至更為簡便的求解方法來解決這

21、種在實際工作中經(jīng)常遇到的問題。運輸問題不僅代表了物資合理調(diào)運、車輛合理調(diào)度等問題，有些其他類型的問題經(jīng)過適當變換后也可以歸結(jié)為運輸問題。后來把這種解決線性網(wǎng)絡(luò)最優(yōu)化的方法與最大流問題相結(jié)合，同時推動了最大流問題的發(fā)展。</p><p>　　最大流問題就是就是在一個有向連通圖中，指定一點為發(fā)點，另一點</p><p>　　為收點，其余的點為中間點，在所有的點 都能承載的情況下能通過此網(wǎng)絡(luò)圖的

22、最大可行流，即發(fā)點發(fā)往收點的最大可行流。本課題的意義在于掌握最大流問題的基本理論和算法來解決實際應(yīng)用問題，提高生產(chǎn)的有效性和生產(chǎn)設(shè)備的有效利用率。</p><p>　　最大流問題應(yīng)用極為廣泛，很多生活中的問題都可轉(zhuǎn)化為最大流問題，其難點是從實際中抽象出最大流模型，即轉(zhuǎn)化問題，且實踐性較強，通過實例分析，更有利于對最大流問題的了解與應(yīng)用。</p><p><b>　　1.3 選題的

23、意義</b></p><p>　　在日常生活和生產(chǎn)中我們時常遇到一些網(wǎng)絡(luò)圖。如交通圖、旅游線路圖、管道系統(tǒng)圖等。在優(yōu)化理論 中所謂圖就是上述各類圖的抽象和概括，用圖來描述我們的研究對象，以及這些對象之間的相互聯(lián)系。例如旅游管理、網(wǎng)絡(luò)通信、交通運輸、金融系統(tǒng)等問題都可以用網(wǎng)絡(luò)圖來描述。</p><p>　　最大流問題就是就是在一個有向連通圖中，指定一點為發(fā)點，另一點為收點，其余的

24、點為中間點，在所有的點 都能承載的情況下能通過此網(wǎng)絡(luò)圖的最大可行流，即發(fā)點發(fā)往收點的最大可行流。本課題的意義在于掌握最大流問題的基本理論和算法來解決實際應(yīng)用問題，提高生產(chǎn)的有效性和生產(chǎn)設(shè)備的有效利用率。</p><p>　　最大流問題應(yīng)用極為廣泛，很多生活中的問題都可轉(zhuǎn)化為最大流問題，其難點是從實際中抽象出最大流模型，即轉(zhuǎn)化問題，且實踐性較強，通過實例分析，更有利于對最大流問題的了解與應(yīng)用。</p>

25、<p><b>　　第二章 預(yù)備知識</b></p><p><b>　　2.1 圖論</b></p><p>　　所謂“圖論”，顧名思義也就是是研究“圖”的理論。圖論中的“圖”是由許多實際問題經(jīng)過抽象而得到，由點及點與點之間的連線構(gòu)成，它可以反映一些對象之間的關(guān)系。圖形中的點表示對象(如工序、選手、通訊站等)，兩點之間的有向或無向連

26、線表示對象之間具有某種特定的關(guān)系(如先后關(guān)系、勝負關(guān)系、傳遞關(guān)系、連接關(guān)系等)。</p><p>　　物質(zhì)結(jié)構(gòu)、電路網(wǎng)絡(luò)、城市規(guī)劃、交通運輸、信息傳遞、物資調(diào)配等都可以用點和線連 接起來的圖進行模擬。這里所研究的圖與平面幾何中的圖不同，這里只關(guān)心圖中有多少個點，點與點之間有無連線，至于連線的方式是直線還是曲線，點與點的相對位置如何，都是無關(guān)緊要的。</p><p>　　定義1：兩點之間不帶

27、箭頭的連線稱為邊，一條連接的邊記為 (或)，表示邊的集合。</p><p>　　定義2：兩點之間帶箭頭的連線稱為弧，一條以為始點</p><p>　　為終點的弧記為表示弧的集合。</p><p>　　定義3：由點和邊構(gòu)成的圖為無向圖，記為；由點和弧構(gòu)成的圖為有向圖，記為.</p><p>　　定義4：在無向圖中，若存在一個點邊交錯序列，滿足&

28、lt;/p><p>　　，則稱之為一條聯(lián)結(jié)和的鏈，記為,若，則稱之為圈。</p><p>　　定義5：在有向圖中，若存在一個點弧交錯序列，弧的始點為，終點為，記為，則稱這條點弧的交錯序列為從到的一條路，記為。若路的第一點和最后一點相同，則稱之為回路。鏈與路中的點互不相同，則為初等鏈(路)，以后說到的鏈與路，均指初等鏈(路)。</p><p>　　定義6：如果對于一個無向

29、圖的每一條邊，相應(yīng)有一個權(quán)數(shù)，則稱這樣的圖為賦權(quán)圖，記為。</p><p>　　定義7：如果對于一個有向圖的每一條弧，相應(yīng)有一個權(quán)數(shù)，稱這樣的圖為網(wǎng)絡(luò),記為。</p><p>　　一般在網(wǎng)絡(luò)圖中，每條弧的權(quán)，不是表示弧的長度、而是表示弧的寬度，即代表距離、費用、通過能力(容量)等等。例如，公路運輸網(wǎng)絡(luò)中路面的寬度或管道輸送網(wǎng)絡(luò)中管道的直徑，它是單位時間內(nèi)允許通過實體的數(shù)量。所以將弧權(quán)稱為弧

30、的容量，網(wǎng)絡(luò)稱為容量網(wǎng)絡(luò)（參見文獻[17]）。</p><p>　　定義8：在圖中，若任何兩個點之間至少有一條鏈（或一條路），則稱是連通圖，否則，稱為不連通圖。</p><p>　　2.2 網(wǎng)絡(luò)的基本概念</p><p>　　假設(shè)要把起點的一批流轉(zhuǎn)物運送到終點去，在每一弧上通過流轉(zhuǎn)物的總量不能超過這條弧上的容量，問題是應(yīng)該怎樣安排運送，才能使從起點運送至終點的總量達

31、到最大，這樣的問題就稱為網(wǎng)絡(luò)上最大流問題，最大流問題是網(wǎng)絡(luò)流問題中的一個非常重要的研究內(nèi)容（參見文獻[15]），以下討論的網(wǎng)絡(luò)均為只有一個發(fā)點和一個收點的容量網(wǎng)絡(luò)。</p><p>　　定義9：對任意容量網(wǎng)絡(luò)中的弧有流量，稱集合為網(wǎng)絡(luò)上的一個流，稱滿足下列條件的流為可行流：</p><p>　　(1)容量限制條件：對中每條弧，有；</p><p><b>

32、　　(2)平衡條件：</b></p><p>　?、賹χ虚g點，有(即中間點的物資的輸入量與輸出量相等)。</p><p>　?、趯κ?、發(fā)點有(即從點發(fā)出的物資總量等于點入的量) ，為網(wǎng)絡(luò)流的總流量。</p><p>　　在容量網(wǎng)絡(luò)中表示弧的容量，令為通過弧的流量，顯然有，流應(yīng)遵守點守恒規(guī)則，即：</p><p><b>

33、　　稱為守恒方程。</b></p><p>　　定義10：對任意容量網(wǎng)絡(luò)，尋求一可行流使得流量取得</p><p>　　極大值，這個可行流便稱為最大流。</p><p>　　定義11：在容量網(wǎng)絡(luò)中，若為網(wǎng)絡(luò)中從發(fā)點到收點的一條路，給定向為從到，上的弧凡與同向稱為前向弧。凡與反向稱為后向弧，其集合分別用和表示，是一個可行流，如果滿足</p>

34、<p>　　則稱為從到的(關(guān)于的)增廣鏈。</p><p>　　定義12：在容量網(wǎng)絡(luò)中，若有弧集為的子集，將分為兩個子圖，其頂點集合分別記，，分別屬于，滿足：①不連通；②為的真子集，而仍連通，則稱為的割集，記。</p><p>　　割集中所有始點在，終點在的邊的容量之和，稱為的割集容量，記為。</p><p>　　2.3 最大流問題核心依據(jù)——Ford-

35、Fulkerson最大流最小割定理</p><p>　　Ford-Fulkerson最大流最小割定理是由Ford和Fulkerson在1956年提出的，是圖論的核心定理。</p><p>　　定理1：（Ford-Fulkerson最大流最小割定理）任一容量網(wǎng)絡(luò)中，從到</p><p>　　的最大流的流量等于分離的最小割的容量。</p><p>

36、;　　證明：設(shè)在中從到的任一可行流的流量為，最小割集為</p><p>　　，最小割集的容量為。這個定理的證明分兩步：</p><p><b>　?、?我們先證明：</b></p><p><b>　　由守恒方程可得：</b></p><p><b>　　因此有：。</b>&l

37、t;/p><p>　　⑵ 下面我們證明一個可行流是最大流，當且僅當不存在關(guān)于它的從到的增廣路徑：</p><p>　　必然性：顯然，因為如果存在增廣路徑，還可以繼續(xù)增廣，流就不是最大流。</p><p>　　充分性：假設(shè)可行流是一個不存在關(guān)于它的增廣路徑的流，對于最小割集，有對任意，存在從到的增廣路徑，而對任意，不存在從到的增廣路徑，由定義可知對任意有：</p&g

38、t;<p><b>　　由公式可知：。</b></p><p>　　即流的值等于割集的容量，定理得證。</p><p>　　第三章 最大流問題的幾種算法</p><p>　　最大流問題是社會經(jīng)濟生活和軍事活動中經(jīng)常出現(xiàn)的優(yōu)化問題。如在經(jīng)濟建設(shè)和國防建設(shè)中，經(jīng)常遇到一些物資調(diào)運的問題。如何制定調(diào)運方案，將物資盡快運到指定點，而且不

39、影響費用的計劃開銷，即為最大流問題。下面用數(shù)學語言來說明最大流問題：</p><p>　　1.設(shè)有一個有向連通圖G(V,A)，在V中指定一點稱為發(fā)點s,和另外一點為收點t，其余的稱為中間點，?。╝rc）集A中每條?。╥，j）上有非負數(shù)稱為這弧的容量，記容量集為c={}，稱這樣的圖為一個網(wǎng)絡(luò)，記為G(V,A,c)（注：當（i，j）不是弧時=0）。</p><p>　　2.在弧集A上的弧（i

40、，j）定義一非負數(shù)，稱為?。╥，j）上的流量，流量的集合f={}稱為網(wǎng)絡(luò)的一個流，滿足下列條件的稱為可行流：</p><p>　　1）容量限制條件，所有的弧的流量不大于弧的容量；</p><p>　　2）平衡條件，對所有的中間點，流入的流量和等于流出的流量和，發(fā)點流出的流量F等于流進收點的總流量F.</p><p>　　最大流問題就是求總流量最大達可行流。</

41、p><p>　　求解最大流問題存在許多算法，這一節(jié)將介紹幾種常用算法。</p><p>　　3.1 標號法(Ford-Fulkerson算法)</p><p>　　3.1.1標號法(Ford-Fulkerson算法)思想</p><p>　　Ford-Fulkerson標號法是一種找最大流的算法。它是由Ford和Fulkerson于1957年最

42、早提出的，其基本思想是從任意一個可行流出發(fā)尋</p><p>　　找—條增廣路徑，并在這條增廣路徑上增加流量，于是便得到一個新的可行流，然后在這新的可行流的基礎(chǔ)上再找一條新的增廣路徑，再增加流量……，繼續(xù)這個過程，一直到找不到新的增廣路徑為止（參見文獻[2]）。</p><p>　　采用Ford-Fulkerson標號法求解最大流問題時，在標號過程中，一個點僅有下列三種狀態(tài)之一：標號已檢查

43、(有標號且所有相鄰點都標號了)；標號未檢查(有標號，但某些相鄰點未標號)；未標號（參見文獻[6]）。</p><p>　　Ford-Fulkerson標號算法分為兩個過程：一是標號過程，通過標號過程找到一條增廣路徑；二是增廣過程，沿著增廣路徑增加網(wǎng)絡(luò)流流量的過程（參見文獻[18]）?，F(xiàn)在我們考慮只有一個發(fā)點和一個收點的容量網(wǎng)絡(luò)，應(yīng)用Ford-Fulkerson標號算法求解它的最大流</p><

44、p>　　3.1.2 Ford-Fulkerson標號法的具體步驟</p><p><b>　　A:標號過程</b></p><p>　　步驟0 確定一初始可行流，可以是零流。</p><p>　　步驟1 給發(fā)點以標號。</p><p>　　步驟2 選擇一個已標號但未檢查的點，并作如下檢查：</p

45、><p>　　對每一弧，若未給標號，而且時，即流出未飽和弧,給以標號；</p><p>　　對每一弧，若未給標號，而且時，即流入非零流弧，給以標號；</p><p><b>　　其中：</b></p><p>　　步驟3 重復(fù)步驟2直到收點被標號，或不再有頂點可以標號為止。</p><p>　　如

46、果點給了標號說明存在一條增廣路徑，故轉(zhuǎn)向增廣過程B。如若點不能獲得標號，而且不存在其它可標號的頂點時，算法結(jié)束，所得到的流便是最大流。</p><p><b>　　B：增廣過程</b></p><p>　　由終點開始，使用標號的第二個元素構(gòu)造一條增廣路徑(點的標號的第二個元素表示在路中倒數(shù)第二個點的下標，而這第二個點的標號的第二個元素表示倒數(shù)第三個點的下標等等)，在上

47、作調(diào)整得新的可行流，(標號的第二個元素的正負號表示通過增加或減少弧流來增大流值)。令為標號的第一個元素的值，作</p><p>　　以新的可行流代替原來的可行流，去掉所有標號，轉(zhuǎn)標號過程的步驟1。</p><p>　　采用Ford-Fulkerson標號算法求解最大流問題，同時得到一個最小割集。最小割集的意義是：網(wǎng)絡(luò)從發(fā)點到收點的各個通路中，由容量決定其通過能力，通常我們將最小割集形象地稱

48、為這些通路的咽喉部分，或叫做“瓶頸”，它決定了整個網(wǎng)絡(luò)的通過能力，即最小割集的容量的大小影響總的流量的提高。因此，為提高總的流量，必須首先考慮改善最小割集中各小弧的流量，提高它們的通過能力（參見文獻[14]）。</p><p>　　3.2 Edmonds-Karp修正算法</p><p>　　Ford-Fulkerson標號算法理論上存在著嚴重的弱點，以下圖3.2.1為例各邊上的權(quán)是它們

49、的容量，其最大流流量為，若增廣路徑選擇得不好,即交替地采用和作為增廣路徑，則每次增廣只能使總的流量增加1,當初始流選為零流，無疑需作次的增加流量才能使之達到最大，可見Ford-Fulkerson算法的時間復(fù)雜度不僅依賴于網(wǎng)絡(luò)的規(guī)模(即依賴于網(wǎng)絡(luò)點數(shù)和邊數(shù))，還和各邊的容量有關(guān),而容量可以是任意的正整數(shù)。如圖3.2.1中，當和交替作為增廣路徑時，弧交替地以前向弧和后向弧出現(xiàn)。利用Ford-Fulkerson算法求解就很麻煩了（參見文獻[8

50、]）。</p><p>　　對于Ford-Fulkerson算法,由于增廣路徑選取的任意性造成了該算法不是好算法，Edmonds和Karp對Ford-Fulkerson算法作修正，可概括為一句話：“先給標號的先掃描”。它的意思是對已給標號的頂點進行掃描時，先對所有和鄰接的未給標號的頂點給予標號。具體的說圖3.2.1的例子，頂點先標記，所以應(yīng)該先掃描，因此避免了Ford-Fulkerson算法那樣交替地出現(xiàn)的情況，

51、也就避免了弧交替地以前向弧和后向弧來回搖擺的局面。所以Edmonds-Karp的修正實質(zhì)是對頂點給標記過程采用了“寬度優(yōu)先”策略。使得流量增加總是沿著一條長度最短的路徑從流向的（參見文獻[3]）。</p><p>　　現(xiàn)在我們?nèi)钥紤]只有一個發(fā)點和一個收點的網(wǎng)絡(luò)圖，Edmonds-Karp修正算法的主要步驟是：</p><p>　　確定一初始可行流，其流量。</p><p

52、>　　檢驗當前所確定可行流是否是網(wǎng)絡(luò)中的最大流，若不是，需進一步調(diào)整(檢驗一個可行流是否為最大流。只要檢查一下當前可行流是否還存在增廣路徑，若存在，則說明當前可行流還不是最大流，否則是最大流)。</p><p>　　將當前的可行流調(diào)整成一個流量更大的新可行流，再由②檢驗。</p><p>　　同樣地，我們通常用觀察法確定網(wǎng)絡(luò)的—個初始可行流。對于較為復(fù)雜的網(wǎng)絡(luò)，至少能把初始可行流取為

53、零流。通過在網(wǎng)絡(luò)上標號的方法能系統(tǒng)地尋找出當前可行流的增廣路徑，它的基本思想是：從起點起，逐步尋找至各點間的增廣路徑，若能找到至的一條增廣路徑，則給點標號（其中第一個標號即為至這條增廣路徑上的最大可調(diào)整量，第二個標號則表示這條可行流上點的前一點是點）。根據(jù)標號可反向追蹤而寫出這條增廣路徑。在逐步擴大已標號的過程中，一旦終點標上號，表示已找到一條由至的增廣路徑。反之，如果標號過程進行至某一步中止了，而尚未標號，則表明對當前的可行流，網(wǎng)絡(luò)中

54、不存在任何增廣路徑。當前可行流即為最大流。Edmonds-Karp修正算法的具體步驟如下：</p><p>　　給發(fā)點標號，含義為至的增廣路徑已找到，前一點為，這條增廣路徑上的調(diào)整量為。選與關(guān)聯(lián)的從流出的未飽和弧或流入的非零流弧，給標號 (對于流出弧)或 (對于流入弧)。</p><p><b>　　其中：</b></p><p>　　將頂點集

55、分為互補的二個點集、，其中為已標號點集，為未標號點集；</p><p>　　考慮所有這樣的弧或，其中。若弧為從流出的未飽和弧，則給標號。其中；若弧為流入的非零流弧，則給標號。其中。依此進行，得到的結(jié)果是： </p><p>　　(a)，說明網(wǎng)絡(luò)中存在增廣路徑，則由標號點反向追蹤找出，轉(zhuǎn)第④步；</p><p>　　(b)，標號已進行不下去，說明對于當前可行流。網(wǎng)絡(luò)中

56、已無新的增廣路徑，當前可行流即為最大流，同時得到最小割集。</p><p><b>　　調(diào)整過程：取，令</b></p><p>　　得到新可行流，流量，即比原可行流流量增加了，再轉(zhuǎn)①步。</p><p>　　用Edmonds-Karp修正算法求解最大流問題時，也可以得到一個最小割集。最小割集的意義同F(xiàn)ord-Fulkerson算法得到的最小割

57、集的意義相同。</p><p>　　3.3 Dinic算法</p><p>　　Dinic于1970年提出了Ford-Fulkerson算法的改進算法，Dinic算法的特點是將頂點按其與發(fā)點的最短距離分層。Edmonds-Karp修正算法的實質(zhì)也是一種分層，如果說Ford-Fulkerson算法是采用了深度優(yōu)先策略。Edmonds-Karp修正算法則是用寬度優(yōu)先取代了深度優(yōu)先，Dinic

58、算法則是兼取這兩種方法。在分層時用的寬度優(yōu)先法，而尋求增廣路徑時則采用深度優(yōu)先策略（參見文獻[3]）。</p><p>　　3.3.1 增量網(wǎng)絡(luò)與分層增量網(wǎng)絡(luò)</p><p>　　定義13：給定一個帶發(fā)點和收點的容量網(wǎng)絡(luò)及上的可行流后，我們定義，因為中任何一對頂點之間至多有一條弧，所以，記，并且對一切令，于是得一個帶發(fā)點和收點的容量網(wǎng)絡(luò)，稱之為的關(guān)于可行流的增量網(wǎng)絡(luò)。</p>

59、<p>　　為了介紹分層增量網(wǎng)絡(luò)，我們先來介紹關(guān)于網(wǎng)絡(luò)的一個算法——分層算法，它的基本思想是：</p><p>　　步驟0：把發(fā)點標為“已標號未檢查”，的層數(shù)。</p><p>　　步驟1：在已標號未檢查頂點中選取最早得到標號的頂點，轉(zhuǎn)步驟2；如果所有標號頂點都已檢查，轉(zhuǎn)步驟3。</p><p>　　步驟2：考察頂點的一切出弧，若已標號，什么也不做；否

60、則將</p><p>　　標為“已標號未檢查”，并令。當?shù)乃谐龌《伎疾焱戤叄?lt;/p><p>　　把改為已檢查，轉(zhuǎn)步驟1。</p><p>　　步驟3：如果有—些頂點沒有標號，則從到這些頂點不存在路；否則為</p><p>　　的根，為中最短路的長。</p><p>　　在增量網(wǎng)絡(luò)中應(yīng)用分層算法，可以求出從發(fā)點到其余

61、各頂點的最短路的長，就是頂點（關(guān)于發(fā)點）的層數(shù)。即就是的第層頂點。的第0層只有一個頂點，把頂點分層后，中</p><p>　　的弧又可以分為三類：</p><p>　　第一類為從第層頂點到第層頂點的弧；</p><p>　　第二類為從第層頂點到同一層頂點的弧；</p><p>　　第三類為從第層頂點到第層頂點的弧（參見文獻[5]）。</

62、p><p>　　定義14：對于帶發(fā)點和收點的容量網(wǎng)絡(luò)，設(shè)關(guān)于可行流的增量網(wǎng)絡(luò)，我們定義的子網(wǎng)絡(luò)如下：</p><p>　　則稱為的關(guān)于可行流的分層增量網(wǎng)絡(luò)。其中第0層和第層分別只有一個頂點和，的所有弧都是由第層頂點指向第層頂點。</p><p>　　3.2 Dinic算法的基本思想及具體步驟</p><p>　　Dinic算法的基本思想是：從帶

63、發(fā)點和收點的容量網(wǎng)絡(luò)的任一可行流 (例如零流)開始，構(gòu)造的關(guān)于的分層增量網(wǎng)絡(luò)，在中找一條從到的增廣路徑，對沿進行增廣得到可行流，在中刪去上容量最小的弧，并相應(yīng)修改上弧的容量，得到網(wǎng)絡(luò)，然后可以在中再找一條從到的增廣路徑，對沿進行增廣得到可行流，重復(fù)上述步驟依次得到的可行流，因為只有有限條弧，每次至少刪去一條弧，所以在有限步后必然使余下的網(wǎng)絡(luò)不再存在增廣路徑，在中的層數(shù)一定大于它在中的層數(shù)；針對重復(fù)上面的做法，在有限次增廣后一定會得到的可

64、行流，使在中的層數(shù)更大。由于的層數(shù)最多為（是網(wǎng)絡(luò)的頂點數(shù)）。因此經(jīng)過有限步后得到的可行流，中不再有的增廣鏈，這時就是的最大流。Dinic算法的具體步驟如下：</p><p>　　步驟0：在網(wǎng)絡(luò)中任意取—個可行流作為初始可行流，令。</p><p>　　步驟1：(作分層增量網(wǎng)絡(luò))根據(jù)作的增量網(wǎng)絡(luò)，再利用分層算</p><p>　　法構(gòu)造分層增量網(wǎng)絡(luò)，如果在作分層增量網(wǎng)

65、絡(luò)時得不到標號，則</p><p>　　算法結(jié)束，就是的最大流；否則轉(zhuǎn)步驟2。</p><p>　　步驟2：(尋找增廣路徑)</p><p>　?、俳o發(fā)點標號為，令。</p><p>　?、谌缭跊]有出弧，轉(zhuǎn)⑤；否則在中任取的一條出弧，轉(zhuǎn)③。</p><p>　?、墼O(shè)的標號為，其中為前面的節(jié)點，令，獲得標號 。<

66、/p><p>　?、苋绻?，轉(zhuǎn)步驟3；否則令，轉(zhuǎn)②。</p><p>　?、菰O(shè)的標號為，如果，在中刪去的所有入弧，所</p><p>　　得的網(wǎng)絡(luò)仍記為，轉(zhuǎn)②；否則置，轉(zhuǎn)步驟1。</p><p>　　步驟3：（增廣）從頂點的標號中的第二個元素反向追蹤，求出的增廣路徑，在中把上的每條弧的容量改為，刪去容量為0的弧，同時把流增廣為流，把中修改容量和刪去

67、弧后的網(wǎng)絡(luò)記為，置，去掉網(wǎng)絡(luò)中所有頂點的標號，轉(zhuǎn)步驟2。</p><p>　　第四章 最大流問題的應(yīng)用</p><p>　　4.1 鐵路貨運列車的最優(yōu)調(diào)度</p><p>　　4.1.1 問題敘述</p><p>　　某地區(qū)A、B兩市之間要修建一鐵路，依據(jù)地勢、環(huán)境、需求等因素，修建鐵路的預(yù)定方案如下：</p><p&g

68、t;　　（1）鐵路的運行方式為客車與貨運兼營的雙軌鐵路（單向單軌），在其運行的列車有旅客快車和貨運列車，由于客車的運行時間是國家鐵路部門早已排定的，不可更改，且規(guī)定客運優(yōu)于貨運，即貨車在每站開出前應(yīng)先明確在其到達前方車站前不會被客車趕上，否則在該站等候不能開車。又若貨車的前方到達站如無停車岔道，則貨車從本站開出前應(yīng)明確在其前面兩站的行程中不會被客車趕上否則在本站等候不能開車，余類推。</p><p>　?。?）鐵

69、路線內(nèi)有A、B、C、D四個站，各站的岔道數(shù)為.</p><p>　　這些岔道可供調(diào)車用，亦可供停車卸貨及洗刷車輛用。</p><p>　　（3）按早已排定的旅客快車時刻表，客車每天凌晨2:00從A站開出，以后每隔5小時開出一列，一晝夜共開出5列，當天最后一列的開車時間與翌晨第一列的開車時間相隔4小時?？蛙嚨男熊嚂r間在A、B站之間為3小時；在B、C站之間為2小時；在C、D站之間為5小時。&l

70、t;/p><p>　?。?）在不干擾客車運行的條件下，關(guān)于貨運列車的初步安排為：每天0:00從A站發(fā)出一列，以后每隔2小時發(fā)出一列，貨車的行車時間在A、B站之間為5小時；</p><p>　　在B、C站之間為4小時；在C、D站之間為7小時。</p><p>　　為了充分發(fā)揮該鐵路線的貨運能力，需要排定一張最優(yōu)的貨車運行時刻表，即要求每天發(fā)出最多的貨運列車且不干擾已排定的

71、客運列車。</p><p>　　4.1.2 問題分析</p><p>　　求解這個問題較為復(fù)雜，但可將其轉(zhuǎn)化為網(wǎng)絡(luò)最大流問題。</p><p>　?。?）設(shè)A、B兩市及其間的車站共P個。每個車站有nk條岔道（k=1,2,3…P）,可停放nk列列車。從第k站到第k+1站的行車時間貨車為tk個小時，客車為tk 個小時。</p><p>　　設(shè)為火

72、車到達第k站并從第k站開出的時刻</p><p>　　設(shè)為客車到達第k站并從第k站開出的時刻</p><p>　　設(shè)為貨車到達第k+1站并從第k+1站開出的時刻</p><p>　　設(shè)為客車到達第k+1站并從第k+1站開出的時刻</p><p><b>　　于是顯然有 </b></p><p&g

73、t;　?。?）若有公共部分，則稱是相交的，否則成為不相交的。顯然有當只相交情況下客車才有可能（并非必然）在第k站與地k+1站間追上貨車。</p><p>　　（3）在相交情況下，，，，間的相交關(guān)系可由圖4.1.1所示：</p><p><b>　　圖4.11</b></p><p>　　情況Ⅵ為途中貨車追上了客車故不符合題意。情況Ⅰ與情況Ⅱ中在

74、第k站與第k+1站間不發(fā)生在途中追上貨車。而在情況Ⅲ中必發(fā)生在第k站與第k+1站間客車在途中追上貨車。</p><p><b>　　于是有下列結(jié)論：</b></p><p>　　若內(nèi)，即，則在第k站與第k+1站必發(fā)生客車追上貨車情況。否則在第k站與第k+1站之間不發(fā)生客車追上貨車情況。</p><p><b>　?。?）繪制網(wǎng)絡(luò)圖&l

75、t;/b></p><p>　　用（k，）表示第k站處于時刻的狀態(tài)，如在=2.3在（k，2.6），（k，6.6）狀態(tài)開出的貨車不會再途中被客車追上，則在圖中表現(xiàn)為（k，2.6）及（k，6.6）兩節(jié)點為起點的兩條水平方向的直線弧，而在（k，4.6）狀態(tài)下開出的貨車會在途中被客車追上，則不能從該點引出水平方向的直線?。▓D4.1.2），垂直方向的直線弧并聯(lián)著同一車站的相鄰狀態(tài)。</p><p&

76、gt;<b>　　圖4.1.2</b></p><p>　　上圖中各弧旁的數(shù)字為容量，因鐵路線是單向單軌的，故水平方向的弧容量為1，垂直方向的弧的容量為各站的岔道數(shù)量，在列出全部狀態(tài)的網(wǎng)絡(luò)圖中求最大流，此最大流即為允許開出的最多貨運列車數(shù)。</p><p>　　4.1.3 問題求解</p><p>　　以貨運列車的運行時間為基礎(chǔ)繪制網(wǎng)絡(luò)圖。&l

77、t;/p><p>　　（1）令為火車從某站開出或到達某站的時刻。依題意，若不受客車干擾則：</p><p>　　=0:00,2:00,4:00……</p><p>　　=5:00,7:00,9:00……</p><p>　　=9:00,11:00,13:00……</p><p>　　=16:00,18:00,20:00……

78、</p><p>　　于是貨車在相鄰兩站的運行時間為（若不受客車干擾）：</p><p>　　(25點即翌日1點，余類推)</p><p>　　(2)令為客車從某站開出或到達某站的時刻，依題意：</p><p>　　=2:00,7:00,12:00,17:00,22:00</p><p>　　=5:00,10:00,1

79、5:00,20:00,25:00(即1:00)</p><p>　　=7:00,12:00,17:00,22:00,27:00（即3:00）</p><p>　　=12:00,17:00,22:00,27:00（即3:00），32:00（即8:00）</p><p>　　于是客車在相鄰兩站之間的運行時間為：</p><p><b>

80、　　圖4.1.3</b></p><p><b>　?。?）比較</b></p><p>　　之內(nèi)。這說明若A站在6:00及16:00開出兩列貨車，則該兩列貨車在到達B站前，必會被客車撞上。故這兩次貨運列車是不可行的。這表示在以貨運列車的運行時刻為基礎(chǔ)的網(wǎng)絡(luò)圖（圖4.1.3）中為（A,6:00）及（A，16:00）兩節(jié)點前未引出水平方向的直線弧。該圖的各個

81、節(jié)點中僅注明貨運列車從該站開出或到達該站的時刻，站名省略了。</p><p>　　比較,我們發(fā)現(xiàn)之內(nèi)；之內(nèi)，其在圖4.1.3中的表示同前。</p><p>　　比較,我們發(fā)現(xiàn)之內(nèi)；</p><p>　　之內(nèi)，其在圖3中的表示同前。</p><p>　?。?）圖4.1.3中各水平方向的直線弧的容量均為1。如前所述，它表示在該時間內(nèi)，貨車在相鄰兩

82、站的行程中不會被客車追上，故可順利地到達前方車站。垂直方向的直線弧的通量表示各站的岔道數(shù)。</p><p>　?。?）做網(wǎng)絡(luò)的發(fā)點，并從向A站的各狀態(tài)節(jié)點作輔助弧，輔助弧的容量等于以A站的各狀態(tài)節(jié)點為起點的各弧的容量的總和。作網(wǎng)絡(luò)的收點，并從D站的各狀態(tài)節(jié)點向作輔助弧。輔助弧的容量等于以D站個狀態(tài)節(jié)點為終點的各弧的容量總和。</p><p>　?。?）求圖4.1.3所示容量網(wǎng)絡(luò)的最大流&l

83、t;/p><p>　?、瘢┮粤懔鱢={0,0,…………0}為初始流，但圖4.1.3的各弧旁省略了零流量。</p><p>　?、颍┮员硎緢D3中第i行第j列的節(jié)點。用Ford-Fulkerson標號法求得以下增廣鏈并按值進行調(diào)整。</p><p>　?、?</p><p>　?、?<

84、/p><p>　　③ </p><p>　?、?</p><p>　?、?</p><p>　　⑥ </p><p>　?、?</p>

85、<p>　?、?</p><p>　?、?</p><p>　?、?</p><p>　　以上10條增廣鏈的調(diào)整量均為。用它對初始流（零流）進行調(diào)整后，結(jié)果如圖4.1.3所示。若對現(xiàn)行流繼續(xù)標號，則只有A站的12個狀態(tài)節(jié)點獲得標號，即標號中斷，不能延伸達。故現(xiàn)行流即為最大流

86、，其流量</p><p>　　結(jié)論 在本問題所給條件下各車站一晝夜中能開出的最多貨運列車數(shù)位10列。</p><p>　　現(xiàn)由圖4.1.3將A站以晝夜中能開出的10列貨車的運行時刻及調(diào)度情況闡述如（貨車一晝夜中在其他各站點的運行及調(diào)度情況可由同圖作類似闡述）</p><p>　　①在0:00,8:00,10:00,18:00,20:00,22:00時刻所開出的貨車

87、在各站點均暢通。</p><p>　　②在2:00開出的貨車，11:00到達C站時須在岔道內(nèi)停留到13:00方可繼續(xù)前行。</p><p>　?、墼?:00開出的貨車，9:00到達B站時，須在岔道內(nèi)停留到11:00方可繼續(xù)前行。</p><p>　?、茉?2:00開出的貨車，21:00到達C站時，須在岔道內(nèi)停留到23:00方可繼續(xù)前行。</p><

88、;p>　　⑤在14:00開出的貨車，19:00到達B站時，須在岔道內(nèi)停留到21:00方可繼續(xù)前行。</p><p>　　至此已求得一晝夜中從A站開出的10次貨運列車的最優(yōu)調(diào)度及最優(yōu)運行時刻表。</p><p>　　仿此，由圖4.1.3可求得從其他各站點開出貨車的最優(yōu)調(diào)度及最優(yōu)運行時刻表。</p><p>　　4.1.4 問題總結(jié)</p><

89、p>　　本問題看似簡單，是個追趕問題，只要計算出貨車與客車在兩站之間的運行時間即可控制貨車的開出時間，其實不然，此問題是在追趕問題的基礎(chǔ)上求最多可開出的貨車輛數(shù)，我們把該問題轉(zhuǎn)化成為最大流問題，應(yīng)用Ford-Fulkerson標號法解決了這一問題。通過對算法的分析求解制定出了貨車運行的最大數(shù)量并列出貨車運行時間表，可見最大流算法的有效性和實用性。</p><p><b>　　第五章 結(jié)論<

90、/b></p><p>　　本課題主要以圖論的知識為理論基礎(chǔ)，來討論最大流問題。最大流問題是一類應(yīng)用極為廣泛的問題，20世紀50年代福特(Ford)、富克遜(Fulkerson)建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。</p><p>　　最大流問題的核心依據(jù)是Ford-Fulkerson最大流最小割定理，在這個定理的基礎(chǔ)上，解決最大流問題的幾種算法有Ford-Fulkers

91、on標號法、Edmonds-Karp修正算法、Dinic算法等本論文分別介紹了這幾種算法，并舉實例說明各個算法具體的解題過程，各算法的優(yōu)劣各不相同，F(xiàn)ord-Fulkerson標號法是最原始的算法，由Ford和Fulkerson提出，Edmonds和Karp針對該算法增廣路徑選取的任意性這一缺點對它做了修正算法產(chǎn)生了Edmonds-Karp修正算法，而Dinic算法則兼取前兩種算法的優(yōu)點，是這三種算法中最有效的算法。</p>

92、<p>　　最大流問題是網(wǎng)絡(luò)流問題的一個重要的內(nèi)容，研究最大流問題并將其應(yīng)用到工業(yè)、工程、商業(yè)、農(nóng)業(yè)，運輸業(yè)等領(lǐng)域可給我們的生活帶來很大方便。</p><p>　　在很多情況下，實際遇到的問題可能是很復(fù)雜的，甚至是無從下手，不過通過分析建立模型，如果可以建立成一個網(wǎng)絡(luò)圖，轉(zhuǎn)化成為最大流問題，就會找到相應(yīng)的解決方法。由此，最大流問題在現(xiàn)實生活中是非常重要的。</p><p>&

93、lt;b>　　參 考 文 獻</b></p><p>　　[1] 熊義杰．運籌學教程．天津：國防工業(yè)出版社，2004</p><p>　　[2] 徐俊明. 圖論及其應(yīng)用. 合肥：中國科學技術(shù)大學出版社，2005</p><p>　　[3] 盧開澄. 圖論及其應(yīng)用. 北京：清華大學出版社，1984</p><p>　　[

94、4] 吳育華，杜綱．管理科學基礎(chǔ)．天津：天津大學出版社，2001</p><p>　　[5] 謝政，李建平. 網(wǎng)絡(luò)算法與復(fù)雜性理論. 北京：國防科技大學出版社，1995</p><p>　　[6] 刁在筠，鄭漢鼎，劉家壯，劉桂真. 運籌學. 第2版. 北京：高等教育出版社，2001</p><p>　　[7] 田豐，馬仲蕃. 圖與網(wǎng)絡(luò)流理論. 北京：科學出版

95、社，1987</p><p>　　[8] 卜月華，吳建專. 圖論及其應(yīng)用. 南京：東南大學出版社， 2000</p><p>　　[9] Bondy JA, Mutry USR. Graph Theory with Applications. London and Basingstoke: MacMillan Press, 1976</p><p>　　[10]

96、 王樹禾. 圖論及其算法. 合肥：中國科學技術(shù)大學出版社，1990</p><p>　　[11] 戴一奇. 圖論及其應(yīng)用. 北京：水利電力出版社，1988</p><p>　　[12] 展丙軍．運籌學．哈爾濱：哈爾濱地圖出版社，2005</p><p>　　[13] 《運籌學》教材編寫組. 運籌學. 第3版. 北京: 清華大學出版社，2004</p>

97、;<p>　　[14] 胡運權(quán)．運籌學教程．北京：清華大學出版社，2007</p><p>　　[15] 謝金星，邢文順. 網(wǎng)絡(luò)優(yōu)化. 北京：清華大學出版社，2000</p><p>　　[16] 李向東. 運籌學：管理科學基礎(chǔ). 北京：北京理工大學出版社，1990</p><p>　　[17] 李建中, 駱吉洲(譯). 圖論導引. 北京：機械

98、工業(yè)出版社，2006</p><p>　　[18] 王朝瑞. 圖論. 北京：北京工業(yè)學院出版社，1987</p><p><b>　　致謝辭</b></p><p>　　本科畢業(yè)論文即將完成，回顧我大學四年的學習生涯，我得到了眾多老師的教誨，同學的支持和幫助，再次對他們表示中心的感謝。</p><p>　　首先感謝我的

99、導師**老師，他生活中待人十分熱情誠懇，給予我無微不至的關(guān)懷和照顧；工作中他治學嚴謹，思維活躍，在研究課題閱讀文獻、論文寫作上給予我許多指導和幫助，使我對數(shù)學的認識有了很大的提高，我將銘記恩師的教誨、關(guān)心和幫助。</p><p>　　還要感謝大學四年來所有的老師，為我們打下堅實的數(shù)學專業(yè)知識基礎(chǔ)，在論文的寫作過程中，還要感謝班內(nèi)同學的幫助，他們在我完成論文的過程中，給我提了許多寶貴的建議，正是因為有了你們的支持和

100、鼓勵。此次畢業(yè)設(shè)計才能夠順利的完成。</p><p>　　感謝所有給予我?guī)椭湾憻挼娜恕?lt;/p><p>　　最后，衷心感謝所有老師對我的栽培、支持和鼓勵，感謝所有朋友的關(guān)心和幫助。向在百忙中抽出時間對此論文進行評審并提出寶貴意見的各位專家表示衷心地感謝！</p><p>　　衷心祝愿母校**大學明天更加美好！</p><p><b&g

101、t;　　附錄1英文原文</b></p><p>　　Maximum flow problem in the introduction, we listed one of the largest flow of goods delivery. If this issue also includes the known conditions of delivery of each unit while t

102、he cost of goods, then how to transport, to get the most traffic, and transportation costs to a minimum? This is the so-called maximum flow problem minimum cost. The maximum flow based on the definition, if each side of

103、a first-priority claim to the number of (that the edge capacity) but also have another weights (that th</p><p>　　Satisfy for all </p><p>　　for all (maximum flow constraints)(Or)</p>&

104、lt;p>　　Algorithm ideas Solve the minimum cost maximum flow problem, there are two general ways. Way is to use a maximum flow algorithm to calculate the maximum flow, and then based on the cost side, check whether it i

105、s possible to balance the flow by adjusting the flow side, so that to reduce the total cost? As long as there is a possibility, on such adjustments. After adjusting for a new </p><p>　　maximum flow. Then, on

106、 the basis of the new flow to continue to check and adjust. This iteration continues until no adjustment may be, they will have the minimum cost maximum flow. The characteristics of this line of thought is to maintain th

107、e feasibility of the problem (always maintain maximum flow), to promote optimal. Solution to another and in front of the maximum flow algorithm, introduced a similar line of thought, first of all, given the general flow

108、as the initial flow of zero. The cost </p><p>　　If G in the edge is not enough traffic, that is, , then G 'in the building edge , Empowering; edge of G if has been the flow, that is, , then G' in t

109、he building edge , to empower the .</p><p>　　The establishment of the network by streaming, you can seek in this network to the Meeting Point source shortest path, as decided by flow path, and then in the or

110、iginal network by flow in this path. Here, the use of maximum flow algorithm is still the principle of increasing flow, but the cost must be selected by the smallest chain by stream flow. Calculation, there is a need to