離散數(shù)學(xué)—圖論1216版ppt課件

1、第8章 圖論問題是要從這四塊陸問題是要從這四塊陸地中任何一塊開始，地中任何一塊開始，通過每一座橋正好一通過每一座橋正好一次，再回到起點(diǎn)。次，再回到起點(diǎn)。 歐拉在歐拉在17361736年解決了年解決了這個問題這個問題 。判定法則：如果通奇數(shù)座橋的地方不止兩個，那么滿足要求的路線便不存在了。如果只有兩個地方通奇數(shù)座橋，則可從其中任何一地出發(fā)找到所要求的路線。若沒有一個地 方通奇數(shù)座橋，則從任何一地出發(fā)，所求的路線都能實(shí)現(xiàn) 第8章 圖論8.1.1 圖圖第8章 圖論圖 8.1-1第8章 圖論第8章 圖論第8章 圖論第8章 圖論圖 8.13 第8章 圖論第8章 圖論第8章 圖論11deg ()deg (

2、)2nniiiim1deg()2niim 證 因?yàn)槊恳粭l邊提供兩個次數(shù),而所有各結(jié)點(diǎn)次數(shù)之和為m條邊所提供,所以上式成立。在有向圖中,上式也可寫成: 第8章 圖論121112deg()deg()deg()iinnniEOiiim 因?yàn)榇螖?shù)為偶數(shù)的各結(jié)點(diǎn)次數(shù)之和為偶數(shù)。所以前一項(xiàng)次數(shù)為偶數(shù);若n2為奇數(shù),則第二項(xiàng)為奇數(shù),兩項(xiàng)之和將為奇數(shù),但這與上式矛盾。故n2必為偶數(shù)。證畢。第8章 圖論 圖 8.15 第8章 圖論第8章 圖論 圖 8.16第8章 圖論 圖 8.17第8章 圖論(3)G1與G2的差,定義為圖G3V3,E3,記為G3=G1-G2。 其中E3=E1-E2,V3=(V1-V2)E3中邊

3、所關(guān)聯(lián)的頂點(diǎn)。 (4)G1與G2的環(huán)和,定義為圖G3V3,E3,G3=(G1G2)-(G1G2),記為G3=G1G2。第8章 圖論 圖 8.19第8章 圖論(4)若在子圖G中,對V中的任意二結(jié)點(diǎn)u、v,當(dāng)u,vE時有u,vE,則G由V唯一確定,此時稱G為由結(jié)點(diǎn)集V導(dǎo)出的子圖。第8章 圖論 圖 8.110第8章 圖論圖8.1-11第8章 圖論HGGG第8章 圖論基本路徑也一定是簡單路徑。第8章 圖論圖8.2-1第8章 圖論第8章 圖論圖中共圖中共n n個結(jié)點(diǎn)個結(jié)點(diǎn), ,故基本路徑長度不超過故基本路徑長度不超過n-1n-1。第8章 圖論第8章 圖論圖圖)。第8章 圖論圖8.22 一個無向圖或者是一

4、個連通圖,如圖8.22(a)所示,或者是由若干個連通分圖組成,如圖8.22(b)所示。第8章 圖論1()(1)2nmnn定義定義8.268.26在有向圖中在有向圖中, ,如果在任兩結(jié)點(diǎn)偶對中如果在任兩結(jié)點(diǎn)偶對中, ,至少至少從一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)是可達(dá)的從一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)是可達(dá)的, ,則稱圖則稱圖G G是單向連是單向連通的通的; ;如果在任兩結(jié)點(diǎn)偶對中如果在任兩結(jié)點(diǎn)偶對中, ,兩結(jié)點(diǎn)都互相可達(dá)兩結(jié)點(diǎn)都互相可達(dá), ,則則稱圖稱圖G G是強(qiáng)連通的是強(qiáng)連通的; ;如果它的底圖是連通的如果它的底圖是連通的, ,則稱圖則稱圖G G是是弱連通的。弱連通的。第8章 圖論第8章 圖論第8章 圖論第8章 圖

5、論( , )d u第8章 圖論,則停止,否則再重復(fù)2。第8章 圖論第8章 圖論第8章 圖論第8章 圖論第8章 圖論圖 8.27 第8章 圖論表 8.21 第8章 圖論第8章 圖論第8章 圖論圖 8.28 第8章 圖論第8章 圖論次數(shù)全是偶數(shù)。第8章 圖論第8章 圖論第8章 圖論第8章 圖論圖 8.29 第8章 圖論第8章 圖論第8章 圖論圖 8.210 第8章 圖論圖 8.210 第8章 圖論第8章 圖論圖 8.211 第8章 圖論第8章 圖論第8章 圖論圖 8.212 第8章 圖論第8章 圖論圖 8.213 第8章 圖論第8章 圖論12111,kiii12,kiii 第8章 圖論 圖 8.214 第8章 圖論第8章 圖論1(3)2n n第8章 圖論第8章 圖論第8章 圖論圖 8.215第8章 圖論第8章 圖論第8章 圖論圖 8.41 第8章