離散數(shù)學0601PPT學習教案

1、會計學1離散數(shù)學離散數(shù)學06012第1頁/共34頁3第2頁/共34頁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頁/共34頁5e1e2e3e4e5e6e7v5v1v2v3v4第4頁/共34頁6e1e2e3e4e5e6e7dabc第5頁/共34頁7第6頁/共34頁8e1e2e3e4e5e6e7v5v1v2v3v4第7頁/共34頁9e1e2e3e4e5

2、e6e7dabc第8頁/共34頁10第9頁/共34頁11e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc第10頁/共34頁12(2) 能能解解 (1) 不可能不可能. . 有奇數(shù)個奇數(shù)有奇數(shù)個奇數(shù). .第11頁/共34頁13例例2 已知圖已知圖G有有10條邊條邊, 4個個3度頂點度頂點, 其余頂點的度數(shù)均小其余頂點的度數(shù)均小于等于于等于2, 問問G至少有多少個頂點至少有多少個頂點? 解解 設(shè)設(shè)G有有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頁/共34頁14證證 用反證法用反證法. 假設(shè)存在這樣的多面體假設(shè)存在這樣的多面體, 作無向圖作無向圖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頁/共34頁15證證 討論所有可能的情況討論所有可能的情況. 設(shè)有設(shè)有a個個5度頂點和度頂點和b個個6度頂點度頂點(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個個6度頂點度頂點, (4)和和(5) 至少至少6個個5度頂點度頂點方法二方法二 假設(shè)假設(shè)b9-5=4. 由握手定理的推論由握手定理的推論, a 6第14頁/共34頁16第15頁/共34頁17e5和和e6 是平行邊是平行邊重數(shù)為重數(shù)為2不是簡單圖不是簡單圖e2和和e3 是平行邊是平行邊,重數(shù)為重數(shù)為2e6和和e7 不是平行邊不是平行邊不是簡單圖不是簡單圖e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc第16頁/共34頁18第17頁/共34

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

6、第25頁/共34頁27123123456123456123456第26頁/共34頁281,1,1,31,1,2,20,2,2,2第27頁/共34頁29第28頁/共34頁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為無向圖為無向圖) ) v v 的關(guān)聯(lián)集的關(guān)聯(lián)集 v v V V( (D D) () (D D為有向圖為有向圖) )相關(guān)概念相關(guān)概念第29頁/共34頁311,2)1( nnnm 1),1(2),1( nnnnm 1,2)1( nnnm 第30頁/共34頁32 (1) (2) (3)定義定義14.714.7 n n 階階k k正則圖正則圖 = = = =k k 的無向簡單圖的無向簡單圖簡單性質(zhì)：邊數(shù)（由握手定理得）簡單性質(zhì)：邊數(shù)（由握手定理得）K Kn n是是 n n 1 1正則圖，正則圖，彼得松圖（見書上圖彼得松圖（見書上圖14