离散数学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