通信網(wǎng)基礎(chǔ)第五章網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分析.ppt

通信網(wǎng)基礎(chǔ) 第五章 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分析,通信網(wǎng)實(shí)驗(yàn)室 C,2019年7月,,2,概述,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分析是很基本，也是很重要的問題。 拓?fù)浣Y(jié)構(gòu)是通信網(wǎng)規(guī)劃和設(shè)計(jì)的第一層次問題。 通信網(wǎng)的拓?fù)浣Y(jié)構(gòu)可以用圖論的模型來代表，本章分析的主要問題為最小支撐樹、最短路徑和網(wǎng)絡(luò)流量安排等問題。,2019年7月,,3,5.1 圖論基礎(chǔ) 5.1.1 圖的定義和基本概念,圖論是應(yīng)用數(shù)學(xué)的一個(gè)分支，有著豐富的內(nèi)容，本節(jié)介紹它的一些概念和結(jié)論。 例5.1 歐拉(Euler) 7橋問題。 有一些河穿過哥尼斯堡城，將該城分為 4個(gè)部分，有7座橋?qū)⒊侵懈鱾€(gè)部分相 連，當(dāng)?shù)赜幸粋€(gè)游戲，問能否從城的某一個(gè)部分出發(fā)遍歷每一座橋同時(shí)不重復(fù)經(jīng)歷任何一座橋。,2019年7月,,4,2019年7月,,5,5.1.1 圖的定義和基本概念,解：Euler分析了這個(gè)問題，并且用圖5.1來代表這個(gè)問題，4個(gè)端點(diǎn)表示4個(gè)城區(qū)，而邊表示7座橋。如果定義端點(diǎn)的度為和它關(guān)聯(lián)的邊的個(gè)數(shù)，那么在圖5.1中，各端點(diǎn)的度為3，3，3，5。 如果存在一個(gè)遍歷每座橋的漫游，除去起點(diǎn)和終點(diǎn)，對(duì)每個(gè)中間端點(diǎn)總是一進(jìn)一出，所以那些中間端點(diǎn)的度應(yīng)該為偶數(shù)，由于圖5.1中度為奇數(shù)的端大于2個(gè)，這樣圖5.1不可能存在一個(gè)遍歷所有橋的漫游。,2019年7月,,6,圖的定義,定義5.1 所謂一個(gè)圖G，是指給了一個(gè)端點(diǎn)集合V，以及邊的集合或V中元素的序?qū)?E，圖一般用 來表示。 如果圖G有n端m條邊，可將V和E表示為 ， 。 某邊的端為 ，稱這邊和端 關(guān)聯(lián)，這個(gè)邊也可記為: 或 。,2019年7月,,7,一些基本概念,有限圖 V，E 無向圖 有向圖 空?qǐng)D 孤立點(diǎn)圖 自環(huán) 重邊 一個(gè)不含自環(huán)和重邊的圖稱為簡(jiǎn)單圖，以后如果沒有特別聲明主要討論簡(jiǎn)單圖。,2019年7月,,8,度的定義,對(duì)無向圖的端 ，與該端關(guān)聯(lián)邊的數(shù)目為該端的度數(shù)，記為： 。 對(duì)有向圖的端 ， 表示離開 的邊數(shù)， 表示進(jìn)入 的邊數(shù)。 性質(zhì)5.1 對(duì)無向圖 對(duì)有向圖,2019年7月,,9,子圖,給定圖 ，若 稱圖 是G中由 生成的子圖，記為 。若 ，稱 為G的子圖。特別，若子圖的端點(diǎn)集合為V，這個(gè)圖被稱為圖G的支撐子圖。 若 ， 稱圖 是G中由 生成的子圖，記為 。,2019年7月,,10,圖的連通性,考慮邊的一個(gè)序列，相鄰兩邊有公共端，如(v1，v2)， (v2，v3)， (v3，v4)， (vi，vi+1)，這個(gè)邊序列稱為鏈，鏈簡(jiǎn)單說就是一個(gè)連續(xù)軌跡。 沒有重復(fù)邊的鏈稱為簡(jiǎn)單鏈；沒有重復(fù)端的鏈稱為初等鏈或道路； 若鏈的起點(diǎn)與終點(diǎn)重合，稱之為圈；若道路的起點(diǎn)與終點(diǎn)重合,稱之為初等圈。一般重點(diǎn)討論道路和初等圈。,2019年7月,,11,連通圖,任何兩端間至少存在一條鏈的圖，為連通圖。否則，就是非連通圖。 非連通圖G有三個(gè)連通分支,2019年7月,,12,圖的例子,完全圖 兩部圖 歐拉圖 正則圖,2019年7月,,13,5.1.2 樹,定義5.2 無圈的連通圖稱為樹。 性質(zhì)5.2 除單點(diǎn)樹，至少有兩個(gè)度數(shù)為1的端(懸掛點(diǎn))。 性質(zhì)5.3 任意樹的邊數(shù)m和端數(shù)n滿足,2019年7月,,14,定理5.1 給定一個(gè)圖 T，若 ， ，則下面論斷等價(jià)： （1）T是樹； （2）T無圈，且 ； （3）T連通，且 。,5.1.2 樹,2019年7月,,15,性質(zhì)5.4 若T是樹，則： （1）T是連通圖，去掉任何一條邊，圖 便分成兩個(gè)且僅僅兩個(gè)連通分支； （2）T是無圈圖，但添加任何一條邊，圖便會(huì)包含一個(gè)且僅僅一個(gè)圈。 性質(zhì)5.5 設(shè)T是樹，則任何兩點(diǎn)之間恰好有一條道路；反之，如圖T中任何兩點(diǎn)之間恰好有一條道路，則T為樹。,5.1.2 樹,2019年7月,,16,如果樹T是連通圖G的子圖，TG，且T包含G的所有端，稱T是G的支撐樹或主樹。 連通圖一定有支撐樹。 樹邊，連枝。,5.1.2 樹,2019年7月,,17,5.1.3 割集,割集指的是某些端集或邊子集。對(duì)連通圖，去掉此類子集，圖變?yōu)椴贿B通。 定義5.3 割端與割端集 設(shè)v是圖G的一個(gè)端，去掉v和其關(guān)聯(lián)邊后，G的部分?jǐn)?shù)增加，則稱v是圖G的割端。去掉一個(gè)端集合后，G的部分?jǐn)?shù)增加，這個(gè)端的集合稱為割端集。,2019年7月,,18,點(diǎn)連通度,對(duì)于連通圖, 在眾多的割端集中至少存在一個(gè)端數(shù)最少的割端集，稱為最小割端集。 最小割端集的端數(shù)目，稱為圖的點(diǎn)連通度或連通度，連通度用 表示。,2019年7月,,19,線連通度,定義5.4 割邊與割邊集 設(shè)e是圖G的一條邊，去掉 e 后，G的部分?jǐn)?shù)增加，則稱e是圖G的割邊。去掉一個(gè)邊集合后，G的部分?jǐn)?shù)增加，這個(gè)邊的集合稱為割邊集。 割邊集中邊數(shù)最少的割邊集，稱為最小割邊集。最小割邊集的邊數(shù)目，稱為線連通度，線連通度用 表示。,2019年7月,,20,性質(zhì)5.5,性質(zhì)5.5 對(duì)于任意一個(gè)連通圖 ，若 ， ， 為最小度，則,2019年7月,,21,基本割集和基本圈,對(duì)于任何一個(gè)連通圖G，設(shè)T為G的一個(gè)支撐樹，圖中的邊分為樹邊和連枝。 對(duì)于支撐樹，去掉樹上任何一條邊，樹便分為兩個(gè)連通分支，從而將原圖的端分為兩個(gè)集合，這兩個(gè)集合之間的所有邊形成一個(gè)極小邊割集，這個(gè)邊割集稱為基本割集。 每一條連枝決定的圈是基本圈，每條樹邊決定一個(gè)基本割集。,2019年7月,,22,基本圈和基本割集,基本割集和基本圈,2019年7月,,23,基本圈和基本割集有許多應(yīng)用，首先通過集合的對(duì)稱差運(yùn)算, 由基本割集可以生成新的割集或它們的并集,事實(shí)上可以證明生成所有的割集；基本圈也有類似的性質(zhì)。 例5.2 通過基本圈和基本割集分析求解電網(wǎng)絡(luò)。,基本割集和基本圈,2019年7月,,24,分析：在每個(gè)等電勢(shì)的區(qū)域抽象一個(gè)端點(diǎn)，一個(gè)電網(wǎng)絡(luò)為一個(gè)連通圖。如果這個(gè)圖有n個(gè)端點(diǎn)，m條邊，則有n-1個(gè)獨(dú)立電勢(shì)變量。任取一個(gè)支撐樹，有n-1個(gè)基本割集。在每個(gè)基本割集上，根據(jù)基爾霍夫定律，流過基本割集電流的代數(shù)和為零。這n-1個(gè)方程由于每個(gè)方程含有唯一的樹枝項(xiàng)，所以這n-1個(gè)方程線性無關(guān)，通過這些方程可以求解所有的電勢(shì)變量。,基本割集和基本圈,2019年7月,,25,反圈,下面給出一個(gè)重要的概念：反圈。 定義5.5 反圈：給定圖 ，若 ，記 ；特別，當(dāng) 時(shí)，將 記為 或 。 設(shè) 是 的非空真子集，若 ， 稱 為由 確定的反圈。,2019年7月,,26,5.1.4 圖的矩陣表示,下面將給出圖的矩陣表示，主要介紹關(guān)聯(lián)陣和鄰 接陣。 1 關(guān)聯(lián)陣 設(shè)圖G有 n 個(gè)端，m 條邊，則全關(guān)聯(lián)陣 ， 其中，,2019年7月,,27,關(guān)聯(lián)陣,例5.3 考慮下面圖5.4所表示的圖,2019年7月,,28,關(guān)聯(lián)陣中每行對(duì)應(yīng)一個(gè)端，每列對(duì)應(yīng)一個(gè)邊，由于完全表示了圖中端集和邊集的信息，所以關(guān)聯(lián)陣是圖的一個(gè)等價(jià)表示。 每行非零元個(gè)數(shù)等于相應(yīng)端的度數(shù), 每列有兩個(gè)1； 任意兩行或兩列互換得到的關(guān)聯(lián)陣本質(zhì)上是一個(gè)圖。 將A0中每列的任一個(gè)1改為-1, 因?yàn)閚行之和零，所以最多只有n-1行線性無關(guān)，再去掉任一行，得到關(guān)聯(lián)陣A，這是一個(gè)（n-1） m矩陣。,關(guān)聯(lián)陣,2019年7月,,29,可以證明A的每一個(gè)n-1階非奇異方陣一一對(duì)應(yīng)一個(gè)支撐樹，并且該方陣的行列式的絕對(duì)值為1 定理5.2 (矩陣-樹定理) 用 表示 的轉(zhuǎn)置, 無向圖G的主樹數(shù)目,關(guān)聯(lián)陣vs支撐樹,2019年7月,,30,同時(shí)n-1階矩陣 可以直接寫出, 主對(duì)角線的元素為相應(yīng)端點(diǎn)的度數(shù), 其余位置根據(jù)相應(yīng)的端點(diǎn)之間是否有邊取值為-1或0。 繼續(xù)例5.3，如果去掉第一行，則,關(guān)聯(lián)陣,2019年7月,,31,關(guān)聯(lián)陣,共有8種支撐樹如下：,2019年7月,,32,鄰接陣,2 鄰接陣 鄰接陣是表示圖的端與端關(guān)系的矩陣，其行和列都與端相對(duì)應(yīng) 。 令 為 端， 邊的有向圖，其鄰接陣：,2019年7月,,33,對(duì)于例5.3中的圖，鄰接陣為： 對(duì)于無向圖 ，因此是鄰接陣為對(duì)稱陣。,鄰接陣,2019年7月,,34,鄰接陣包含了圖的所有信息，和關(guān)聯(lián)陣一樣，是圖的等價(jià)表示。 鄰接陣和關(guān)聯(lián)陣以后被經(jīng)常用來表示圖。 可以通過對(duì)鄰接陣C做一些計(jì)算，得到圖G的一些性質(zhì)，例如可以計(jì)算C的冪來考慮圖是否連通。,鄰接陣,2019年7月,,35,矩陣P為判斷矩陣，1表示連通，0為不連通 (1)置新矩陣 P:= C; (2)置 = 1; (3)對(duì)所有的 , 如果 , 則對(duì) k=1,2,n，有 ; (4) ; (5) 如 轉(zhuǎn)向步驟(3), 否則停止。,Warshall算法,2019年7月,,36,5.2 最短路徑問題,上節(jié)中介紹的圖只考慮了圖頂點(diǎn)之間的關(guān)聯(lián)性，本節(jié)將要對(duì)圖的邊和端賦予權(quán)值，討論有權(quán)圖。 權(quán)值在各種各樣實(shí)際問題中有不同的物理意義，如費(fèi)用，幾何距離，容量等。 在本節(jié)中將討論最小支撐樹和最短路徑問題等算法。,2019年7月,,37,5.2.1 最小支撐樹,給定連通圖 ， 是定義在 上的非負(fù)函數(shù)， 為 的一個(gè)支撐樹。定義樹 的權(quán)為 。 最小支撐樹問題就是求支撐樹 ，使 最小。下面介紹求最小支撐樹的方法，首先不加證明地引用定理5.3。,2019年7月,,38,最小支撐樹的特征,定理5.3 設(shè) 是 的支撐樹，則如下論斷等價(jià)： （1） 是最小支撐樹； （2）對(duì) 的任一樹邊 ， 是由 所決定的基本割集或反圈中的最小權(quán)邊； （3）對(duì) 的任一連枝 ， 是由 所決定的基本圈中的最大權(quán)邊。 這個(gè)定理描述了最小支撐樹的特征。依照不同的邏輯，可以有下面不同的具體做法。,2019年7月,,39,Prim 算法反圈法,Prim(1957年) (1)任取一點(diǎn)作為初始的 ； (2)在反圈 中選邊的原則是： 從 中選一條權(quán)最小的邊（如果有多條權(quán)最小的邊，則任選一條）； 將選出邊的鄰端并入 形成 ； (3)若在某一步， ，則 不含支撐樹；若在某一步， ，則由所有被選邊生成的樹是最小支撐樹。,2019年7月,,40,例5.4 求下圖中的最小支撐樹。,Prim 算法,解：如果以 為 ，按照Prim算法，選出的端序列為： ，其中 的順序可以改變。最小支撐樹 。,Prim 算法,2019年7月,,41,Kruskal算法避圈法,將所有邊排序，然后由小到大選邊，保持所選的邊不生成圈，如果選了n1條邊，則生成了一個(gè)最小支撐樹 。 設(shè) 是 的無圈支撐子圖,開始 若 是連通的,則它是最小支撐樹；若 不連通,取 為這樣的一邊,它的兩個(gè)端點(diǎn)分屬 的兩個(gè)不同連通分支,并且權(quán)最小。令 = + ,重復(fù)上述過程。,2019年7月,,42,2,2,3,3,4,4,5,6,1,2019年7月,,43,破圈法,設(shè) 是 的連通支撐子圖，開始 ，若 中不含圈，則它是最小支撐樹；若 中包含圈，設(shè)是中的一個(gè)圈，取上的一條權(quán)最大的邊 ，令 = - ，重復(fù)上述過程。 從連通圖中尋找圈，然后在圈中刪去權(quán)最大的邊，最后剩下的無圈連通圖為最小支撐樹,2019年7月,,44,破圈法,例5.5 對(duì)于一個(gè)無向圖, 如何尋找其中的圈? 解：首先，度為1的頂點(diǎn)肯定不在任何圈上，將這類懸掛點(diǎn)刪去不影響對(duì)圈的尋找，通過逐步刪去圖中度為1的頂點(diǎn)而使圖簡(jiǎn)化。如果一個(gè)圖不含度為1的端，可以從任意一個(gè)端出發(fā)漫游，由于有限性，端一定會(huì)重復(fù)，而這就找到了一個(gè)圈。,2019年7月,,45,2,2,3,3,4,4,5,6,1,2019年7月,,46,5.2.2 端間最短路徑和路由,已知圖 ，每條邊 有權(quán) 需要求網(wǎng)絡(luò)中端點(diǎn)之間的最端距離和路由。這類問題分兩種情況： 1 尋找指定端至其它端的最短路徑和路由，這個(gè)問題可以使用Dijkstra算法解決； 2 尋找任意二端最短路徑和路由, 這個(gè)問題可以使用Floyd算法解決。,2019年7月,,47,Dijkstra算法,圖 的每一邊上有一個(gè)權(quán) 設(shè) 是 中的一條鏈，定義鏈 的權(quán)為： 。 Dijkstra(1959年)算法可以簡(jiǎn)述如下： (1)初始 ，記 ，并且 的標(biāo)號(hào)為 。 (2)對(duì)任一邊 反圈 計(jì)算 的值。,2019年7月,,48,在 中選一邊，設(shè)為 ； 使 ，并令 并且 的標(biāo)號(hào)為 。 (3)當(dāng)出現(xiàn)下面情況之一時(shí)停止。 情況1：目的端 滿足 ； 情況2：目的端 滿足 ，但 。,Dijkstra算法,2019年7月,,49,Dijkstra算法,例5.6 在下圖中求 到其余端點(diǎn)的最短距離和路由。,2019年7月,,50,計(jì)算如表5.1所示。,Dijkstra算法,2019年7月,,51,對(duì)于Dijkstra算法, 提出若干問題如下： (1) 如果端點(diǎn)有權(quán)如何處理? (2) 如果邊的權(quán)可正可負(fù), 算法是否仍然 有效? (3)算法是否對(duì)有向圖也適用？,Dijkstra算法,2019年7月,,52,例5.7 深度優(yōu)先和廣度優(yōu)先搜索。 如果要搜索的環(huán)境為圖 ，每條邊賦權(quán)1，搜索的起點(diǎn)為 ，應(yīng)用Dijkstra算法求 到任意端 的距離，距離 表示了端 的“代”數(shù)。 廣度優(yōu)先搜索可以簡(jiǎn)述如下： （1）開始取 作為 。,Dijkstra算法,2019年7月,,53,（2）在 中選邊時(shí)，遵守如下原則：首先在 中選一個(gè)“代”數(shù)最小的端，如 ，然后選所有以 為端點(diǎn)的邊。如果 的標(biāo)號(hào)為 ，則選中邊的相鄰端的標(biāo)號(hào)應(yīng)為 ；將新的端點(diǎn)加入到 形成 。 （3）如果在某一步， ，表明圖不連通；如果在某一步, ,結(jié)束。 注意，標(biāo)號(hào)記錄了該端的“代”數(shù)和搜索到該端的路由。,廣度優(yōu)先搜索,2019年7月,,54,深度優(yōu)先搜索,（1）開始取 作為 。 （2）在 中選邊時(shí)，遵守如下原則：只選一條邊，該邊在 中的端的“代”數(shù)最大；將新的端點(diǎn)加入到 形成 。 （3）如果在某一步， ，表明圖不連通；如果在某一步, ,結(jié)束。,2019年7月,,55,Floyd算法,定理5.4 對(duì)于圖 , 如果 表示端 和 端 之間的可實(shí)現(xiàn)的距離, 那么 表示端 和 之間的最短距離當(dāng)且僅當(dāng)對(duì)于任意 ，有 證明：首先，如果 表示端 和 之間的最短距離，則,2019年7月,,56,下面考慮充分性： 若 是任一個(gè)從端 到端 的鏈， ， 則反復(fù)應(yīng)用充分條件，有,Floyd算法,2019年7月,,57,因?yàn)?表示端 和 之間的可實(shí)現(xiàn)的距離，則 表示端 和 之間的最短距離。,Floyd算法,2019年7月,,58,Floyd算法,給定圖 及其邊 的權(quán) ：初始化距離矩陣 和路由矩陣 其中：,2019年7月,,59,F1：已求得 和 ，依據(jù)下面的迭代求 和 ： F2：若kn，重復(fù)；k=n終止。,Floyd算法,2019年7月,,60,對(duì)于Floyd算法, 同樣提出若干問題如下: (1) 如果端點(diǎn)有權(quán)如何處理? (2) 如果邊的權(quán)可正可負(fù), 算法是否仍然有效? (3) 算法是否對(duì)有向圖也適用？ 問題1和3在Dijkstra算法中有過討論，這里重點(diǎn)討論問題(2)。,Floyd算法,2019年7月,,61,圖的中心與中點(diǎn),已知圖 為權(quán)圖, 根據(jù)Floyd算法的結(jié)果可以定義網(wǎng)絡(luò)的中心和中點(diǎn)。 中心 對(duì)每個(gè)端點(diǎn) ，先求 此值最小的端稱為網(wǎng)的中心，即滿足下式的端： =,2019年7月,,62,中點(diǎn) 對(duì)每個(gè)端點(diǎn) ,計(jì)算 , 然后求出 的最小值, 相應(yīng)的端點(diǎn)為中點(diǎn)。,圖的中心與中點(diǎn),2019年7月,,63,例5.8 圖G的距離矩陣如下，用Floyd算法求任意端間最短距離和路由，并求中心和中點(diǎn)。,2019年7月,,64,解：距離矩陣包含了鄰接矩陣和權(quán)的所有信息，依照Floyd算法計(jì)算結(jié)果如下：,2019年7月,,65,R矩陣更新,2019年7月,,66,最后結(jié)果及驗(yàn)證,2019年7月,,67,路由查找舉例,找v1v4: 路由查得r14=4，不轉(zhuǎn)接v1v4； 找v3v4: 路由查得r34=7，經(jīng)7轉(zhuǎn)接； 查v3v7得r37=7，無轉(zhuǎn)接。 查v7v4得r74=1，經(jīng)1轉(zhuǎn)接：查v7v1得1無轉(zhuǎn)接；查v1v4得4，無轉(zhuǎn)接。 路由為v3v7v1v4 找v4v6: ,2019年7月,,68,正向路由,回溯路由,2019年7月,,69,從而，圖的中心為 ，中點(diǎn)為,上例中的中心和中點(diǎn),對(duì)于中心和中點(diǎn)，根據(jù)的計(jì)算結(jié)果可以得到：,2019年7月,,70,5.3 網(wǎng)絡(luò)流量問題,網(wǎng)絡(luò)的目的是把一定的業(yè)務(wù)流從源端送到宿端，流量分配的優(yōu)劣將直接關(guān)系到網(wǎng)絡(luò)的使用效率和相應(yīng)的經(jīng)濟(jì)效益。 網(wǎng)絡(luò)的流量分配受限于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，邊和端的容量，流量分配和路由規(guī)劃關(guān)系密切。 本節(jié)中關(guān)于流量問題的內(nèi)容均在有向圖上考慮，并且均是單商品流問題，即網(wǎng)絡(luò)中需要安排的只有一種商品或業(yè)務(wù)；,2019年7月,,71,5.3.1 基本概念,給定一個(gè)有向圖 ， 是定義在邊集合 上一個(gè)非負(fù)函數(shù)，稱為容量；邊 的容量 表示這條邊能通過的最大流量。 設(shè) 是上述網(wǎng)絡(luò)的一個(gè)流，該流有一個(gè)源 和一個(gè)宿 ，若能滿足下述二個(gè)限制條件，稱為可行流。,2019年7月,,72,可行流的條件,（1）非負(fù)有界性：對(duì)任意邊 有， （2）連續(xù)性: 對(duì)任意端 有，,2019年7月,,73,最大流問題,為源宿間流的總流量。需要解決的基本問題分為兩類: 1 最大流問題 在確定流的源和宿的情況下, 求一個(gè)可行流 , 使 為最大。,2019年7月,,74,最小費(fèi)用流問題,2 最小費(fèi)用流問題 如果邊 的單位流費(fèi)用為 , 流 的費(fèi)用為： 最小費(fèi)用流問題 在確定流的源和宿的情況下, 求一個(gè)可行 流 ,使 為最小。,2019年7月,,75,下面介紹割量和可增流路的概念。 設(shè) 是 的真子集，且 ， 表示起點(diǎn)和終點(diǎn)分別在 和 的邊集合，這是一個(gè)帶方向的反圈或割集,割集的正方向?yàn)閺?到 。割量 定義為這個(gè)割集中所有邊容量的和:,割量,2019年7月,,76,邊的流量和,對(duì)可行流 : 表示前向邊的流量和， , 表示反向邊的流量和， ；,2019年7月,,77,則源為 宿為 的任意流 有: 1. ，其中 ， 對(duì)任 : 對(duì)所有 ,將上述等式求和：,性質(zhì)5.7,2019年7月,,78,2. 由 非負(fù)，可得：,性質(zhì)5.7,2019年7月,,79,下面討論可增流路的概念。 從端s到端t的一個(gè)路，有一個(gè)自然的正方向，然后將路上的邊分為兩類：前向邊集合和反向邊集合。對(duì)于某條流，若在某條路中，前向邊均不飽和（ ），反向邊均有非0流量（ ），稱這條路為可增流路。 在可增流路上增流不影響連續(xù)性條件，也不改變其它邊上的流量，同時(shí)可以使從源端到宿端的流量增大。,可增流路,2019年7月,,80,5.3.2 最大流問題,所謂最大流問題，在確定流的源端和宿端的情況下, 求一個(gè)可行流 , 使 為最大。對(duì)于一個(gè)網(wǎng)絡(luò)，求最大流的方法采用可增流路的方法，下面的定理5.5為這種方法提供了保證。,2019年7月,,81,定理5.5 (最大流-最小割定理) 可行流 為最大流當(dāng)且僅當(dāng) 中不存在從 到 的可增流路。 證明： 必要性： 設(shè) 為最大流,如果 中存 在關(guān)于 的從 到 的可增流路 。 構(gòu)造一個(gè)新流 如下: ,5.3.2 最大流問題,2019年7月,,82,不難驗(yàn)證新流 為一個(gè)可行流,而且 ,矛盾。 充分性: 設(shè) 為可行流, G中不存在關(guān)于這個(gè)流的可增流路。,5.3.2 最大流問題,2019年7月,,83,令X* = v|G中存在從 到 的可增流路,從而 。 對(duì)于任意邊 ，有 對(duì)于任意邊 ，有 這樣, ,那么流 為最大流， 為最小割。證畢。 性質(zhì)5.8：如果所有邊的容量為整數(shù)，則必定存在整數(shù)最大流。,5.3.2 最大流問題,2019年7月,,84,求最大流的基本思想是： 在一個(gè)可行流的基礎(chǔ)上， 找 到 的可增流路，然后在此路上增流，直至無可增流路時(shí)，停止。 M算法：從任一可行流開始，通常以零流開始。 （1）標(biāo)志過程：從 開始給鄰端加標(biāo)志,加上標(biāo)志的端稱已標(biāo)端;,5.3.2 最大流問題,2019年7月,,85,（2）選查過程：從 開始選查已標(biāo)未查端；查某端，即標(biāo)其可能增流的鄰端;所有鄰端已標(biāo)，則該端已查。標(biāo)志宿端，則找出一條可增流路到宿端，進(jìn)入增流過程。 （3）增流過程：在已找到的可增流路上增流。,5.3.2 最大流問題,2019年7月,,86,步驟： M0：初始令 ； M1：標(biāo)源端 ： ； M2：從 始，查已標(biāo)未查端 ，即標(biāo) 的滿足下列條件的鄰端 ， 若 ，且 ，標(biāo) 為: 其中 ， 為 已標(biāo)值。 若 ，且 ，標(biāo) 為: 其中 ，其余 端不標(biāo)。,5.3.2 最大流問題,2019年7月,,87,所有能加標(biāo)的鄰端 已標(biāo)，則稱 已查。 倘若所有端已查且宿端未標(biāo)，則算法終止。 M3：若宿端 已標(biāo)，則沿該可增流