《離散數(shù)學(xué)ch》ppt課件-全文預(yù)覽
【正文】 ? 深刻理解握手定理及推論的內(nèi)容并能靈活地應(yīng)用它們 ? 深刻理解圖同構(gòu)、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖、二部圖的概念以及它們的性質(zhì)及相互之間的關(guān)系 ? 記住通路與回路的定義、分類及表示法 ? 深刻理解與無向圖連通性、連通度有關(guān)的諸多概念 ? 會(huì)判別有向圖連通性的類型 ? 熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會(huì)求可達(dá)矩陣 45 1． 9階無向圖 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 階圖矛盾 . 46 2．?dāng)?shù)組 2, 2, 2, 2, 3, 3能簡(jiǎn)單圖化嗎？若能，畫出盡可能多的非同構(gòu)的圖來 . 練習(xí) 2 只要能畫出 6 階無向簡(jiǎn)單圖，就說明它可簡(jiǎn)單圖化 . 下圖的 4個(gè)圖都以此數(shù)列為度數(shù)列，請(qǐng)證明它們彼此不同構(gòu)，都是 K6的子圖 . 47 用擴(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 48 (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如圖所示， 回答下列諸問： 練習(xí) 4 49 解答 (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)畫出它們的圖形來 . (3) D是強(qiáng)連通的（為什么？） 為解 (4)— (8)，只需先求 D的鄰接矩陣的前 4次冪 . ????????????????????????????????????????????????????1222234412222465012112220121222310010121100102210100100101000021432AAAA50 (4) v1到 v4長(zhǎng)度為 1,2,3,4的通路數(shù)分別為 0,0,2,2. 其中只有長(zhǎng)度為 4的兩條是非初級(jí)的簡(jiǎn)單通路（定義意義下），見下圖所示 . 解答 51 解答 (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矩陣 . 。1 第五部分 圖論 本部分主要內(nèi)容 ? 圖的基本概念 ? 歐拉圖、哈密頓圖 ? 樹 ? 平面圖 ? 支配集、覆蓋集、獨(dú)立集、匹配與著色 2 第十四章 圖的基本概念 主要內(nèi)容 ? 圖 ? 通路與回路 ? 圖的連通性 ? 圖的矩陣表示 ? 圖的運(yùn)算 預(yù)備知識(shí) ? 多重集合 —— 元素可以重復(fù)出現(xiàn)的集合 ? 無序集 —— A?B={(x,y) | x?A?y?B} 3 圖 定義 無向圖 G = V,E, 其中 (1) V ? ?為頂點(diǎn)集，元素稱為 頂點(diǎn) (2) E為 V?V 的多重集，其元素稱為無向邊，簡(jiǎn)稱 邊 實(shí)例 設(shè) 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表示的是一個(gè)有向圖，試寫出它的 V 和 E 注意：圖的數(shù)學(xué)定義與圖形表示，在同構(gòu)（
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1