圖的連通性和性質(zhì)

1、圖的連通性和性質(zhì)12主要內(nèi)容一、割邊、割點和塊二、圖的連通度與敏格爾定理三、圖的寬直徑簡介教學(xué)時數(shù)安排6學(xué)時講授本章內(nèi)容圖的連通性刻畫3本次課主要內(nèi)容(一)、割邊及其性質(zhì)(二)、割點及其性質(zhì)(三)、塊及其性質(zhì)割邊、割點和塊4研究圖的連通性的意義 研究圖的連通性，主要研究圖的連通程度的刻畫，其意義是： 圖論意義：圖的連通程度的高低，是圖結(jié)構(gòu)性質(zhì)的重要表征，圖的許多性質(zhì)都與其相關(guān)，例如：連通圖中任意兩點間不相交路的條數(shù)就與圖的連通程度有關(guān)。 實際意義：圖的連通程度的高低，在與之對應(yīng)的通信網(wǎng)絡(luò)中，對應(yīng)于網(wǎng)絡(luò)“可靠性程度”的高低。 網(wǎng)絡(luò)可靠性，是指網(wǎng)絡(luò)運作的好壞程度，即指如計算機網(wǎng)絡(luò)、通信網(wǎng)絡(luò)等對某個

2、組成部分崩潰的容忍程度。 網(wǎng)絡(luò)可靠性， 是用可靠性參數(shù)來描述的。參數(shù)主要分確定性參數(shù)與概率性參數(shù)。5 確定性參數(shù)主要考慮網(wǎng)絡(luò)在最壞情況下的可靠性度量，常稱為網(wǎng)絡(luò)拓撲的“容錯性度量”，通常用圖論概念給出，其中，本章將介紹的圖的連通度就是網(wǎng)路確定性參數(shù)之一。近年來，人們又提出了“堅韌度”、“核度”、“整度”等描述網(wǎng)絡(luò)容錯性的參數(shù)。 概率性參數(shù)主要考慮網(wǎng)絡(luò)中處理器與信關(guān)以隨機的、彼此獨立的按某種確定性概率損壞的情況下，網(wǎng)絡(luò)的可靠性度量，常稱為網(wǎng)絡(luò)拓撲的“可靠性度量”。(一)、割邊及其性質(zhì) 定義1 邊e為圖G的一條割邊，如果 。紅色邊為該圖的割邊6 注：割邊又稱為圖的“橋”。 圖的割邊有如下性質(zhì)： 定

3、理1 邊 e 是圖G的割邊當(dāng)且僅當(dāng) e 不在G的任何圈中。 證明：可以假設(shè)G連通。 若不然。設(shè) e 在圖G的某圈 C 中，且令e = u v. 考慮P = C- e,則P是一條u v路。下面證明G-e連通。 對任意 x, y V(G-e) 由于G連通，所以存在x -y路Q.若Q不含e，則x與y在G-e里連通；若Q含有e，則可選擇路：x -u P v - y,說明x與y在G-e里也連通。所以,若邊e在G的某圈中，則G-e連通。 但這與e是G的割邊矛盾！ “必要性”7 “充分性” 如果e不是G的割邊，則G-e連通，于是在G-e中存在一條u - v 路，顯然：該路并上邊e得到G中一個包含邊e的圈，矛

4、盾。 推論1 e為連通圖G的一條邊，如果e含于G的某圈中，則G-e連通。 證明：若不然，G-e不連通，于是e是割邊。由定理1，e不在G的任意圈中，矛盾！ 例1 求證: (1) 若G的每個頂點的度數(shù)均為偶數(shù)，則G沒有割邊; (2) 若G為k正則二部圖(k2)，則G無割邊。 證明: (1)若不然，設(shè)e=uv 為G的割邊。則G-e的含有頂點u的那個分支中點u的度數(shù)為奇，而其余點的度數(shù)為偶數(shù)，與握手定理推論相矛盾！8 (2)若不然，設(shè)e=uv 為G的割邊。取G-e的其中一個分支G1, 顯然，G1中只有一個頂點的度數(shù)是k-1,其余點的度數(shù)為k。并且G1仍然為偶圖。 假若G1的兩個頂點子集包含的頂點數(shù)分別

5、為m與n，并且包含m個頂點的頂點子集包含度為k-1的那個點，那么有：k m-1= k n。但是因k2，所以等式不能成立！ 注：該題可以直接證明G中任何一條邊均在某一圈中，由定理1得出結(jié)論。邊割集簡介 邊割集跟回路、樹等概念一樣，是圖論中重要概念。在應(yīng)用上，它是電路網(wǎng)絡(luò)圖論的基本概念之一。所以，下面作簡單介紹。9 定義2 一個具有n個頂點的連通圖G,定義n-1為該連通圖的秩；具有p個分支的圖的秩定義為n-p。記為R(G)。 (1) R (G-S) = n-2; 定義3 設(shè)S是連通圖G的一個邊子集，如果： (2) 對S的任一真子集S1,有R(G-S1)=n-2。 稱S為G的一個邊割集，簡稱G的一個

6、邊割。 例2 邊子集：S1=a, c, e, S2=a, b, ,S3=f是否是下圖G的邊割？agedcbhfi圖G10 定義6 設(shè)G是連通圖，T是G的一棵生成樹。如果G的一個割集S恰好包含T的一條樹枝，稱S是G的對于T的一個基本割集。11 例如：在圖G中fedcba圖G G的相對于T的基本割集為： a , e, f , c, f, b , e, d.(二)、割點及其性質(zhì) 定義7 在G中，如果E(G)可以劃分為兩個非空子集E1與E2,使GE1和GE2以點v為公共頂點，稱v為G的一個割點。12 在圖G1中，點v1,v2均是割點；在G2中，v5是割點。v1v2v3v4e3e1e2e4e5e6圖G1

