第三章 通信網(wǎng)結(jié)構(gòu) 第一節(jié)

第三章

通信網(wǎng)結(jié)構(gòu)

一、

基本定義

設(shè)端集V={v1,v2,……vn}邊集E={e1,e2,…….em}eij=(vi,vj)圖G是V，E及R的集合G={V,E}=V∪E=(V,E,R)§1圖論基礎(chǔ)(從傳輸網(wǎng)絡(luò)所需出發(fā)介紹)

無向圖:viRvj等價于vjRvi(eij=eji)有向圖:viRvj不等價于vjRvi

空圖：V=φ(此時E必為空集)孤立點圖：E=φ,V≠φ有限圖：V,E均為有限元，∣V∣,∣E∣≠∞無限圖：V,E無限元圖的幾何表示：端—點邊—線（不一定直線）端—端有邊——鄰接vi與vj鄰接：有邊端—邊相連——關(guān)聯(lián)eij與vi關(guān)聯(lián)有些應(yīng)用場合，不許線交叉，不可畫在平面圖上（如印制，集成）——圖的平面性。有權(quán)圖：通常對邊與端附于一定權(quán)值，表示某種性質(zhì)。賦之值—權(quán)值，權(quán)——權(quán)不限于一個f1(v1),f2(v2)......

如：距，代價，流量，容量，轉(zhuǎn)接容量...... 電流，電位......對通信網(wǎng)：端（站，局）；邊（信道）運輸網(wǎng)：車站 路排水系統(tǒng)：泵源 管道邏輯思維：狀態(tài) 轉(zhuǎn)移如M序列,以n=3為例，該序列周期為=8周期為的序列有種

對于n=3，共有2種，即：子圖：若A的端集與邊集分別為G的端集與邊集的子集，則A為G的子圖。若A

G，且A

G，則A為G的真子集真子集---G中至少有一個元素不在A內(nèi)若A=G，則A

G，A

G圖的運算：設(shè)A={e1，e2},e1=（v1，v3）,e2=（v3，v2）設(shè)B={e1，e3},e1=（v1，v3）,e3=（v1，v4）并：A

B={e1，e2，e3}——A，B所有元素組成

交：A

B={e1}——A，B公共元素

若A

B=φ，則A

B=A+B稱直和

差：A-B={e2}—屬A但不屬B之元素A中去掉B的公共邊環(huán)和：A

B={e2，e3}——屬A或?qū)貰，但不同屬A與B(特有邊)注意：去端—同時去掉與該端關(guān)聯(lián)的所有邊去邊—不去關(guān)聯(lián)端二、圖的聯(lián)結(jié)性端度數(shù)：與該端關(guān)聯(lián)的邊數(shù)，記為：d(vi)有向圖：d+(vi)=離開vi的邊數(shù)

d-(vi)=進(jìn)入vi的邊數(shù)有：d(vi)=d+(vi)+d-(vi)性質(zhì)：

1)由定義而來：任一邊或與二端關(guān)聯(lián)，或與一端關(guān)聯(lián)（自環(huán)）。所以每邊均提供度數(shù)為2,所以有下式2）奇度數(shù)端有偶數(shù)個（或0個）將端集分為：v1——奇度數(shù)端集

v2——偶度數(shù)端集

v=v1

v2鏈、徑、環(huán)的定義邊序列：相鄰二邊有公共端的邊的串序排列（有限）(v1,v2),(v2,v3),(v3,v4),

(vi,vj),

邊序列中，邊可重復(fù)出現(xiàn)——重邊

端可重復(fù)出現(xiàn)——重端

鏈：無重邊的邊序列

鏈中每邊只出現(xiàn)一次

一般鏈中只有二個端度數(shù)為奇數(shù)（起止不同端）

鏈可有環(huán)徑：無重邊，無重端的邊序列

徑是無環(huán)的鏈（每邊、每端只能出現(xiàn)一次）

除起止端外，其他各端度數(shù)均為2

即網(wǎng)中的路徑、路由環(huán)：閉鏈聯(lián)結(jié)圖：任何二端間至少存在一條徑的圖非聯(lián)結(jié)圖

