圖論基本概念ppt課件-在線瀏覽
2025-06-20 22:00本頁(yè)面
【正文】 與通路外的頂點(diǎn)相鄰為止 . 設(shè)最后得到的路徑為 ?l+k（長(zhǎng)度 為 l 的路徑擴(kuò)大成了長(zhǎng)度為 l+k 的路徑），稱 ?l+k為“極大路 徑”，稱使用此種方法證明問題的方法為“ 擴(kuò)大路徑法 ” . 有向圖中類似討論，只需注意，在每步擴(kuò)大中保證有向邊方 向的一致性 . 34 實(shí)例 由某條路徑擴(kuò)大出的極大路徑不惟一，極大路徑不一定是 圖中最長(zhǎng)的路徑 上圖中， (1)中實(shí)線邊所示的長(zhǎng)為 2的初始路徑 ?， (2),(3),(4) 中實(shí)線邊所示的都是它擴(kuò)展成的極大路徑 . 還能找到另外的極大路徑嗎？ (1) (2) (4) (3) 35 擴(kuò)大路徑法的應(yīng)用 例 4 設(shè) G 為 n（ n?3）階無(wú)向簡(jiǎn)單圖， ? ? 2，證明 G 中存在 長(zhǎng)度 ? ?+1 的圈 . 證 設(shè) ? = v0v1… vl 是由初始路徑 ?0 用擴(kuò)大路徑法的得到的極 大路徑，則 l ? ? （為什么？） . 因?yàn)?v0 不與 ? 外頂點(diǎn)相鄰，又 d(v0) ? ?，因而在 ?上除 v1 外，至少還存在 ??1個(gè)頂點(diǎn)與 v0 相鄰 . 設(shè) vx 是離 v0 最遠(yuǎn)的頂 點(diǎn)，于是 v0v1… vxv0 為 G 中長(zhǎng)度 ? ?+1 的圈 . 36 二部圖 定義 設(shè) G=V,E為一個(gè)無(wú)向圖，若能將 V分成 V1和 V2 (V1?V2=V， V1?V2=?)，使得 G 中的每條邊的兩個(gè)端點(diǎn)都是 一個(gè)屬于 V1，另一個(gè)屬于 V2，則稱 G 為 二部圖 ( 或稱 二分 圖 、 偶圖 等 )，稱 V1和 V2為 互補(bǔ)頂點(diǎn)子集 ，常將二部圖 G 記為 V1,V2,E. 又若 G是簡(jiǎn)單二部圖， V1中每個(gè)頂點(diǎn)均與 V2中所有的頂點(diǎn)相 鄰，則稱 G為 完全二部圖 ，記為 Kr,s，其中 r=|V1|， s=|V2|. 注意， n 階零圖為二部圖 . 37 二部圖的判別法 定理 無(wú)向圖 G=V,E是 二部圖 當(dāng)且僅當(dāng) G中無(wú)奇圈 由定理 9中各圖都是二部圖，哪些是完全二部 圖？哪些圖是同構(gòu)的？ 38 圖的矩陣表示 無(wú)向圖的關(guān)聯(lián)矩陣（對(duì)圖無(wú)限制） 定義 無(wú)向圖 G=V,E， |V|=n， |E|=m，令 mij為 vi 與 ej 的關(guān)聯(lián)次數(shù)，稱 (mij)n?m為 G 的 關(guān)聯(lián)矩陣 ，記為 M(G). 性質(zhì) 平行邊的列相同)4(2)3(), .. . ,2,1()()2(), .. . ,2,1(2)1(,11mmnivdmmjmjiijimj ijni ij??????????39 ?? ???????????? ????jiijmjmj iijiijni ijmnivdmvdmmjm,1 110)3(, . . . ,2,1),()1(),()1()2(), . . . ,2,1(0)1(???????的終點(diǎn)為，不關(guān)聯(lián)與，的始點(diǎn)為jijijiijevevevm10,1有向圖的關(guān)聯(lián)矩陣（無(wú)環(huán)有向圖） 定義 有向圖 D=V,E，令 則稱 (mij)n?m為 D的 關(guān)聯(lián)矩陣 ，記為 M(D). (4) 平行邊對(duì)應(yīng)的列相同 性質(zhì) 有向圖的關(guān)聯(lián)矩陣 40 有向圖的鄰接矩陣（無(wú)限制） 定義 設(shè)有向圖 D=V,E, V={v1, v2, …, vn}, E={e1, e2, …, em}, 令為頂點(diǎn) vi 鄰接到頂點(diǎn) vj 邊的條數(shù)，稱為 D的 鄰接矩 陣 ，記作 A(D)，或簡(jiǎn)記為 A. 性質(zhì) 的回路數(shù)中長(zhǎng)度為的通路數(shù)中長(zhǎng)度為1)4(1)3(, . . . ,2,1),()2(, . . . ,2,1),()1(1)1(,)1(1)1(1)1(DaDmanjvdanivdaniiijiijjniijinjij????????????????????41 推論 設(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ù) . 42 例 5 有向圖 D如圖所示，求 A, A2, A3, A4，并回答諸問題： (1) D 中長(zhǎng)度為 1, 2, 3, 4的通路各有多少條？其中回路分別為多少條？ (2) D 中長(zhǎng)度小于或等于 4的通路為多少條？其中有多少條回路？ 實(shí)例 43 ????????????????????????????????????????????????????10040104100500010103100301040001
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1