7、v1v3v2v4v5圖G2 定理6 G無環(huán)且非平凡，則v是G的割點，當(dāng)且僅當(dāng) 證明：“必要性” 設(shè)v是G的割點。則E(G)可劃分為兩個非空邊子集E1與E2,使GE1,GE2恰好以v為公共點。由于G沒有環(huán)，所13以，GE1,GE2分別至少包含異于v的G的點，這樣，G-v的分支數(shù)比G的分支數(shù)至少多1，所以： “充分性” 由割點定義結(jié)論顯然。 定理7 v是樹T的頂點，則v是割點，當(dāng)且僅當(dāng)v是樹的分支點。 證明：“必要性” 若不然，有deg(v)=1,即v是樹葉，顯然不能是割點。 “充分性” 設(shè)v是分支點，則deg(v)1.于是設(shè)x與y是v的鄰點，由樹的性質(zhì)，只有唯一路連接x與y，所以G-v分離x與y

8、 .即v為割點。14 定理8 設(shè)v是無環(huán)連通圖G的一個頂點，則v是G的割點，當(dāng)且僅當(dāng)V(G-v)可以劃分為兩個非空子集V1與V2,使得對任意x V1, y V2, 點v在每一條x y路上。 證明：“必要性” v是無環(huán)連通圖G的割點，由定理6，G-v至少有兩個連通分支。設(shè)其中一個連通分支頂點集合為V1,另外連通分支頂點集合為V2,即V1與V2構(gòu)成V的劃分。 “充分性” 對于任意的x V1, y V2，如果點v不在某一條xy路上，那么，該路也是連接G-v中的x與y的路，這與x,y處于G-v的不同分支矛盾。 若v不是圖G的割點，那么G-v連通，因此在G-v中存在x,y路，當(dāng)然也是G中一條沒有經(jīng)過點v

9、的x,y路。矛盾。15 例5 求證：無環(huán)非平凡連通圖至少有兩個非割點。 證明： 由于G是無環(huán)非平凡連通圖，所以存在非平凡生成樹，而非平凡生成樹至少兩片樹葉，它不能為割點，所以，它也不能為G的割點。 證明：設(shè)T是G的一棵生成樹。由于G有n-2個割點，所以，T有n-2個割點，即T只有兩片樹葉，所以T是一條路。這說明，G的任意生成樹為路。 例6 求證：恰有兩個非割點的連通單圖是一條路。 一個單圖的任意生成樹為路，則該圖為圈或路，若為圈，則G沒有割點，矛盾，所以，G為路。 例7 求證：若v是單圖G的割點，則它不是G的補圖的割點。16 證明： v是單圖G的割點，則G-v至少兩個連通分支。現(xiàn)任取 , 如果

10、x,y在G-v的同一分支中，令u是與x,y處于不同分支的點，那么，通過u，可說明，x與y在G-v的補圖中連通。若x,y在G-v的不同分支中，則它們在G-v的補圖中鄰接。所以，若v是G的割點，則v不是其補圖的割點。(三)、塊及其性質(zhì) 定義8 沒有割點的連通圖稱為是一個塊圖，簡稱塊；G的一個子圖B稱為是G的一個塊，如果(1), 它本身是塊；(2), 若沒有真包含B的G的塊存在。 例7 找出下圖G中的所有塊。17 解：由塊的定義得：圖G18 定理9 若|V(G)|3,則G是塊，當(dāng)且僅當(dāng)G無環(huán)且任意兩頂點位于同一圈上。 證明：(必要性）設(shè)G是塊。因G沒有割點，所以，它不能有環(huán)。對任意u, v V(G)

11、,下面證明u, v位于某一圈上。 對d (u, v) 作數(shù)學(xué)歸納法證明。 當(dāng)d (u, v) =1時，由于G是至少3個點的塊，所以，邊uv不能為割邊，否則，u或v為割點，矛盾。由割邊性質(zhì)，uv必然在某圈中。 設(shè)當(dāng)d (u, v) k時結(jié)論成立。 設(shè)當(dāng)d (u, v) =k。 設(shè)P是一條最短(u, v)路，w是v前面一點，則d (u, v) =k-119 由歸納假設(shè)，u與w在同一圈C =P1P2上。uwvPP2P1 考慮G-w. 由于G是塊，所以G-w連通。設(shè)Q是一條在G-w中的(u, v)路，并且設(shè)它與C的最后一個交點為x。uwvQP2P1x20 則uP1xvwP2為包含u, v的圈。 (充分

12、性)：若G不是塊，所以G中有割點v。由于G無環(huán)，所以G-v至少兩個分支。設(shè)x, y是G-v的兩個不同分支中的點，則x, y在G中不能位于同一圈上，矛盾！ 定理10 點v是圖G的割點當(dāng)且僅當(dāng)v至少屬于G的兩個不同的塊。 證明：(必要性) 設(shè)v是G的割點。由割點定義：E(G)可以劃分為兩個邊子集E1與E2。顯然GE1與GE2有唯一公共頂點v。設(shè)B1與B2分別是GE1和GE2中包含v的塊，顯然它們也是G的塊。即證明v至少屬于G的兩個不同塊。 (充分性) 如果v屬于G的兩個不同塊，我們證明：v 一定是圖G的割點。21 如果包含v的其中一個塊是環(huán)，顯然v是割點； 設(shè)包含v的兩個塊是B1與B2。如果包含v的兩個塊不是環(huán)，那么兩個塊分別至少有兩個頂點。假如v不是割點，在B1與B2