離散數(shù)學(xué)0601PPT學(xué)習(xí)教案_第1頁(yè)
離散數(shù)學(xué)0601PPT學(xué)習(xí)教案_第2頁(yè)
離散數(shù)學(xué)0601PPT學(xué)習(xí)教案_第3頁(yè)
離散數(shù)學(xué)0601PPT學(xué)習(xí)教案_第4頁(yè)
離散數(shù)學(xué)0601PPT學(xué)習(xí)教案_第5頁(yè)
已閱讀5頁(yè),還剩29頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、會(huì)計(jì)學(xué)1離散數(shù)學(xué)離散數(shù)學(xué)06012第1頁(yè)/共34頁(yè)3第2頁(yè)/共34頁(yè)4定義定義4.2 設(shè)設(shè)A, B為集合,為集合,A與與B 的的笛卡兒積笛卡兒積記作記作A B, A B = | x A y B .例例2 A=0, 1, B=a, b, c A B=, B A = ? A = , B = P(A) = , P(A) A = ? P(A) B = ? , , 第3頁(yè)/共34頁(yè)5e1e2e3e4e5e6e7v5v1v2v3v4第4頁(yè)/共34頁(yè)6e1e2e3e4e5e6e7dabc第5頁(yè)/共34頁(yè)7第6頁(yè)/共34頁(yè)8e1e2e3e4e5e6e7v5v1v2v3v4第7頁(yè)/共34頁(yè)9e1e2e3e4e5

2、e6e7dabc第8頁(yè)/共34頁(yè)10第9頁(yè)/共34頁(yè)11e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc第10頁(yè)/共34頁(yè)12(2) 能能解解 (1) 不可能不可能. . 有奇數(shù)個(gè)奇數(shù)有奇數(shù)個(gè)奇數(shù). .第11頁(yè)/共34頁(yè)13例例2 已知圖已知圖G有有10條邊條邊, 4個(gè)個(gè)3度頂點(diǎn)度頂點(diǎn), 其余頂點(diǎn)的度數(shù)均小其余頂點(diǎn)的度數(shù)均小于等于于等于2, 問(wèn)問(wèn)G至少有多少個(gè)頂點(diǎn)至少有多少個(gè)頂點(diǎn)? 解解 設(shè)設(shè)G有有n個(gè)頂點(diǎn)個(gè)頂點(diǎn). 由握手定理由握手定理, 4 3+2 (n-4) 2 10解得解得 n 8例例3 已知已知5階有向圖的度數(shù)列和出度列階有向圖的度數(shù)列和出度列分別為

3、分別為3,3,2,3,3和和 1,2,1,2,1, 求它的入度列求它的入度列解解 2,1,1,1,2第12頁(yè)/共34頁(yè)14證證 用反證法用反證法. 假設(shè)存在這樣的多面體假設(shè)存在這樣的多面體, 作無(wú)向圖作無(wú)向圖G=,其中其中 V=v | v為多面體的面為多面體的面, E=(u,v) | u,v V u與與v有公共的棱有公共的棱 u v.根據(jù)假設(shè)根據(jù)假設(shè), |V|為奇數(shù)且為奇數(shù)且 v V, d(v)為奇數(shù)為奇數(shù). 這與握手定理這與握手定理的推論矛盾的推論矛盾.第13頁(yè)/共34頁(yè)15證證 討論所有可能的情況討論所有可能的情況. 設(shè)有設(shè)有a個(gè)個(gè)5度頂點(diǎn)和度頂點(diǎn)和b個(gè)個(gè)6度頂點(diǎn)度頂點(diǎn)(1)a=0, b=

4、9;(2)a=2, b=7;(3)a=4, b=5;(4)a=6, b=3;(5)a=8, b=1(1)(3) 至少至少5個(gè)個(gè)6度頂點(diǎn)度頂點(diǎn), (4)和和(5) 至少至少6個(gè)個(gè)5度頂點(diǎn)度頂點(diǎn)方法二方法二 假設(shè)假設(shè)b9-5=4. 由握手定理的推論由握手定理的推論, a 6第14頁(yè)/共34頁(yè)16第15頁(yè)/共34頁(yè)17e5和和e6 是平行邊是平行邊重?cái)?shù)為重?cái)?shù)為2不是簡(jiǎn)單圖不是簡(jiǎn)單圖e2和和e3 是平行邊是平行邊,重?cái)?shù)為重?cái)?shù)為2e6和和e7 不是平行邊不是平行邊不是簡(jiǎn)單圖不是簡(jiǎn)單圖e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc第16頁(yè)/共34頁(yè)18第17頁(yè)/共34

5、頁(yè)19K3K53階有向完全階有向完全圖圖2正則圖正則圖4正則圖正則圖 3正則圖正則圖彼得松圖彼得松圖第18頁(yè)/共34頁(yè)20第19頁(yè)/共34頁(yè)210100011011000001010011110100111101第20頁(yè)/共34頁(yè)22aabbccdddeee f f f e1 e1 e2 e3 e3 e4 e5 e5 e5 e6 e6 e7 e7 e7(1)(2)(3)第21頁(yè)/共34頁(yè)23第22頁(yè)/共34頁(yè)24aabbccdddeee f f f e1 e1 e2 e3 e3 e4 e5 e5 e5 e6 e6 e7 e7 e7(1)(2)(3)第23頁(yè)/共34頁(yè)25G第24頁(yè)/共34頁(yè)26

6、第25頁(yè)/共34頁(yè)27123123456123456123456第26頁(yè)/共34頁(yè)281,1,1,31,1,2,20,2,2,2第27頁(yè)/共34頁(yè)29第28頁(yè)/共34頁(yè)30)()()(),()(|)(vvNvNvvuGEvuGVuuvNv 的的閉閉鄰鄰域域的的鄰鄰域域)(|)(關(guān)關(guān)聯(lián)聯(lián)與與veGEeevI )()()()()()(,)(|)()(,)(|)(vvNvNvvvvNvvuDEvuDVuuvvvuDEuvDVuuvvDDDDDDD 的閉鄰域的閉鄰域的鄰域的鄰域的先驅(qū)元集的先驅(qū)元集的后繼元集的后繼元集8. 8. 鄰域與關(guān)聯(lián)集鄰域與關(guān)聯(lián)集 v v V V( (G G) () (G G為無(wú)向圖為無(wú)向圖) ) v v 的關(guān)聯(lián)集的關(guān)聯(lián)集 v v V V( (D D) () (D D為有向圖為有向圖) )相關(guān)概念相關(guān)概念第29頁(yè)/共34頁(yè)311,2)1( nnnm 1),1(2),1( nnnnm 1,2)1( nnnm 第30頁(yè)/共34頁(yè)32 (1) (2) (3)定義定義14.714.7 n n 階階k k正則圖正則圖 = = = =k k 的無(wú)向簡(jiǎn)單圖的無(wú)向簡(jiǎn)單圖簡(jiǎn)單性質(zhì):邊數(shù)(由握手定理得)簡(jiǎn)單性質(zhì):邊數(shù)(由握手定理得)K Kn n是是 n n 1 1正則圖,正則圖,彼得松圖(見(jiàn)書(shū)上圖彼得松圖(見(jiàn)書(shū)上圖14

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論