通信網(wǎng)基礎第五章網(wǎng)絡拓撲結構分析.ppt

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