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