14-圖的基本概念-資料下載頁(yè)
2025-08-05 19:27本頁(yè)面
【正文】 4 部圖 2 部圖 r 部圖 /rpartite graph, 二部圖 /bipartite graph 二部圖 ? ? ? ? ? 完全 r 部圖 : 頂點(diǎn)集劃分成 r 類(lèi) , 同類(lèi)頂點(diǎn)不相鄰 。 不同類(lèi)的頂點(diǎn)都相鄰 . 完全 4 部圖 K1, 2, 2, 3 完全 2 部圖 K3, 4 完全 r 部圖 /plete rpartite graph,完全二部圖/plete rpartite graph. ? ? ? ? ? 2 部圖 V2 V1 完全 2 部圖 K3, 4 2 部圖必然無(wú)環(huán) 完全二部圖 : 頂點(diǎn)集劃分成 2 類(lèi) , 同類(lèi)頂點(diǎn)不相鄰 。 不同類(lèi)的頂點(diǎn)都相鄰 。 且無(wú)平行邊 . G = ?V1, V2, E? 互補(bǔ)頂點(diǎn)子集 : V1, V2. ? ? ? ? ? 例 9 二部圖 ? 同色頂點(diǎn)不相鄰 構(gòu)成兩個(gè)互補(bǔ)頂點(diǎn)子集 因此是二部圖 . 與上圖同構(gòu)的圖 ? ? ? ? ? 由定理 ，哪些是完 全二部圖？哪些圖是同構(gòu)的？ 定理 . 無(wú)向圖 G=V, E 是二部圖當(dāng)且僅當(dāng) G中無(wú)奇圈 . 完 ? ? ? ? ? 1. 非負(fù)性 : d(u, v) ? 0 (當(dāng)且僅當(dāng) u = v 時(shí) , 等號(hào)成立 ). 距離的性質(zhì) : 2. 對(duì)稱(chēng)性 : d(u, v) = d(v, u). 3. 三角不等式 : d(u, v) + d(v, w) ? d(u, w). 完 ? ? ? ? ? 一、無(wú)向圖的關(guān)聯(lián)矩陣（對(duì)圖無(wú)限制） 定義 無(wú)向圖 G=V, E， |V|=n， |E|=m，令 mij 為 vi 與 ej的關(guān)聯(lián)次數(shù)，稱(chēng) (mij)n?m為 G 的關(guān)聯(lián)矩陣，記 為 M(G). 圖的矩陣表示 ? ? ? ? ? v1 v2 v4 v3 e1 e2 e3 e4 e 5 1 1 1 0 00 1 1 1 0()1 0 0 1 20 0 0 0 0MG?????????例 平行邊的列相同)4(2)3(), . . . ,2,1()()2(), . . . ,2,1(2)1(,11mmnivdmmjmjiijimj ijni ij??????????性質(zhì)： ? ? ? ? ? ???????的終點(diǎn)為，不關(guān)聯(lián)與，的始點(diǎn)為jijijiijevevevm10,1有向圖的關(guān)聯(lián)矩陣（無(wú)環(huán)） 定義 有向圖 D=V,E，令 二、有向圖的關(guān)聯(lián)矩陣 則稱(chēng) ( mij )n?m為 D 的關(guān)聯(lián)矩陣，記為 M(D). ? ? ? ? ? ?? ???????????? ????jiijmjmj iijiijni ijmnivdmvdmmjm,1 110)3(,...,2,1),()1(),()1()2(),...,2,1(0)1((4) 平行邊對(duì)應(yīng)的列相同 性質(zhì) v4 v1 v2 v3 e1 e2 e3 e4 e5 1 1 0 0 01 0 1 1 1()0 0 0 0 10 1 1 1 0MD?????????? ????? ? ? ? ? 定義 設(shè)有向圖 D=V,E, V={v1, v2, …, vn}, E={e1, e2, …, em}, 令 ai j為頂點(diǎn) vi 鄰接到頂點(diǎn) vj 邊的條數(shù)，稱(chēng)為 D 的鄰接矩陣，記作 A(D)，或簡(jiǎn)記為 A. 三、有向圖的領(lǐng)接矩陣 ? ? ? ? ? v2 v1 v4 v3 1 2 1 00 0 1 0()0 0 0 10 0 1 0AD?????????????的回路數(shù)中長(zhǎng)度為的通路數(shù)中長(zhǎng)度為1)4(1)3(, . . . ,2,1),()2(, . . . ,2,1),()1(1)1(,)1(1)1(1)1(DaDmanjvdanivdaniiijiijjniijinjij????????????????????? ? ? ? ? 推論 設(shè) Bl=A+A2+…+ Al（ l?1），則 Bl中元素 為 D中長(zhǎng)度為 l 的通路總數(shù)， )(lija)(liia??? ?ninjlija1 1)(??niliia1)(??? ?ninjlijb1 1)(??niliib1)(定理 設(shè) A為有向圖 D 的鄰接矩陣， V={v1, v2, …, vn}為頂點(diǎn)集，則 A 的 l 次冪 Al（ l?1）中元素 為 D中 vi 到 vj長(zhǎng)度為 l 的通路數(shù)，其中 為 vi到自身長(zhǎng)度為 l 的回路數(shù)，而 為 D中長(zhǎng)度小于或等于 l 的回路數(shù) 為 D中長(zhǎng)度小于或等于 l 的通路數(shù) . 鄰接矩陣的應(yīng)用 為 D 中長(zhǎng)度為 l 的回路總數(shù) . ? ? ? ? ? 例 5 有向圖 D如圖所示，求 A, A2, A3, A4，并回答諸問(wèn)題： (1) D 中長(zhǎng)度為 1, 2, 3, 4的通路各有多少條？其中回路分別為多少條？ (2) D 中長(zhǎng)度小于或等于 4的通路為多少條？其中有多少條回路？ 實(shí)例 ? ? ? ? ? ????????????????????????????????????????????????????1004010410050001010310030104000110020102100300010101100101020001432AAAA(1) D中長(zhǎng)度為 1的通路為 8條，其中有 1條是回路 . D中長(zhǎng)度為 2的通路為 11條，其中有 3條是回路 . D中長(zhǎng)度為 3和 4的通路分別為 14和 17條，回路分別 為 1與 3條 . (2) D中長(zhǎng)度小于等于 4的通路為 50條，其中有 8條是回路 . 實(shí)例求解 ? ? ? ? ? 1,0,ijijvvp ????可 達(dá)否 則?????????????1101110111110001P定義 設(shè) D = V, E 為有向圖 . V = { v1 , v2 , …, vn }, 令 四、有向圖的可達(dá)矩陣（無(wú)限制） 稱(chēng) (pij)n?n 為 D的可達(dá)矩陣，記作 P(D)，簡(jiǎn)記為 P. 由于 ?vi?V， vi?vi，所以 P(D)主對(duì)角線(xiàn)上的元素全為 1. 由定義不難看出 , D 強(qiáng)連通當(dāng)且僅當(dāng) P(D)為全 1矩陣 . 下圖所示有向圖 D 的可達(dá)矩陣為 ? ? ? ? ? 有向圖的鄰接矩陣與可達(dá)矩陣的關(guān)系？ 作業(yè)： 習(xí)題十四： 35， 39， 45 ? ? ? ? ? 無(wú)向圖的關(guān)聯(lián)矩陣 定義 無(wú)向圖 G=V, E， |V|=n， |E|=m，令 mij 為 vi 與 ej的關(guān)聯(lián)次數(shù)，稱(chēng) (mij)n?m為 G 的關(guān)聯(lián)矩陣，記 為 M(G). （對(duì)圖無(wú)限制） ? ? ? ? ? v1 v2 v4 v3 e1 e2 e3 e4 e 5 1 1 1 0 00 1 1 1 0()1 0 0 1 20 0 0 0 0MG?????????例 1( 1 ) 2 ( 1 , 2 , . . . , )niji m j m? ???性質(zhì)： 1,( 2 ) ( ) ( 1 , 2 , . . . , )( 3 ) 2( 4 )mij ijijijm d v i nmm??????平 行 的 列 相 同完 , 作業(yè)： 習(xí)題十四： 21， 33，
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1