離散數(shù)學chppt課件-在線瀏覽
2025-06-21 08:14本頁面
【正文】 定理及推論的內(nèi)容并能靈活地應用它們 ? 深刻理解圖同構、簡單圖、完全圖、正則圖、子圖、補圖、二部圖的概念以及它們的性質及相互之間的關系 ? 記住通路與回路的定義、分類及表示法 ? 深刻理解與無向圖連通性、連通度有關的諸多概念 ? 會判別有向圖連通性的類型 ? 熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會求可達矩陣 45 1． 9階無向圖 G中，每個頂點的度數(shù)不是 5就是 6. 證明 G中至少有 5個 6度頂點或至少有 6個 5度頂點 . 練習 1 證 關鍵是利用握手定理的推論 . 方法一：窮舉法 設 G中有 x個 5度頂點，則必有 (9?x)個 6度頂點，由握手定理推論可知， (x,9?x)只有 5種可能： (0,9), (2,7), (4,5), (6,3), (8,1）它們都滿足要求 . 方法二：反證法 否則，由握手定理推論可知，“ G至多有 4個 5度頂點并且至多有 4個 6度頂點”，這與 G是 9 階圖矛盾 . 46 2．數(shù)組 2, 2, 2, 2, 3, 3能簡單圖化嗎？若能，畫出盡可能多的非同構的圖來 . 練習 2 只要能畫出 6 階無向簡單圖，就說明它可簡單圖化 . 下圖的 4個圖都以此數(shù)列為度數(shù)列，請證明它們彼此不同構，都是 K6的子圖 . 47 用擴大路徑法證明 . 情況一： ?? ? ?+. 證明 D中存在長度 ? ??+1的圈 . 設 ? = v0v1… vl為極大路徑，則 l ? ??(為什么 ?).由于 d?(v0)? ??，所以在 ? 上存在 PLAY ??iii vvv ,..., 21010 . . .. . .. . . 21 vvvvvv iii ??鄰接到 v0，于是 情況二： ?+ ? ??，只需注意 d+(vl) ? ? + . 3．設 D=V,E為有向簡單圖，已知 ?(D) ? 2， ?+(D)0，??(D)0，證明 D中存在長度 ? max{?+,??}+1的圈 . 為 D中長度 ? ??+1的有向圈 練習 3 48 (1) D中有幾種非同構的圈？ (2) D中有幾種非圈非同構的簡單回路？ (3) D是哪類連通圖 ? (4) D中 v1到 v4長度為 1,2,3,4的通路各多少 條？其中幾條是非初級的簡單通路？ (5) D中 v1到 v1長度為 1,2,3,4的回路各多少 條？討論它們的類型 . (6) D中長度為 4的通路（不含回路）有多少條？ (7) D中長度為 4的回路有多少條？ (8) D中長度 ?4的通路有多少條？其中有幾條是回路？ (9) 寫出 D的可達矩陣 . 4．有向圖 D如圖所示， 回答下列諸問： 練習 4 49 解答 (1) D中有 3種非同構的圈，長度分別為 1,2,3，請畫出它們的圖形 . (2) D中有 3種非圈的非同構的簡單回路，它們的長度分別為 4,5,6. 請畫出它們的圖形來 . (3) D是強連通的（為什么？） 為解 (4)— (8)，只需先求 D的鄰接矩陣的前 4次冪 . ????????????????????????????????????????????????????1222234412222465012112220121222310010121100102210100100101000021432AAAA50 (4) v1到 v4長度為 1,2,3,4的通路數(shù)分別為 0,0,2,2. 其中只有長度為 4的兩條是非初級的簡單通路（定義意義下），見下圖所示 . 解答 51 解答 (5) v1到 v1長度為 1,2,3,4的回路數(shù)分別為 1,1,3,5. 其中長度為 1的是初級的 (環(huán) )；長度為 2的是復雜的；長度為 3的中有 1條是復雜的， 2條是初級的；長度為 4的有 1條是復雜的，有 4條是非初級的簡單回路 . 請在圖中行遍以上各回路 . (6) 長度為 4的通路 (不含回路 )為 33條 . (7) 長度為 4的回路為 11條 . (8) 長度 ?4的通路 88條，其中 22條為回路 . (9) 4?4的全 1矩陣 . 。1 第五部分 圖論 本部分主要內(nèi)容 ? 圖的基本概念 ? 歐拉圖、哈密頓圖 ? 樹 ? 平面圖 ? 支配集、覆蓋集、獨立集、匹配與著色 2 第十四章 圖的基本概念 主要內(nèi)容 ? 圖 ? 通路與回路 ? 圖的連通性 ? 圖的矩陣表示 ? 圖的運算 預備知識 ? 多重集合 —— 元素可以重復出現(xiàn)的集合 ? 無序集 —— A?B={(x,y) | x?A?y?B} 3 圖 定義 無向圖 G = V,E, 其中 (1) V ? ?為頂點集，元素稱為 頂點 (2) E為 V?V 的多重集，其元素稱為無向邊，簡稱 邊 實例 設 V = {v1, v2, …, v5}, E = {(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)} 則 G = V,E為一無向圖 4 有向圖 定義 有向圖 D=V,E, 只需注意 E是 V?V 的多重子集 圖 2表示的是一個有向圖，試寫出它的 V 和 E 注意：圖的數(shù)學定義與圖形表示，在同構（待敘）的意義下
教學課件相關推薦
鄂ICP備17016276號-1