離散數學0601PPT學習教案

1、會計學1離散數學離散數學06012第1頁/共34頁3第2頁/共34頁4定義定義4.2 設設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) 不可能不可能. . 有奇數個奇數有奇數個奇數. .第11頁/共34頁13例例2 已知圖已知圖G有有10條邊條邊, 4個個3度頂點度頂點, 其余頂點的度數均小其余頂點的度數均小于等于于等于2, 問問G至少有多少個頂點至少有多少個頂點? 解解 設設G有有n個頂點個頂點. 由握手定理由握手定理, 4 3+2 (n-4) 2 10解得解得 n 8例例3 已知已知5階有向圖的度數列和出度列階有向圖的度數列和出度列分別為

3、分別為3,3,2,3,3和和 1,2,1,2,1, 求它的入度列求它的入度列解解 2,1,1,1,2第12頁/共34頁14證證 用反證法用反證法. 假設存在這樣的多面體假設存在這樣的多面體, 作無向圖作無向圖G=,其中其中 V=v | v為多面體的面為多面體的面, E=(u,v) | u,v V u與與v有公共的棱有公共的棱 u v.根據假設根據假設, |V|為奇數且為奇數且 v V, d(v)為奇數為奇數. 這與握手定理這與握手定理的推論矛盾的推論矛盾.第13頁/共34頁15證證 討論所有可能的情況討論所有可能的情況. 設有設有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度頂點度頂點方法二方法二 假設假設b9-5=4. 由握手定理的推論由握手定理的推論, a 6第14頁/共34頁16第15頁/共34頁17e5和和e6 是平行邊是平行邊重數為重數為2不是簡單圖不是簡單圖e2和和e3 是平行邊是平行邊,重數為重數為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 的的閉閉鄰鄰域域的的鄰鄰域域)(|)(關關聯聯與與veGEeevI )()()()()()(,)(|)()(,)(|)(vvNvNvvvvNvvuDEvuDVuuvvvuDEuvDVuuvvDDDDDDD 的閉鄰域的閉鄰域的鄰域的鄰域的先驅元集的先驅元集的后繼元集的后繼元集8. 8. 鄰域與關聯集鄰域與關聯集 v v V V( (G G) () (G G為無向圖為無向圖) ) v v 的關聯集的關聯集 v v V V( (D D) () (D D為有向圖為有向圖) )相關概念相關概念第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 的無向簡單圖的無向簡單圖簡單性質：邊數（由握手定理得）簡單性質：邊數（由握手定理得）K Kn n是是 n n 1 1正則圖，正則圖，彼得松圖（見書上圖彼得松圖（見書上圖14