離散數(shù)學(xué)第6章圖的基本概念-資料下載頁
2025-01-16 20:35本頁面
【正文】 頂點 ． r p設(shè) ， ，將 標(biāo)在相應(yīng)頂點 處，表明 獲得 標(biāo)號． ??)(ril ? ?)1(1m in ???rjTv lrj1?r ?)(rilivpiv修改通過集 和未通過集 ． ?rP ? ?ir vP ?1? ? ?irr vTT ?? ?1查 ：若 ，則算法結(jié)束，否則轉(zhuǎn)第 2步． rTrT ??第 步 修改 中各頂點的 標(biāo)號： 1?r rT t ?)(rjl ? ?ijrirj wll ??? )()1( ,m i n?)(ril 是剛剛獲得 標(biāo)號頂點的 標(biāo)號 p p 令 ，轉(zhuǎn)第 步． 1?? rr r二、關(guān)鍵路徑問題 PERT圖． 最早完成時間 )( ivTE最晚完成時間 )( ivTL)( ivTS ? )( ivTL )( ivTE?緩沖時間 一、無向圖與有向圖。 基本概念。 有向圖與無向圖的定義；關(guān)聯(lián)與鄰接 (相鄰 )； 頂點的度數(shù)；零圖與平凡圖；簡單圖與多重圖； 完全圖；子圖，補圖；圖的同構(gòu)。 第六章 小結(jié)與例題 運用。 (1) 靈活運用握手定理及其推論， (2) 判斷兩個圖是否同構(gòu)， (3) 畫出滿足某些條件的子圖，補圖等。 二、通路，回路，圖的連通性。 基本概念。 通路和回路；無向圖和有向圖中頂點之間的 可達關(guān)系；短程線，距離；有向圖連通的 分類。 運用。 (1) 判斷有向圖或無向圖中通路 (回路 )的類型。 (2) 求短程線和距離。 (3) 判斷有向圖連通的類型。 三、圖的矩陣表示。 基本概念。 無向圖的關(guān)聯(lián)矩陣，有向圖的關(guān)聯(lián)矩陣和鄰接矩陣。 運用。 (1) 關(guān)聯(lián)矩陣的行和、頂點度數(shù)間的關(guān)系。 (2) 由有向圖的鄰接矩陣的 次冪求從一頂點 k到另一頂點的長度為 k 的通路數(shù)。 四、最短路徑和關(guān)鍵路徑 基本概念。 權(quán)，帶權(quán)圖，最短路徑，標(biāo)號法 PERT圖，最早完成時間，后繼元集，先驅(qū)元集 最晚完成時間，緩沖時間 運用。 （ 1）標(biāo)號法求解最短路徑問題 （ 2）求解關(guān)鍵路徑問題 例 設(shè)圖 ，其中 ,G V E? ? ?, , , ,V a b c d e?， 分別由下面給出。判斷哪些是簡單圖，哪些 E是多重圖？ ? ?( , ) , ( , ) , ( , ) , ( , )E a b b c c d a e?(1) ? ?( , ) , ( , ) , ( , ) , ( , ) , ( , )E a b b e e b a e d e?(2) ? ?( , ) , ( , ) , ( , ) , ( , )E a b b e e d c c?(3) 簡單圖 多重圖 不是 ? ?, , , , , , , , , , ,E a b b c c a a d d a d e?(4) ? ?, , , , , , , , ,E a b a b b c c d d e?(5) ? ?, , , , , , , , ,E a a a b b c e c e d?(6) 簡單圖 多重圖 不是 例 下列各序列中，可以構(gòu)成無向簡單圖的 度數(shù)序列的有哪些？ (1) ( 2 , 2 , 2 , 2 , 2) 可以 (2) (1 , 1 , 2 , 2 , 3 ) 不可以 (3) (1 , 1 , 2 , 2 , 2) 可以 (4) ( 0 , 1 , 3 , 3 , 3 ) 不可以 例 (1) 畫出完全圖 的所有非同構(gòu)的生成子圖。 4K解： (2) 的生成子圖有幾個是連通圖？ 4K解： 有 6個： 例 下圖所示的六個圖中，強連通，單向連通， 弱連通的分別有哪些？ 強連通 單向連通 弱連通 單向連通 強連通 強連通 例 已知圖 的鄰接矩陣， D1 0 1 11 0 0 0()1 0 0 11 1 0 0AD?????????????23 1 1 21 0 1 1()2 1 1 12 0 1 1AD?????????????37 2 3 43 1 1 2()5 1 2 34 1 2 3AD?????????????， 3( ) _ _ _ _ _dv? ?(1) 1( ) __ __ _dv? ?2( ) ___ ___ ___ ___ ___ ___ _dv ?2 422( ) ( ) 2d v d v????(2) 從 到 長度為 2的通路數(shù)。 1v 4v解： 因 ，所以從 到 長度為 2的通路數(shù)為 2。 ( 2 )14 2a ? 1v 4v(3) 從 到 長度為 3的通路數(shù)。 3v 1v解： 因 ，所以從 到 長度為 3的通路數(shù)為 5。 ( 3 )31 5a ? 3v 1v(4) 過 長度為 3的回路數(shù)。 4v解： 因 ，所以過 長度為 3的回路數(shù)為 3。 ( 3 )44 3a ? 4v例 設(shè) 為 9個頂點的無向圖，每個頂點的度數(shù) G不是 5就是 6。證明 中至少有 5個 6度頂點或者至 G少有 6個 5度頂點。 證明： 由握手定理的推論知， 中 5度頂點的個數(shù) G只能是 0， 2， 4， 6， 8這五種情形。 此時 6度頂點的個數(shù)分別為 9， 7， 5， 3， 1這五種 情形，不論何種情形，均滿足結(jié)論要求。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1