離散數(shù)學(xué)圖的基本概論(編輯修改稿)
2025-02-12 20:24 本頁面
【文章內(nèi)容簡(jiǎn)介】 通關(guān)系是頂點(diǎn)集 V上的 等價(jià)關(guān)系 。 (1) 自反性 ：由于規(guī)定任何頂點(diǎn)到自身總是連通的； 證明 ： (2) 對(duì)稱性 ：無向圖中頂點(diǎn)之間的連通是相互的； (3) 傳遞性 ：由連通性的定義可知。 連通分支 ：無向圖 G中每個(gè)劃分塊稱為 G的一個(gè)連通分支 ， p(G)表示連通分支的個(gè)數(shù) 。 p(G) = 1為連通圖 。 點(diǎn)割集 ：無向圖 G = V,E 為連通圖 ， 如果 V39。?V，且在 G中刪除 V39。中所有頂點(diǎn) (包括與該頂點(diǎn)關(guān)聯(lián)的邊 )后所得子圖是不連通的或是平凡圖 ， 而刪除 V39。中任何真子集中的頂點(diǎn)時(shí) ，所得子圖仍連通 ， 則 V39。是 G的點(diǎn)割集 。 如果點(diǎn)割集中只有一個(gè)頂點(diǎn)，該點(diǎn)為割點(diǎn)。 四、連通圖的連通度 點(diǎn)連通度 ： G為無向連通圖，記 k(G) = min{|V39。| V39。是 G的點(diǎn)割集 }，稱 k(G)為 G的 點(diǎn)連通度 。 由定義知，點(diǎn)連通度即使 G不連通的需刪除頂點(diǎn)的最少數(shù)目。 完全圖 Kn的連通度 k(G) = n–1。 存在割點(diǎn) 的連通圖連通度為 1， 分離圖 的連通度為 0； 邊割集 ：設(shè)無向圖 G = V,E 連通 ， 邊集 E39。?E，在 G中刪除 E39。中所有邊后所得子圖不連通 ， 而刪除 E39。中的任何子集中的邊后 ，所得子圖仍連通 ， 則 E39。為 G的邊割集 。 如果 邊割集中只有一邊時(shí)，該邊為割邊(或橋 ) 邊連通度 ：設(shè) G為無向連通圖，記 ?(G) = min{| E39。 | E39。是 G的邊割集 }， ?(G)為 G的邊連通度。 連通度的性質(zhì) ： k(G) ? ?(G) ? ? (G) 五、有向圖的連通性： (1) 如果有向圖 D = V,E 中所有有向邊的方向去掉后所得圖為無向連通圖，則說 D為弱連通圖 。 (2) u,v?V， 如果存在 u到 v的一條通路，則說 u可達(dá) v。 (3) 弱連通圖 V,E 中 ， 任何一對(duì)頂點(diǎn)之間，至少有一頂點(diǎn)可達(dá)另一個(gè)頂點(diǎn)，則 V,E 是 單向連通 的； 任何兩個(gè)頂點(diǎn)之間互相可達(dá)，稱 V,E 強(qiáng)連通 。 有向連通圖的性質(zhì) ： (1) 強(qiáng)連通一定單向連通，單向連通一定弱連通。反過來都不成立。 (2) 有向圖 D強(qiáng)連通，當(dāng)且僅當(dāng) D中存在一條回路，它至少經(jīng)過每個(gè)頂點(diǎn)一次。 (充分性 ) 如果 D中存在回路 C， 它經(jīng)過 D中的每個(gè)頂點(diǎn)至少一次 ， 則 D中的任意兩個(gè)頂點(diǎn)都在回路中 ， 所以 ， D中任意兩個(gè)頂點(diǎn)都是可達(dá)的 ， 因而 D是強(qiáng)連通的 。 證明 ： 因?yàn)?vi可達(dá) vi+1, i=1,2,… ， n–1，讓這些通路首尾相連 ， (2) 有向圖 D強(qiáng)連通，當(dāng)且僅當(dāng) D中存在一條回路，它至少經(jīng)過每個(gè)頂點(diǎn)一次。 (必要性 ) D是強(qiáng)連通的，則 D中任何兩個(gè)頂點(diǎn)都是可達(dá)的。 則得一回路。顯然每個(gè)頂點(diǎn)在回路中至少出現(xiàn)一次。 證明 ： 所以 vi到 vi+1存在通路， 不妨設(shè) D中的頂點(diǎn) 為 v1,v2,…, vn， 且 vn到 v1也存在通路， 圖的矩陣表示 鄰接矩陣 ：設(shè) G = V,E 是一個(gè)簡(jiǎn)單圖，它有n個(gè)頂點(diǎn)， V = {v1,v2,…, vn}， 令 aij = 1 vi, vj ?E (或 (vi, vj)?E) 0 vi, vj ?E (或 (vi, vj)?E) 稱 A(G) = (aij) 為 G的鄰接矩陣。 一、鄰接矩陣及其性質(zhì) 鄰接矩陣的特性：在無向圖中： (1) 鄰接陣是對(duì)稱陣； (2) 同一行或者同一列的元素和為對(duì)應(yīng)頂點(diǎn)的度數(shù) ；或即 )()( jn1iijin1jij vdavda ?? ????(3) 矩陣中所有元素的和為邊數(shù)的 2倍 )(2n1jn1iij 握手定理即 ma ?? ?? ?在有向圖中： (1) 同一行的元素和為對(duì)應(yīng)頂點(diǎn)的出度 (2) 同一列的元素和為對(duì)應(yīng)頂點(diǎn)的入度 )( in1jij vda????即)( jn1iij vda????即(3) ? ? aij = 2 m (邊的數(shù)目 ) 鄰接矩陣可推廣到多重圖或帶權(quán)圖，這時(shí)令 aij為 vi到 vj的邊的重?cái)?shù)或邊上的權(quán)值W(vi, vj)。 鄰接陣多用于有向圖。 關(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)nxm為 G的 關(guān)聯(lián)矩陣 。 vi 關(guān)聯(lián) ej vi 不關(guān)聯(lián) ej 二、關(guān)聯(lián)矩陣及其性質(zhì) (2) 設(shè) D = V,E 是有向圖且無環(huán)，令： mij = 1 0 則稱 M(D) = (mij)nxm為 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)矩陣的性質(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(握手定理 ) 有向圖的關(guān)聯(lián)矩陣的性質(zhì) ： 0,2,10)1( ijn1iij ???????mmjm ，從而， ?)()1()2( im1jij vdm?
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1