分為幾個最大聯(lián)結(jié)子圖

即幾個“部分”“最大聯(lián)結(jié)子圖”—此圖加一個屬原圖而不屬此圖的元素則此圖不聯(lián)結(jié)—即部分G=A

B

C=A+B+C全聯(lián)結(jié)圖：任何二端間有邊（直通路由）

最完整的聯(lián)結(jié)圖

對應(yīng)全聯(lián)結(jié)網(wǎng)

邊、端數(shù)之間固定關(guān)系(無自環(huán),無重邊)n=5的全聯(lián)結(jié)圖：正則圖：所有端度數(shù)都相同的聯(lián)結(jié)圖

d(vi)=常數(shù)（i=1,2,

n）

聯(lián)結(jié)性最均勻的圖

無重邊的全聯(lián)結(jié)圖是正則圖，其d(v)=n-1

正則圖不一定是全聯(lián)結(jié)圖尤拉圖(Euler):端度數(shù)均為偶數(shù)的圖

不一定是聯(lián)結(jié)圖

聯(lián)結(jié)尤拉圖是一筆畫圖

充要條件:聯(lián)結(jié)尤拉圖存在一個含全邊的環(huán)(鏈)

二尤拉圖的環(huán)和也為尤拉圖M圖:只有二個奇度數(shù)端的圖

不一定是聯(lián)結(jié)的

不可能一徑走完

充要條件:存在含全邊的開鏈E圖去任何一邊----M圖M圖奇度端間加一邊----E圖H圖：哈密爾頓圖(Hamrton)至少存在一個含全端的環(huán)(Hamrton環(huán))

是聯(lián)結(jié)圖

充要條件:存在一個含全端的環(huán)這些圖在圖論中占有重要位置。三、樹:樹的概念與性質(zhì)在網(wǎng)中運用是十分重要的.定義:任何二端有徑且只有一條徑的圖稱為樹.性質(zhì):1.樹是最小聯(lián)結(jié)網(wǎng).最小:去一邊則不聯(lián)結(jié)2.樹中定無環(huán).據(jù)定義:二端只一徑3.m=n-1(m:樹的邊數(shù),n:端數(shù))用數(shù)學(xué)歸納法可證:對n=2(最少端)顯然成立若n-1成立則m=n-2

則對n:

端度數(shù)至少為1d(vi)

1

所有端不能全為d(vi)

2

至少有1個端為d(vi)=1

移去此端及其關(guān)聯(lián)邊,留下仍為樹,此時有n-1端(m=n-2)

所以對n有m=n-14.除單點樹，至少有兩個度數(shù)為1的端樹枝:樹上的邊(branch)主樹:(SpainningTree)

考慮T是G的子圖，若T

G,且T包含G的所有端,稱T是G的主樹.

只有聯(lián)結(jié)圖才有主樹,反之有主樹的圖必為聯(lián)結(jié)圖

一般主樹不止一個,至少一個

主樹上任二端間添加一條樹支以外的邊,則形成環(huán)(circuit)

連枝—主樹外任一邊稱主樹的連枝連枝集—樹補(bǔ)(Cotree),不同主樹對應(yīng)不同連枝集

圖的階與空度階—主樹樹枝數(shù)=

T

=n-1=

—表示主樹大??；空度—主樹之連枝數(shù)=

G-T

=m-n+1=

空度表示主樹覆蓋圖的程度

—連枝多，聯(lián)結(jié)性更好

—主樹覆蓋程度高

=0，G本身即為主樹對非聯(lián)結(jié)圖:分成K個最大聯(lián)結(jié)子圖(K個“部分”),各有主樹

K個主樹集合—G的主林,其余的邊為林補(bǔ)

主林的邊數(shù)——階：

=n-kn=n1+n2+

+nk

=(n1-1)+(n2-1)+

+(nk-1)=n-k

主林的連枝數(shù)———空度：

=m-n+kk=3;

=11-3=8;

=12-11+3=4四、割(cut)某些子集(端集或邊集)聯(lián)結(jié)圖

去掉此類子集

變?yōu)椴宦?lián)結(jié)非聯(lián)結(jié)圖

去掉此類子集

