資源描述：
《圖的連通性和矩陣表示及計算》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、圖的連通性和矩陣表示及計算3.2圖的連通性3.2.1連通性如未說明,則本節(jié)的圖G均是指無向圖.定義3.2.1圖G=中,設(shè)有結(jié)點vj與vk,若從vj到vk存在任何一條路徑,則稱結(jié)點vk從結(jié)點vj可達,也稱結(jié)點vj與vk是連通的.約定,對任意結(jié)點v,v與v是連通的.定義3.2.2若G是平凡圖或G中任意兩個結(jié)點都是連通的,則稱G是連通圖,否則,稱G為非連通圖或分離圖.定義3.2.3設(shè)G=是圖,連通關(guān)系的商集為｛V1,V2,...,Vm｝,則其導(dǎo)出的子圖G(Vi)(i=1,2,...,m)稱為圖G的連通分支
2、,將圖G的連通分支數(shù)記作W(G).顯然,如果圖G只有一個連通分支,則G是連通圖.見例1定義3.2.4設(shè)u與v是圖G的兩個結(jié)點,若u與v連通,則稱u與v之間長度最短的路為u與v之間的短程線.短程線的長度可作為結(jié)點u與v間的距離,記作d(u,v).其滿足下列性質(zhì):d(u,v)≥0,u=v時,d(u,v)=0(非負性)d(u,v)=d(v,u)(對稱性)d(u,v)+d(v,w)≥d(u,w)(三角不等式)若u與v不連通,則通常記作d(u,v)=∞.見例2無向圖的連通性不能直接推廣到有向圖.在有向圖G中,可達性是結(jié)點集上的二
3、元關(guān)系,其為自反的和傳遞的,但不是對稱的,因若從u到v有一條路時,不一定必有v到u的一條路,故有向圖的可達性不是等價關(guān)系.若u,v可達,其間可能不止一條路,在所有這些路中,最短路的長度稱為結(jié)點u與v間的距離,記作d.其滿足下列性質(zhì):(1)d≥0;(2)d=0;(3)d+d≥d;(4)若u不可達v,則通常記作d=∞;(5)若u可達v,且v可達u時,d不一定等于d.見例3定義3.2.5在簡單有向圖中,若在任何結(jié)點偶對中,至少從一個結(jié)點
4、到另一個結(jié)點是可達的,則稱圖G是單向(側(cè))連通的.若在任何結(jié)點偶對中,兩結(jié)點對互相可達,則稱圖G是強連通的;若圖G的底圖,即在圖G中略去邊的方向,得到的無向圖是連通的,則稱圖G是弱連通的.顯然,強連通的一定是單向連通的和弱連通的,單向連通的一定是弱連通的,但其逆均不真.見例3定理3.2.1一個有向圖是強連通的,當且僅當G有一個回路,且其至少包含每個結(jié)點一次證明見書.定義3.2.6在簡單有向圖G=中,G'是G的子圖,如果G'是強連通的(單向連通的、弱連通的),且沒有包含G'的更大的子圖G''是強連通的(單向連通
5、的、弱連通的),則稱G'是極大強連通(單向連通、弱連通)子圖,又叫強分圖(單向分圖、弱分圖).定理3.2.2在有向圖G=中,G的每一結(jié)點都在也只在一個強(弱)分圖中.(在無向圖中,類似的定理也成立)證明見書結(jié)點在同一單向分圖中是相容關(guān)系(具有自反的和對稱的二元關(guān)系).相容關(guān)系把結(jié)點分成最大相容類,最大相容集合是集合V的一個覆蓋.每個最大相容類的結(jié)點導(dǎo)出一極大單向連通子圖,因此有以下定理:定理3.2.3在有向圖G=中,G的每一結(jié)點都處在一個或一個以上的單向分圖中.3.2.2連通度定義3.2.7設(shè)無向圖
6、G=為連通圖,若有點集V1V,使圖G刪除了V1的所有結(jié)點后,所得的子圖是不連通圖,而刪除了V1的任何真子集后,所得的子圖是連通圖,則稱V1是G的一個點割集.若某個結(jié)點構(gòu)成一個點割集,則稱該結(jié)點為割點.見例5定義3.2.8若G為無向連通圖且不含Kn為生成子圖,則稱k(G)=min｛V1｜,其中V1是G的一個點割集｝為G的點連通度(簡稱連通度).規(guī)定:完全圖Kn的點連通度為n,n≥1.非連通圖的點連通度為0.若k(G)≥k,則稱G為k-連通圖.顯然,點連通度k(G)是產(chǎn)生一個不連通圖所需要刪除的點的最少數(shù)目.見例
7、6定義3.2.9設(shè)無向圖G=為連通圖,若有邊集E1E,使圖G刪除了E1的所有邊后,所得的子圖是不連通圖,而刪除了E1的任何真子集后,所得的子圖是連通圖,則稱E是G的一個邊割集.若某個邊構(gòu)成一個邊割集,則稱該邊為割邊(或橋).見例7定義3.2.10若G為無向連通圖,則稱λ(G)=min｛
8、E1
9、｜,其中E1是G的一個邊割集｝為G的邊連通度.規(guī)定:非連通圖的邊連通度為0.若λ(G)≥k,則稱G為k邊-連通圖.顯然,邊連通度λ(G)是產(chǎn)生一個不連通圖所需要刪除的邊的最少數(shù)目.定理3.2.4對于任意圖G,有k(G)≤
10、λ(G)≤δ(G)其中,k(G),λ(G),δ(G)分別為G的點連通度、邊連通度和最小度。證明見書定理3.2.5一個連通無向圖G中的結(jié)點v是割點的充分必要條件是存在兩個結(jié)點u和w,使得結(jié)點u與w的每一條路都通過v.證明見書.3.3圖的矩陣表示與運算3.3.1設(shè)G=是一個簡單圖,其中V=｛v1,v2,...,vn｝,則n階
