離散數(shù)學(xué)0601PPT學(xué)習(xí)教案

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