其部分?jǐn)?shù)增加

種類:割端集與割邊集1、割端與端集割端:V,去掉V(連同其關(guān)聯(lián)邊),使G的部分?jǐn)?shù)增加。有的聯(lián)結(jié)圖無割端——不可分圖(網(wǎng)有意義)割端集:幾個端具有割性質(zhì)。有最小化問題最小割端集：最小化的割端集,其真子集不割圖的聯(lián)結(jié)度：最小割端集的端數(shù)目2、

割邊集與割集聯(lián)結(jié)圖G的邊子集S’,去掉S’使G為不聯(lián)結(jié),稱S’為割邊集；若S的任一真子集不具割的性質(zhì)，稱S為割集。最小化：S:minimal{e:G-{e}為不聯(lián)結(jié)}

min——再減邊,非割,

mal——再加邊,真子集割更一般化,對任意G:

(G)-

(G-S)=1最小割集——割集中邊數(shù)最小的結(jié)合度——最小割集的邊數(shù),表示聯(lián)通度,結(jié)合度

聯(lián)通度好3．基本割集與基本環(huán)（討論聯(lián)結(jié)圖）1）設(shè)T為聯(lián)結(jié)圖G的一個主樹，取主樹的一邊（枝）與某些連枝，定可構(gòu)成割集，此割集稱為基本割集?；颍夯靖罴呛鳂銽之一個樹枝的割集。主樹T={}連枝：,基本割集：（,）,(,,),(,),(,)基本割集數(shù)=樹枝數(shù)=n-1，有n-1個基本割集。共連枝的基本割集兩兩環(huán)和為割集不共連枝的基本割集兩兩環(huán)和為割集之并n個基本割集與樹枝一一對應(yīng)，因而它們線性無關(guān)以n-1個基本割集為基，其線性組合（環(huán)合）可生成一個子空間，共有個元。每個元或為割集或為不共邊割集之并。二個基本割集之環(huán)合，必含二個樹枝，還可能含連枝。連枝集（e6,e7,e8,e9）

e6—c1={e6,e1,e3,e2}e7—c2={e7,e3,e4}

e8—c3={e8,e3,e2}

e9—c4={e9,e4,e3}2）基本環(huán)

T為聯(lián)結(jié)圖G的一個主樹，G-T為連枝集取一連枝+某些樹枝

基本環(huán)（包含唯一連枝的閉徑稱基本環(huán)）基本環(huán)：每個基本環(huán)只取一個連枝---與連枝一一對應(yīng)，其數(shù)目=連枝數(shù)，共m-n+1個基本環(huán)之間線性無關(guān)，環(huán)合或為環(huán)，或為不共邊環(huán)之并，以此做基可得個元的子空間。

對偶圖：聯(lián)結(jié)圖G1與G2G1中每個無重端環(huán)

---

對應(yīng)G2中每個割集，反之亦然，稱G1與G2為對偶圖。

G1:G2:

環(huán)(e1,e2,e3)

--

割集(e1,e2,e3)

環(huán)(e3,e4,e5)

--

割集（e3,e4,e5)

環(huán)（e1,e2,e5,e4)

--

割集（e1,e2,e5,e4)G1:G2:有重端環(huán)（非初等環(huán)）對應(yīng)對偶圖上的割邊集，但非割集（真子集無割）。構(gòu)造對偶圖：關(guān)于圖的平面性平面圖：畫在平面上，除端點外，邊不相交的圖

平面圖把全平面分成s個區(qū)域（含開區(qū)域）設(shè)有m邊，n端，聯(lián)結(jié)，則s=m-n+2——尤拉公式

m=4,n=4,s=2歸納法證：s=1,無環(huán)，為樹，m=n-1成立；設(shè)s-1成立對s：∵s>2∴定有環(huán)去環(huán)一邊，余m-1邊，區(qū)數(shù)為s-1,

有s-1=(m-1)-n+2,即s=m-n+2

證畢。

▲

