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