離散數(shù)學(xué)第八章-(第2講)課件

1、8.2路與圖的連通性1、路的定義：在圖G =中，設(shè)v0，v1，vnV, e1 ,e2 en E ， 其中ei是關(guān)聯(lián)于結(jié)點vi-1,vi的邊，結(jié)點與邊的交替序列v0 e1 v1 en vn稱為聯(lián)結(jié)v0到vn的路。v1v4v5v2v3e1e2e3e4e5e6e7e8v1v4v5v2v3e1e2e3e4e5e6e7e8v0v3v4v1v2e1e2e3e4e5e6e7e8路的其它概念（1）在路 v0 e1 v1 en vn 中，v0和vn分別稱作路的起點與終點。（2）一條路中所有的邊的數(shù)目稱作路的長度。（3）一條路中所有的邊均不相同，則此路稱作跡。（4）一條路中所有的結(jié)點均不相同，則此路稱作通路。 顯

2、然：通路必為跡，而跡不一定是通路。v0v3v4v1v2e1e2e3e4e5e6e7e8路的其它概念（5）在路 v0 e1 v1 en vn 中，若v0= vn 則路稱作回路。（6）除v0= vn 外，其余結(jié)點和所有邊均不相同的回路，稱作圈 (基本回路)。（7） 所有邊均不相同的回路，稱作簡單回路。 顯然：基本回路必為簡單回路，反之，則不然。v0v3v4v1v2e1e2e3e4e5e6e7e8路的表示方法：(a)結(jié)點表示法：(b)邊表示法：例：給出有向圖，求起始于，終止于4的路。在下圖中， ADEBCF；ADEBCEF這兩條路，哪個是通路，哪個是跡？練習(xí)：在下圖中，求v1到v4長度分別為1，2，

3、3的路分別有哪些？練習(xí)：解 ：v1到v4長度分別為1和2的路：沒有。v1到v4長度為3的路一條：v1 v2 v3 v4。定理1：在一個 n 階圖中，如果從結(jié)點u到結(jié)點v存在一條路，則從從結(jié)點u到結(jié)點v必存在一條長度小于等于 n-1條邊的通路。 定理2：在一個 n 階圖中，若存在v到自身的簡單回路，則必存在v到自身長度小于等于n的基本回路。 無向圖的結(jié)點連通性 定義：設(shè)圖為無向圖，且 u , vV ，若從u到v存在任何一條路徑 ，則稱u到v是連通的。 有向圖的結(jié)點可達性 定義：設(shè)圖為簡單有向圖，且u , vV,若從u到v存在任何一條路徑，則稱u到v是可達的。 圖的連通性：（1）連通性與非連通性：

4、若無向圖G是平凡圖，或G中任意兩結(jié)點間都是連通的，則稱圖G是連通圖，否則稱G是是非連通圖。一個有向圖，忽略邊的方向后得到的無向圖若是連通的，則稱該有向圖為連通圖，否則稱非連通圖。 （a）abcd（b）abcd 練習(xí)：已知關(guān)于人員A,B,C,D,E的下述事實：A說英語；B說英語和西班牙語；C說英語，意大利語和俄語；D說日語和西班牙語；E說法語，日語和俄語。試問，上述五個人中是否任意兩人都能交談。（如果必要，可由其余3人所組成的譯員鏈幫忙） （2）連通分支 若無向圖G的每個子圖都是連通圖，稱為G的連通分支。G的分支數(shù)記作p(G) 。（3）強連通，單向連通，弱連通 簡單有向圖G： 如果G的任何兩結(jié)點

5、間均是互相可達的，則稱圖G是強連通的。 如果G的任何兩結(jié)點間至少有一個結(jié)點到另一結(jié)點是可達的。則稱G是單向連通的。 如果忽略邊的方向，將它看成無向圖后，圖是連通的，則稱該圖為弱連通的。 若G是強連通的，則G是單向連通的。若G是單向連通的，則G是弱連通的。 反之，不成立。(b)ABC (c)ABCABC(a)練習(xí)：下列各有向圖是強連通圖的是（）. 定理 ：一個有向圖是強連通的充要條件是：它包含一個回路，該回路至少包含每個結(jié)點一次。ABCD定義：設(shè)，為一簡單有向圖，且是的子圖。 具有強連通性質(zhì)的極大子圖稱為強分圖； 具有單側(cè)連通性質(zhì)的極大子圖稱為單側(cè)圖； 具有弱連通性質(zhì)的極大子圖稱為弱分圖。例：

6、G的強分圖為：1,2,3，4，5，6G的單側(cè)圖為：1,2,3,4,5，5,6G的弱分圖為：1,2,3,4,5,6 定理：在任一簡單有向圖，中，有向 圖的每一個結(jié)點位于且只位于一個強分圖之中。14235定義 設(shè)無向圖G = 是連通無向圖, V1V, 若G V1 不連通或是平凡圖,而對于V1的任何一個非空真子集V2， G V2 是連通的，則稱V1 是G的點割集。 在下圖中, v2, v4 , v3 和 v5 都是點割集, v3和v5都是割點。 若某一個結(jié)點構(gòu)成一個點割集，則稱該結(jié)點為割點。練習(xí)：設(shè)圖G=的結(jié)點集為V=v1,v2,v3,邊集為E=,則G的割點是( ) A.v1 B.v2 C.v3 D

7、.v2,v3 定義：設(shè)G為無向連通圖且為非完全圖, 則稱 (G) = min |V1| | V1 為G的點割集 為G的點連通度, 簡稱連通度。(G)簡記為 。 完全圖Kn(n 1)的點連通度為n-1；規(guī)定非連通圖和平凡圖的點連通度為0；定義 設(shè)無向圖G = 是連通無向圖, E1E, 若G E1 不連通，而對于E1的任何一個非空真子集E2， G E2 是連通的，則稱E1 是G的邊割集。在下圖中, e5 , e6 , e2, e3 , e1, e2 , e3, e4 , e1, e4 , e1, e3 , e2, e4 都是邊割集, 其中e5和e6是橋。 若某一條邊構(gòu)成一個邊割集，則稱該條邊為割邊或橋。定義 設(shè)G為無向連通圖且為非平凡圖, 則稱(G) = min |E1| | E1 為G的邊割集 為G的邊連通度。規(guī)定:非連通圖和平凡圖的邊連通度為(G) = 0；完全圖Kn(n 1)的邊連通度(Kn) =n-1.練習(xí)：下圖的點連通度為 ，邊連通度為_.練習(xí)：分別求出n階完全無向圖Kn的點連通度和邊連通度。解 ：定理： 對于任何無向圖G, 有: (G) (G) (G)。例 (1) 給出一