對無重邊（平行），無自環(huán)的聯(lián)結(jié)平面圖，有m<=3n-6(n>=3)證：形成區(qū)域至少3邊，區(qū)域周線上的邊數(shù)至少3s(不考慮區(qū)域共邊)，實際每邊均在二區(qū)域周線上，最多有2m邊（周線上）?？紤]區(qū)域共邊，有，代入尤拉公式得m<=3n-6

此為平面圖的必要，非充分條件五、圖的矩陣表示

1、全關(guān)聯(lián)陣與關(guān)聯(lián)陣--端（行）于與邊（列）的關(guān)系

G:n端,m邊 端----行i(n行) 邊----列j(m列)

全關(guān)聯(lián)陣 其中:無向圖

有向圖

▲i行非零元個數(shù)----端度數(shù)▲i行均0元--為孤立端,G為非聯(lián)結(jié)圖▲i行只一個非0元----為懸掛邊端▲列非0元和為0或偶數(shù)(邊與二端相關(guān)聯(lián)) ▲中n-1行之和比等于余下之行,所以只有n-1行線性無關(guān),秩為n-1。全關(guān)聯(lián)陣(聯(lián)結(jié)圖)中去任一行

關(guān)聯(lián)陣A

▲A中非奇異方陣---主樹如:主樹數(shù)=│AAT│▲主樹數(shù)直接求算方法

a)寫出端-端方陣(nxn)(對角線元素=端度數(shù),其它元素)

b)e陣任一對角線元素之余子式=主樹數(shù)

前例:

5邊取3數(shù),===10,其中8種為主樹

▲n端全聯(lián)結(jié)圖主樹數(shù)S=

│AAT│=

如:n=5,==125,主樹主樹邊n-1=4,全聯(lián)結(jié)邊數(shù)==1010邊中取4數(shù)===210種即此210個4邊集中有125種為主樹

主樹數(shù)S=│AAT│證：A==,==

式中==++…+=

式中,,…,在1~m中任取，

│B│中之對應(yīng)A中所有可能的方陣，n-1邊含重邊（重列）▲

其中，取有重列的，相關(guān)，顯然│B│=0▲不重列，若n-1邊不構(gòu)成主樹，│B│=0（見結(jié)論前）▲

不重列，主樹，對角線為1,其余0,1,或-1,列線性無關(guān)，經(jīng)初等變換可為三角行列式,│B│=1

對有向圖：

直接求法：2)找到n-1個基本割集()=(e1e5)()=(e2e3)()=(e4e3e5)

3)用基本割集的連枝置換割集內(nèi)的主樹枝，得與t距離為1的主樹族尋找所有主樹的置換法1）任找一參考主樹t0=(e1e2e4)e5換e1=(e5e2e4)e3換e2=(e3e4e1)

e3換e4=(e3e1e2)

e5換e4=(e5e1e2)4)置換新主樹，得與距離為2的主樹族（1）的基本割集()=(e2,e3)()()=(e2,e3),e3換e2

得=(e3e4e5)的基本割集()=(e1e4e3)()()=(e3,e4),e3換e4得=(e3

e2e5)的基本割集()=(e1,e5)()()=,已不可換,換畢.（2）的基本割集2、割陣與環(huán)陣 若G=（V，E），是V的非空子集，其間割集S=<,>(內(nèi)端與內(nèi)端間邊集)此割方向定為:

若割上邊也是,則稱此邊與割S方向相同。割陣:▲對應(yīng)一棵主樹▲基本割集∽邊,即(n-1)xm陣 ▲基本割集方向----取主樹枝方向

Q=有向=無向=

如右下圖，主樹（e2e3

e5

e6）

e2割=（e1e2

）,方向為(v-),即e2方向

e3割=（e1

e3

e4

）,方向為(v-),即e3方向

e5割=（e4e5e7）,方向為e5方向

e6割=（e6e7

）,方向為e6方向

重排Q矩陣得:其中幺陣I為(n-1)(n-1),

為(n-1)(m-n+1)

行向量環(huán)和為割集環(huán)陣:▲對應(yīng)主樹▲基本環(huán)∽邊,即(m-n+1)m陣 ▲基本環(huán)方向取連枝方向如圖:主樹(e2e3

e5

e6)

e1

:=(e1e3e2),e1方向,順時針 =(e4e3e5),e4方向,順