離散數學ppt課件(編輯修改稿)

　

【文章內容簡介】 此，若將可達性看成是圖 G＝ V， E的結點集合 V上的二元關系的話， 對有向圖來說，該可達性關系滿足什么性質？ 離散數學 34 定義 定義 在圖 G＝ V， E中，對 ?vi， vj?V，如果從 vi到 vj存在路，則稱長度最短的路為從 vi到 vj的 短程線 ,從 vi到 vj的短程線的長度稱為從 vi到 vj的 距離 ，記為 d(vi,vj)。 d(vi， vj)滿足下列性質： d(vi， vj)?0； d(vi， vi)＝ 0； d(vi， vk)+d(vk， vj)? d(vi， vj)； d(vi， vj)＝ ? (當 vi到 vj不可達 )。 此外 ， 有關距離的概念對無向圖也適用 。 離散數學 35 在 (a)中有： d(v2， v1)＝ d(v1， v2)＝ d(v3， v1)＝ d(v1， v3)＝ 在 (b)中有： d(v1， v3)＝， d(v3， v7)＝， d(v1， v7)＝。 例： 例： 離散數學 36 定義 ? 設 G＝ V， E是一個有向圖，若 G中任意兩個結點之間都是相互可達的，則稱該有向圖 G是一個 強連通圖 ； ? 設 G＝ V， E是一個有向圖，若 G中任意兩個結點之間至少單方向可達的，則稱該有向圖 G是一個 單側連通圖 ； ? 設 G＝ V， E是一個有向圖，若略去 G中所有有向邊的方向后所得到的無向圖 G1是一個無向連通圖，則稱該有向圖 G是一個 弱連通圖 。 定義 離散數學 37 例： 例： 離散數學 38 定理 定理 一個有向圖 G是強連通圖當且僅當 G中有一個回 路，它至少包含每一個結點一次。 證明 ： “ ?” G中有一個回路，它至少包含每個結點，則G中任何兩個結點間都是相互可達的，故 G為強連通圖。 “ ?” G是強連通圖，則任意兩個結點之間都是相互可達的，設 G＝ V， E， V＝ {v1,v２ ,v３ ,… ,vｎ }，則 v1到 v2可達，v2到 v3可達， v3到 v4可達， …… ， vｎ １ 到 vｎ 可達， vn到 v1可達，由此可得到一條回路 (v1， v２ ， v３ ， …… ， vｎ ， v1)，它至少包含每個結點一次。■ 離散數學 39 定義 定義 設 G＝ V， E是一個有向圖， G1＝ V1， E1是 G的導出子圖， 若 G1是弱連通圖 (單側連通圖，強連通圖 )，且沒有包含 G1的更大的子圖是弱連通圖 (單側連通圖，強連通圖 )，則稱 G1是 極大弱連通子圖 (極大單側連通子圖，極大強連通子圖 )或稱為 弱分圖 (單側分圖，強分圖 )。 離散數學 40 例： 如上圖 (a)所示，有： 例： ? 由 {v２ }、 {v６ }、 {v1,v３ ,v４ ,v５ ,v７ }所導出的子圖構成了該圖的強分圖； ? 由 {v1,v２ ,v３ ,v４ ,v５ ,v7}、 {v1,v３ ,v４ ,v5,v６ ,v７ }所導出的子圖構成了該圖的單側分圖； ? (a)圖本身就是一個弱分圖。 離散數學 41 例： 如上圖 (b)所示，有： ? 由 {v1}、 {v２ }、 {v3}、 {v4}、 {v5,v6,v７ }所導出的子圖構成了該圖的強分圖； ? 由 {v1,v２ ,v３ }、 {v1,v3,v4}、 {v５ ,v６ ,v７ }所導出的子圖構成了該圖的單側分圖； ? 由 {v1,v２ ,v３ ,v４ }、 {v５ ,v６ ,v７ }所導出的子圖構成了該圖的弱分圖。 離散數學 42 定理 ? 在有向圖 G＝ V， E，它的每一個結點必然位于且僅位于一個強分圖中； ? 在有向圖 G＝ V， E，它的每一個結點和每一條邊都至少位于一個單向分圖中； ? 在有向圖 G＝ V， E，它的每一個結點和每一條邊必然位于且僅位于一個弱分圖中。 定理 離散數學 43 證： (僅以 1)為例加以說明 ) 證： ① . 對 ?v?V，令 S是 G中所有與 v相互可達的結點集，則有 v?S，由于 v與 S中的一切結點相互可達，所以，由可達性具有傳遞性知： S中的一切結點之間是相互可達的，即 S是 G的一個強分圖，所以， v位于一個強分圖中； ② . 設 v還位于另一個強分圖 T中，則由 S中的每個結點都與 v相互可達，且 T中的每個結點也都與 v相互可達，所以，由可達性具有傳遞性知： S中的一切結點與 T中的一切結點之間是相互可達的，即由S∪T 就構成了一個更大的強連通的子圖，這就與 S、 T都是兩個強分圖矛盾，故 G的每個結點僅位于一個強分圖中。■ 離散數學 44 例： 在圖 (a)中，結點 v1， v2， v3， v4僅位于強分圖 { v1， v2， v3， v4}中，結點v5僅位于強分圖 { v5} 中，但邊 v4， v v3， v5都不位于強分圖中； 結點 v1， v2， v3， v4， v5僅位于單向分圖 { v1， v2， v3， v4， v5}，所有的邊也都僅位于單向分圖中； 結點 v1， v2， v3， v4， v5僅位于弱分圖 { v1， v2，v3， v4， v5}；所有的邊也都僅位于弱分圖中。 (b)中，結點 v2， v3和邊 v2， v3同時位于兩個單向分圖 { v1， v2，v3}和 {v2， v3， v4}中。 例： 離散數學 45 73 圖的矩陣表示 一、 鄰接矩陣 設 G＝ V,E是一個簡單圖， V＝ {v1,v2,… ,vn}， E＝{e1,e2,… ,en}，則 n階方陣 A(G)＝ (aij)n?n稱為 G的 鄰接矩陣 。其中： ??????????????EvvEvv0EvvEvv1ajijijijiij ），或（，），或（，由鄰接矩陣的定義知：其矩陣的元素是一個二值元素，所以，又稱該矩陣為 位矩陣 或 布爾矩陣 。 離散數學 46 例： 鄰接矩陣： 。，??????????????????????????????0100110001010110)G(A0011011011011010)G(A 21例： 離散數學 47 性質 設 G＝ V， E是一個簡單圖，則有： ? 如 aij＝ 1,則表示什么？ (i,j?{1,2,3,… ,n}) ? 如對 ?i,j?{1,2,3,… ,n},都有 aij＝ 0，則表示什么？ ? 如對 ?i,j?{1,2,3,… ,n},都有 aij＝ 1(i?j), aii＝ 0，則表示什么？ ? 如 G是一個無向簡單圖 ,則對任意 vi?V，都有： ?)deg( ?iv ，?????nkkinkik aa11離散數學 48 性質 如 G是一個有向簡單圖，則對任意 v