【文章內(nèi)容簡介】 如果從 vi到 vj (vi?vj)存在通路，則必存在從 vi到 vj 的 長度小于等于 n–1的 初級 通路 。（簡單通 路 ？ ） (3) 在 n階圖中，如果存在從 vi到自身的回路，則從 vi 到自身存在 長度小于等于 n的回路 。 (4) 在 n階圖中，如果從 vi到自身存在一條簡單回路，則從 vi 到自身存在 長度小于等于 n的 初級回路 。 思考 ： 在 n階圖中，若兩點之間存在 初級 通路，則其長度 一定 小于等于 n–1？ 若為簡單通路 ？ 思考 ： 在 n階圖中，如果從 vi到自身存在一條初級回路，則從 vi 到自身的長度 一定 小于等于 n？ （簡單回路？） 兩頂點連通 ： u,v為無向圖 G的兩個頂點， u到 v存在一條通路。 連 通 圖 ： G 中 任何兩個頂點是連通 的；否則是 分離圖 。 三、無向圖的連通性 連通分支 ：無向圖 G中每個劃分塊稱為 G的一個連通分支 ， p(G)表示連通分支的個數(shù) 。p(G) = ？ 為連通圖 。 連通性的性質(zhì) ：無向圖中頂點之間的連通關(guān)系是頂點集 V上的 等價關(guān)系 。 (1) 自反性 ：由于規(guī)定任何頂點到自身總是連通的； 證明 ： (2) 對稱性 ：無向圖中頂點之間的連通是相互的； (3) 傳遞性 ：由連通性的定義可知。 四、有向圖的連通性 ： (1) 如果有向圖 D = V,E 中 所有有向邊的方向去掉后所得圖為 無向連通圖 ，則說 D為 弱連通圖 。 (2) 弱連通圖 V,E 中 ， 任何一對頂點之間，至少有一頂點可達(dá)另一個頂點 ，則 V,E 是 單向連通 的； (3)任何兩個頂點之間互相可達(dá) ，稱 V,E 強(qiáng)連通 。 思考： 弱連通、單向連通、強(qiáng)連通關(guān)系 ？ 圖 1 圖 2 圖 3 v1 v1 v1 v2 v2 v2 v3 v3 v3 v4 v4 v4 有向連通圖的判定 ： 僅僅 弱連通 :有向連通圖中至少有兩個以上頂點為全入度或全出度 單向連通 :依次從各頂點出發(fā) ,尋找到其他所有頂點的可達(dá)性 .(存在經(jīng)過每點至少一次的通路 ) 強(qiáng)連通的充要條件 :當(dāng)且僅當(dāng) D中存在一條回路，它至少經(jīng)過每個頂點一次 .(存在經(jīng)過每點至少一次的回路 ) 有向圖 D強(qiáng)連通，當(dāng)且僅當(dāng) D中存在一條回路，它至少經(jīng)過每個頂點一次。 (充分性 ) 如果 D中存在回路 ， 它經(jīng)過 D中的每個頂點至少一次 ， 則 D中的任意兩個頂點都在回路 中 ，以 ， D中任意兩個頂點都是可達(dá) ， 因而 D是強(qiáng)連通 。 (必要性 ) D是強(qiáng)連通的，則 D中任何兩個頂點都是可達(dá)的 。不妨設(shè) D中的頂點為 v1,v2,…,vn ， 因為 vi可達(dá) vi+1, i=1,2,… ， n–1， 讓這些通路首尾相連，所以vi到 vi+1存在通路，且 vn到 v1也存在通路，則得 一回路 。顯然每個頂點在回路中至少出現(xiàn)一次。 證明 ： 點割集 ：無向圖 G = V,E ， 如果存在頂點集 V‘?V 1) 在 G中 刪除 V’中所有頂點 (包括與該頂點關(guān)聯(lián)的邊 )后 所得子圖 GV’的連通分支數(shù)與 G的連通分支數(shù)滿足 P(GV’)P(G)， 2)而 刪除 V‘中任何 真子集 V”后 P(GV”)=P(G) ，則 V39。是 G的點割集 。 如果點割集中只有一個頂點，該點為 割點 。 五、割集 思考： 如果點割集中頂點 1，點割集中會含割點嗎？ 邊割集 ：設(shè)無向圖 G = V,E ， 存在邊集 E‘?E 1) 在 G中 刪除 E’中所有邊 (不包括邊關(guān)聯(lián)的頂點 )后所得子圖 GE’的連通分支數(shù)與 G的連通分支數(shù)滿足 P(GE’)P(G)， 2） 而 刪除 E‘中任何真子集 E”后 P(GE”)=P(G) ， 則 E’是 G的邊割集 。 如果 邊割集中只有一邊時，該邊為 割邊 (或橋 ) 思考： 如果邊割集中邊數(shù) 1，邊割集中會含割邊嗎？ 1) {V2, V4 }是點割集 ？ 2) {V6, V1, V5}是點割集 ？ V6是割點 ？ V1？ V5？ 3) {e9, e7, e8}是邊割集 ？ e9是割邊 ？ 4) {e8, e7}是邊割集 ？ {e8, e7， e1}是邊割集 ? e3 e1 e2 e4 e5 v4 v1 v2 v3 v5 v6 v7 e6 e8 e7 e9 點割集中不會含其有它點割集 ？ 邊割集中不會含有其他邊割集 ？ 看 P 292 21 (1) .43 無向圖 關(guān)聯(lián)矩陣 ： (1) 設(shè) G = V,E 為 (n,m)無向圖 , V = {v1,v2,…, vn}, E = {e1, e2,…, em}, 令： mij = 1 0 稱 M(G) = (mij)n m為 G的 關(guān)聯(lián)矩陣 。 vi 關(guān)聯(lián) ej（ 環(huán) ?2） vi 不關(guān)聯(lián) ej 一、關(guān)聯(lián)矩陣及其性質(zhì) 圖的矩陣表示 v4 e1 e2 e3 e4 e5 v1 v2 v3 強(qiáng)調(diào)： 頂點與邊的關(guān)系 ， (mij)n m行 n為 ？ m為 ？ 無向圖的關(guān)聯(lián)矩陣的性質(zhì) ： ))(,2,1(2)1(n1iij 每條邊關(guān)聯(lián)兩個頂點mjm ?????))(()2( iim1jij 的度數(shù)vvdm ?????????n1iiij )(2)3( vdmm是孤立點當(dāng)且僅當(dāng)???m1jiij 0)4( vm為平行邊與列相同，說明列與第若第 kj)5( eekj(?定理 ) v4 e1 e2 e3 e4 e5 v1 v2 v3 1 1 1 0 0 0 1 1 1 0 1 0 0 1 2 0 0 0 0 0 (?圖與矩陣 ) (2) 設(shè) D = V,E 是有向圖且 無環(huán) ，令： mij = 1 0 則稱 M(D) = (mij)n m為 D的 關(guān)聯(lián)矩陣 。 –1 D中 vi 是 ej 的始點 vi 與 ej 不關(guān)聯(lián) vi 是 ej 的終點 有向圖 關(guān)聯(lián)矩陣 v1 v4 v3 v2 e1 e2 e3 e4 強(qiáng)調(diào)： 頂點與邊的關(guān)系 ， (mij)n m行 n為 ？ m為 ？ 有向圖的關(guān)聯(lián)矩陣的性質(zhì) ： 0,2,10)1( ijn1iij ???????mmjm ，從而， ?)()1()2( im1jij vdm?????mvdm ??? ?? ???? ?n1iin1im1jij )()1(從而有)()1( im1jij vdm???????mvdm ?????? ?? ???? ?n1iin1im1jij )()1(孤立點 ？ 兩列相同 ？ 有向圖的關(guān)聯(lián)矩陣所有元素之和為 ？ v1 v4 v3 v2 e1 e2 e3 e4 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 (?圖與矩陣 ) 鄰接矩陣 ：設(shè) G = V,E 是一個圖，它有 n個頂點， V = {v1,v2,…, vn}， 令 aij = x vi, vj ?E (或 (vi, vj)?E 環(huán) ?2) 0 vi, vj ?E (或 (vi, vj)?E) 稱 A(G) = (aij) 為 G的 鄰接矩陣 。 二、鄰接矩陣及其性質(zhì) v1 v4