圖論基本概念ppt課件-閱讀頁(yè)
2025-05-18 22:00本頁(yè)面
【正文】 10020102100300010101100101020001432AAAA(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í)例求解 44 ????否則可達(dá),1,0 jiijvvp?????????????1101110111110001P定義 設(shè) D=V,E為有向圖 . V={v1, v2, …, vn}, 令 有向圖的可達(dá)矩陣（無(wú)限制） 稱 (pij)n?n 為 D的可達(dá)矩陣，記作 P(D)，簡(jiǎn)記為 P. 由于 ?vi?V， vi?vi，所以 P(D)主對(duì)角線上的元素全為 1. 由定義不難看出 , D 強(qiáng)連通當(dāng)且僅當(dāng) P(D)為全 1矩陣 . 下圖所示有向圖 D 的可達(dá)矩陣為 45 第十四章 習(xí)題課 主要內(nèi)容 ? 無(wú)向圖、有向圖、關(guān)聯(lián)與相鄰、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖；握手定理與推論；圖的同構(gòu) ? 通路與回路及其分類 ? 無(wú)向圖的連通性與連通度 ? 有向圖的連通性及其分類 ? 圖的矩陣表示 46 基本要求 ? 深刻理解握手定理及推論的內(nèi)容并能靈活地應(yīng)用它們 ? 深刻理解圖同構(gòu)、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖、二部圖的概念以及它們的性質(zhì)及相互之間的關(guān)系 ? 記住通路與回路的定義、分類及表示法 ? 深刻理解與無(wú)向圖連通性、連通度有關(guān)的諸多概念 ? 會(huì)判別有向圖連通性的類型 ? 熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會(huì)求可達(dá)矩陣 47 1． 9階無(wú)向圖 G中，每個(gè)頂點(diǎn)的度數(shù)不是 5就是 6. 證明 G中至少有 5個(gè) 6度頂點(diǎn)或至少有 6個(gè) 5度頂點(diǎn) . 練習(xí) 1 證 關(guān)鍵是利用握手定理的推論 . 方法一：窮舉法 設(shè) G中有 x個(gè) 5度頂點(diǎn)，則必有 (9?x)個(gè) 6度頂點(diǎn)，由握手定理推論可知， (x,9?x)只有 5種可能： (0,9), (2,7), (4,5), (6,3), (8,1）它們都滿足要求 . 方法二：反證法 否則，由握手定理推論可知，“ G至多有 4個(gè) 5度頂點(diǎn)并且至多有 4個(gè) 6度頂點(diǎn)”，這與 G是 9 階圖矛盾 . 48 2．?dāng)?shù)組 2, 2, 2, 2, 3, 3能簡(jiǎn)單圖化嗎？若能，畫出盡可能多的非同構(gòu)的圖來(lái) . 練習(xí) 2 只要能畫出 6 階無(wú)向簡(jiǎn)單圖，就說(shuō)明它可簡(jiǎn)單圖化 . 下圖的 4個(gè)圖都以此數(shù)列為度數(shù)列，請(qǐng)證明它們彼此不同構(gòu)，都是 K6的子圖 . 49 用擴(kuò)大路徑法證明 . 情況一： ?? ? ?+. 證明 D中存在長(zhǎng)度 ? ??+1的圈 . 設(shè) ? = v0v1… vl為極大路徑，則 l ? ??(為什么 ?).由于 d?(v0)? ??，所以在 ? 上存在 PLAY ??iii vvv ,..., 21010 . . .. . .. . . 21 vvvvvv iii ??鄰接到 v0，于是 情況二： ?+ ? ??，只需注意 d+(vl) ? ? + . 3．設(shè) D=V,E為有向簡(jiǎn)單圖，已知 ?(D) ? 2， ?+(D)0，??(D)0，證明 D中存在長(zhǎng)度 ? max{?+,??}+1的圈 . 為 D中長(zhǎng)度 ? ??+1的有向圈 練習(xí) 3 50 (1) D中有幾種非同構(gòu)的圈？ (2) D中有幾種非圈非同構(gòu)的簡(jiǎn)單回路？ (3) D是哪類連通圖 ? (4) D中 v1到 v4長(zhǎng)度為 1,2,3,4的通路各多少 條？其中幾條是非初級(jí)的簡(jiǎn)單通路？ (5) D中 v1到 v1長(zhǎng)度為 1,2,3,4的回路各多少 條？討論它們的類型 . (6) D中長(zhǎng)度為 4的通路（不含回路）有多少條？ (7) D中長(zhǎng)度為 4的回路有多少條？ (8) D中長(zhǎng)度 ?4的通路有多少條？其中有幾條是回路？ (9) 寫出 D的可達(dá)矩陣 . 4．有向圖 D如圖所示， 回答下列諸問(wèn)： 練習(xí) 4 51 解答 (1) D中有 3種非同構(gòu)的圈，長(zhǎng)度分別為 1,2,3，請(qǐng)畫出它們的圖形 . (2) D中有 3種非圈的非同構(gòu)的簡(jiǎn)單回路，它們的長(zhǎng)度分別為 4,5,6. 請(qǐng)畫出它們的圖形來(lái) . (3) D是強(qiáng)連通的（為什么？） 為解 (4)— (8)，只需先求 D的鄰接矩陣的前 4次冪 . ????????????????????????????????????????????????????1222234412222465012112220121222310010121100102210100100101000021432AAAA52 (4) v1到 v4長(zhǎng)度為 1,2,3,4的通路數(shù)分別為 0,0,2,2. 其中只有長(zhǎng)度為 4的兩條是非初級(jí)的簡(jiǎn)單通路（定義意義下），見(jiàn)下圖所示 . 解答 53 解答 (5) v1到 v1長(zhǎng)度為 1,2,3,4的回路數(shù)分別為 1,1,3,5. 其中長(zhǎng)度為 1的是初級(jí)的 (環(huán) )；長(zhǎng)度為 2的是復(fù)雜的；長(zhǎng)度為 3的中有 1條是復(fù)雜的， 2條是初級(jí)的；長(zhǎng)度為 4的有 1條是復(fù)雜的，有 4條是非初級(jí)的簡(jiǎn)單回路 . 請(qǐng)?jiān)趫D中行遍以上各回路 . (6) 長(zhǎng)度為 4的通路 (不含回路 )為 33條 . (7) 長(zhǎng)度為 4的回路為 11條 . (8) 長(zhǎng)度 ?4的通路 88條，其中 22條為回路 . (9) 4?4的全 1矩陣 .
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1