第九章 色数

第5节 古典概型 最新考纲核心素养 考情聚焦 1.理解古典概型及其概率计算公式．2.会计算一些随机事件所包含的基本事件数及事件发生的概率．3.了解随机数的意义，能运用模拟方法估计概率 1.简单的古典概型，增强数学建模、逻辑推理数学运算的素养． 2.古典概型的交汇问题，提升增强数学建模、逻辑推理数学运算的素养 预计2020年的高考有以下形式： 古典概型将以概率为基础，常与排列组合相结合，以统计为实际背景考查1．基本事件的特点(1)任何两个基本事件是互斥的；(2)任何事件(除不可能事件)都可以表示成基本事件的和．2．古典概型的定义、特点及计算公式(1)定义：具有以下两个特点的概率模型称为古典概率模型，简称为古典概型．(2)特点：①试验中所有可能出现的基本事件只有有限个；②每个基本事件出现的可能性相等．计算公式：P (A )＝A包含的基本事件的个数基本事件的总数.[思考辨析]判断下列说法是否正确，正确的在它后面的括号里打“√”，错误的打“×”．(1)“在适宜条件下，种下一粒种子观察它是否发芽”属于古典概型，其基本事件是“发芽与不发芽”( )(2)掷一枚硬币两次，出现“两个正面”“一正一反”“两个反面”这三个结果是等可能事件( )(3)分别从3名男同学、4名女同学中各选一名作代表，那么每个同学当选的可能性相同．( )(4)利用古典概型的概率公式可求“在边长为2的正方形内任取一点，这点到正方形中心距离小于或等于1”的概率．( )答案：(1)× (2)× (3)× (4)×[小题查验]1．(2019·黄冈质检)一部3卷文集随机地排在书架上，卷号自左向右或自右向左恰为1,2,3的概率是( )A.16B.13C.12D.23解析：B [3卷文集随机排列，共有6种结果，卷号自左向右或自右向左恰为1,2,3的只有2种结果，所以卷号自左向右或自右向左恰为1,2,3的概率是26＝13.] 2．(2018·全国Ⅱ卷)我国数学家陈景润在哥德巴赫猜想的研究中取得了世界领先的成果．哥德巴赫猜想是“每个大于2的偶数可以表示为两个素数的和”，如30＝7＋23.在不超过30的素数中，随机选取两个不同的数，其和等于30的概率是( )A.112B.114C.115D.118解析：C [不超过30的素数有2,3,5,7,11,13,17,19,23,29，共10个，随机选取两个数共有C 210种，其和等于30的数对有(7,23)，(11,19)，(13,17)，3组，故所求概率为p ＝3C 210＝345＝115.] 3．甲在微信群中发布6元“拼手气”红包一个，被乙、丙、丁三人抢完，若三人均领到整数元，且每人至少领到1元，则乙获得“手气最佳”(即乙领取的钱数不少于其他任何人)的概率是( )A.34B.13C.310D.25解析：D [用(x ，y ，z )表示乙、丙、丁抢到的红包分别为x 元、y 元、z 元．乙、丙、丁三人抢完6元钱的所有不同的可能结果有10种，分别为(1,1,4)，(1,4,1)，(4,1,1)，(1,2,3)，(1,3,2)，(2,1,3)，(2,3,1)，(3,1,2)，(3,2,1)，(2,2,2)．乙获得“手气最佳”的所有不同的可能结果有4种，分别为(4,1,1)，(3,1,2)，(3,2,1)，(2,2,2)．根据古典概型的概率计算公式，得乙获得“手气最佳”的概率P ＝410＝25.] 4．(2019·福建市第一学期高三模拟考试)某商店随机将三幅分别印有福州三宝(脱胎漆器、角梳、油纸伞)的宣传画并排贴在同一面墙上，则角梳与油纸伞的宣传画相邻的概率是________．解析：记脱胎漆器、角梳、油纸伞的宣传画分别为a ，b ，c ，则并排贴的情况有abc ，acb ，bac ，bca ，cab ，cba ，共6种，其中b ，c 相邻的情况有abc ，acb ，bca ，cba ，共4种，故由古典概型的概率计算公式，得所求概率P ＝46＝23. 答案：235．(2019·贵阳市一模)某校选定4名教师去3个边远地区支教(每地至少1人)，则甲、乙两人不在同一边远地区的概率是________．解析：某校选定4名教师去3个边远地区支教(每地至少1人)，基本事件总数n ＝C 24C 12C 11A 22·A 33＝36， 甲、乙两人在同一边远地区包含的基本事件个数m ＝C 22A 33＝6，∴甲、乙两人不在同一边远地区的概率是P ＝1－m n ＝1－636＝56. 答案：56考点一 简单的古典概念(自主练透)[题组集训]1．(2019·包头市一模)某学生食堂规定，每份午餐可以在三种热菜中任选两种，则甲、乙两同学各自所选的两种热菜相同的概率为( )A.12B.13C.14D.16解析：B [学生食堂规定，每份午餐可以在三种热菜中任选两种，甲、乙两同学各选两种热菜，基本事件总数n ＝C 23C 23＝9， 甲、乙两同学各自所选的两种热菜相同包含的基本事件个数m ＝C 23＝3，∴甲、乙两同学各自所选的两种热菜相同的概率为P ＝m n ＝39＝13.故选B.] 2．(2019·全国Ⅱ卷)生物实验室有5只兔子，其中只有3只测量过某项指标．若从这5只兔子中随机取出3只，则恰有2只测量过该指标的概率为( )A.23B.35C.25D.15解析：B [测量过指标的兔子设为A ，B ，C ，没有测量过指标的兔子设为E ，F ，随机取出3只有ABC ，ABE ，ABF ，AEF ，BCE ，BCF ，BEF ，CEF ，ACE ，ACF 共10种，则恰有2只测量过指标的有ABE ，ABF ，BCE ，BCF ，ACE ，ACF 共6种，其概率为610＝35.] 3．(2019·全国Ⅰ卷)我国古代典籍《周易》用“卦”描述万物的变化．每一“重卦”由从下到上排列的6个爻组成，爻分为阳爻“—”和阴爻“－－”，如图就是一重卦．在所有重卦中随机取一重卦，则该重卦恰有3个阳爻的概率是( )A.516B.1132C.2132D.1116解析：A [要求的概率为P ＝C 36⎝⎛⎭⎫123⎝⎛⎭⎫123＝516，故选A.]1．求古典概型概率的步骤(1)读题，理解题意；(2)判断试验结果是否为等可能事件，设出所求事件A ；(3)分别求出基本事件总数n 与所求事件A 所包含的基本事件的个数m ；(4)利用公式P (A )＝m n求出事件A 的概率. 提醒：在计算基本事件总数和事件包括的基本事件个数时，要注意它们是否是等可能的．2．求较复杂事件的概率问题的方法(1)将所求事件转化成彼此互斥的事件的和事件，再利用互斥事件的概率加法公式求解．(2)先求其对立事件的概率，再利用对立事件的概率公式求解．(3)在求基本事件总数和所求事件包含的基本事件数时，要保证计数的一致性，就是在计算基本事件数时，都按排列数求，或都按组合数求．考点二 古典概型的交汇问题(多维探究)[命题角度1] 古典概型与平面向量相结合1．(2019·兰州市模拟)如图，在平行四边形ABCD 中，O 是AC 与BD 的交点，P ，Q ，M ，N 分别是线段OA ，OB ，OC ，OD 的中点．在A ，P ，M ，C 中任取一点记为E ，在B ，Q ，N ，D 中任取一点记为F .设G 为满足向量OG →＝OE →＋OF →的点，则在上述的点G 组成的集合中的点，落在平行四边形ABCD 外(不含边界)的概率为________．解析：基本事件的总数是4×4＝16，在OG →＝OE →＋OF →中，当OG →＝OP →＋OQ →，OG →＝OP →＋ON →，OG →＝ON →＋OM →，OG →＝OM →＋OQ →时，点G 分别为该平行四边形的各边的中点，此时点G 在平行四边形的边界上，而其余情况的点G 都在平行四边形外，故所求的概率是1－416＝34. 答案：34古典概型与平面向量交汇问题的处理方法(1)根据平面向量的知识进行坐标运算，得出事件满足的约束条件；(2)根据约束条件(等式或不等式)列举所有符合的结果；(3)利用古典概型概率计算公式求解概率．[命题角度2] 古典概型与圆锥曲线相结合2．(2019·洛阳市统考)将一颗骰子先后投掷两次分别得到点数a ，b ，则直线ax ＋by ＝0与圆(x －2)2＋y 2＝2有公共点的概率为________．解析：依题意，将一颗骰子先后投掷两次得到的点数所形成的数组(a ，b )有(1,1)，(1,2)，(1,3)，…，(6,6)，共36种，其中满足直线ax ＋by ＝0与圆(x －2)2＋y 2＝2有公共点，即满足2aa 2＋b 2≤2，a 2≤b 2的数组(a ，b )有(1,1)，(1,2)，(1,3)，(1,4)，…，(6,6)，共6＋5＋4＋3＋2＋1＝21种，因此所求的概率等于2136＝712. 答案：712古典概型与圆锥曲线相结合的处理方法(1)首先根据圆锥曲线的相关性质，确定相关参数应满足的条件；(2)再根据相关参数满足的条件进行分类考虑，求出所有符合条件的基本事件个数；(3)最后利用古典概型的概率计算公式求解概率．[命题角度3] 古典概型与函数相结合3．设a ∈{}2，4，b ∈{}1，3，函数f (x )＝12ax 2＋bx ＋1. (1)求f (x )在区间(]－∞，－1上是减函数的概率；(2)从满足条件的所有函数f (x )中随机抽取两个，求它们在(1，f (1))处的切线互相平行的概率．解：(1)f ′(x )＝ax ＋b ，由题意f ′(－1)≤0，即b ≤a ，而(a ，b )共有(2,1)，(2,3)，(4,1)，(4,3)四种，满足b ≤a 的有3种，故概率为34. (2)由(1)可知，函数f (x )共有4种可能，从中随机抽取两个，有6种抽法．∵函数f (x )在(1，f (1))处的切线的斜率为f ′(1)＝a ＋b ，∴这两个函数中的a 与b 之和应该相等，而只有(2,3)，(4,1)这1组满足，∴概率为16.古典概型与函数交汇问题的处理方法(1)首先根据函数的相关性质，确定相关系数应满足的条件；(2)再根据系数满足的条件进行分类考虑，求出所有符合条件的基本事件个数；(3)最后利用古典概型的概率计算公式求解概率．[命题角度4] 古典概型与统计相结合4．某车间共有12名工人，随机抽取6名作为样本，他们某日加工零件个数的茎叶图如图所示，其中茎为十位数，叶为个位数，日加工零件个数大于样本均值的工人为优秀工人．要从这6人中，随机选出2人参加一项技术比赛，选出的2人至少有1人为优秀工人的概率为________．解析：由已知得，样本均值为x －＝20＋60＋30＋(7＋9＋1＋5)6＝22，所以优秀工人只有2人，所以所求概率为P ＝C 26－C 24C 26＝915＝35. 答案：355．从某地高中男生中随机抽取100名同学，将他们的体重(单位：kg)数据绘制成频率分布直方图(如图所示)．由图中数据可知体重的平均值为________kg ；若要从体重在[60,70)，[70,80)，[80,90]三组内的男生中，用分层抽样的方法选取12人参加一项活动，再从这12个人中选两人当正副队长，则这两人体重不在同一组内的概率为________．解析：由频率分布直方图可知，体重在[40,50)内的男生人数为0.005×10×100＝5，同理，体重在[50,60)，[60,70)，[70,80)，[80,90]内的人数分别为35,30,20,10，所以体重的平均值为45×5＋55×35＋65×30＋75×20＋85×10100＝64.5.利用分层抽样的方法选取12人，则从体重在[60,70)，[70,80)，[80,90]三组内选取的人数分别为12×3060＝6,12×2060＝4,12×1060＝2，则两人体重不在同一组内的概率为C 16C 16＋C 14C 18＋C 12C 110A 212＝23. 答案：64.5 23解决与古典概型交汇命题的问题时，把相关的知识转化为事件，列举基本事件，求出基本事件和随机事件的个数，然后利用古典概型的概率计算公式进行计算.1．(2019·武汉市模拟)从装有3双不同鞋的柜子里，随机取2只，则取出的2只鞋不成对的概率为( )A.1415B.45C.35D.15解析：B [从装有3双不同鞋的柜子里，随机取2只，基本事件总数n ＝C 26＝15，取出的2只鞋不成对包含的基本事件m ＝C 26－C 13＝12，则取出的2只鞋不成对的概率为P ＝m n ＝1215＝45.故选B.] 2．男女生共8人，从中任选3人，出现2个男生，1个女生的概率为1528，则其中女生人数是( )A ．2人B ．3人C ．2人或3人D ．4人解析：C [设女生人数是x 人，则男生(8－x )人，又∵从中任选3人，出现2个男生，1个女生的概率为1528， ∴C 28－x C 1x C 38＝1528，∴x ＝2或3.故选C.] 3．(2019·沈阳市教学质量检测(一))将A ，B ，C ，D 这4名同学从左至右随机地排成一排，则“A 与B 相邻且A 与C 之间恰好有1名同学”的概率是( )A.12B.14C.16D.18解析：B [A ，B ，C ，D 4名同学排成一排有A 44＝24种排法．当A ，C 之间是B 时，有2×2＝4种排法，当A ，C 之间是D 时，有2种排法．所以所求概率为4＋224＝14，故选B.] 4．满足a ，b ∈{－1,0,1,2}，且关于x 的方程ax 2＋2x ＋b ＝0有实数解的概率为( ) A.712 B.1112 C.1116 D.1316解析：D [满足条件的方程共有4×4＝16个，即基本事件共有16个．若a ＝0，则b ＝－1,0,1,2，此时共组成四个不同的方程，且都有实数解；若a ≠0，则方程ax 2＋2x ＋b ＝0有实根，需Δ＝4－4ab ≥0，所以ab ≤1，此时(a ，b )的取值为(－1,0)，(－1,1)，(－1，－1)，(－1,2)，(1,1)，(1,0)，(1，－1)，(2，－1)，(2,0)，共9个．所以(a ，b )的个数为4＋9＝13.因此，所求的概率为1316.] 5．(2019·福建省普通高中质量检查)某食品厂制作了3种与“福”字有关的精美卡片，分别是“富强福”“和谐福”“友善福”，每袋食品中随机装入一张卡片．若只有集齐3种卡片才可获奖，则购买该食品4袋，获奖的概率为( )A.316B.49C.38D.89解析：B [将3种不同的精美卡片随机放进4个食品袋中，根据分步乘法计数原理可知共有34＝81种不同放法，4个食品袋中3种不同的卡片都有的放法共有3×C 24×A 22＝36种，根据古典概型概率公式得，能获奖的概率为3681＝49，故选B.] 6．口袋内装有一些除颜色不同之外其他均相同的红球、白球和黑球，从中摸出1个球，摸出红球的概率是0.42，摸出白球的概率是0.28，若红球有21个，则黑球有________________个．解析：摸到黑球的概率为1－0.42－0.28＝0.3.设黑球有n 个，则0.4221＝0.3n，故n ＝15. 答案：157．在30瓶饮料中，有3瓶已过了保质期．从这30瓶饮料中任取2瓶，则至少取到一瓶已过保质期的概率为________．(结果用最简分数表示)解析：由题意知本题属古典概型，概率为P ＝C 127C 13＋C 23C 230＝28145，或概率为P ＝1－C 227C 230＝28145. 答案：281458．已知小李每次打靶命中靶心的概率都为40%，现采用随机模拟的方法估计小李三次打靶恰有两次命中靶心的概率．先由计算器产生0到9之间取整数值的随机数，指定0,1,2,3表示命中靶心，4,5,6,7,8,9表示未命中靶心，再以每三个随机数为一组，代表三次打靶的结果，经随机模拟产生了如下20组随机数：321 421 191 925 271 932 800 478 589 663531 297 396 021 546 388 230 113 507 965据此估计，小李三次打靶恰有两次命中靶心的概率为________．解析：由题意知，在20组随机数中表示三次打靶恰有两次命中靶心的有421,191,271,932,800,531，共6组随机数，所以所求概率为620＝0.30. 答案：0.309．(2019·信阳市模拟)2018年11月28日凌晨，张家口市桥东区河北盛华化工有限公司附近发生爆炸起火事故，甲、乙等五名消防官兵被随机地分到A ，B ，C ，D 四个不同的地点救火，每个地点至少有一名消防人员．(1)求甲、乙两人同时参加A 地点救火的概率；(2)求甲、乙两人不在同一个地点救火的概率；(3)求五名消防人员中仅有一人参加A 地点救火的概率．解：(1)记“甲、乙两人同时参加A 地点救火”为事件E A ，那么P (E A )＝A 33C 25A 44＝140，即甲、乙两人同时参加A 地点救火的概率是140. (2)记“甲、乙两人同时参加同一地点救火”为事件E ，那么P (E )＝A 44C 25A 44＝110，所以甲、乙两人不在同一地点救火的概率是P (E )＝1－P (E )＝910. (3)有两人同时参加A 地点救火的概率P 2＝C 25A 33C 25A 44＝14，所以仅有一人参加A 地点救火的概率P 1＝1－P 2＝34. 10．(2018·高考天津卷)已知某校甲、乙、丙三个年级的学生志愿者人数分别为240,160,160，现采用分层抽样的方法从中抽取7名同学去某敬老院参加献爱心活动．(1)应从甲、乙、丙三个年级的学生志愿者中分别抽取多少人？(2)设抽出的7名同学分别用A ，B ，C ，D ，E ，F ，G 表示，现从中随机抽取2名同学承担敬老院的卫生工作．(ⅰ)试用所给字母列举出所有可能的抽取结果；(ⅱ)设M 为事件“抽取的2名同学来自同一年级”，求事件M 发生的概率．解：(1)由已知，甲、乙、丙三个年级的学生志愿者人数之比为3∶2∶2，由于采用分层抽样的方法从中抽取7名同学，因此应从甲、乙、丙三个年级的学生志愿者中分别抽取3人，2人，2人．(2)(ⅰ)从抽出的7名同学中随机抽取2名同学的所有可能结果为{A ，B }，{A ，C }，{A ，D }，{A ，E }，{A ，F }，{A ，G }，{B ，C }，{B ，D }，{B ，E }，{B ，F }，{B ，G }，{C ，D }，{C ，E }，{C ，F }，{C ，G }，{D ，E }，{D ，F }，{D ，G }，{E ，F }，{E ，G }，{F ，G }，共21种．(ⅱ)由(1)，不妨设抽出的7名同学中，来自甲年级的是A ，B ，C ，来自乙年级的是D ，E ，来自丙年级的是F ，G ，则从抽出的7名同学中随机抽取的2名同学来自同一年级的所有可能结果为{A ，B }，{A ，C }，{B ，C }，{D ，E }，{F ，G }，共5种．所以，事件M 发生的概率P (M )＝521.。

第一篇集合论第一章集合及其运算1.1 集合的概念1.2 子集、集合的相等1.3 集合的基本运算1.4 余集、De Morgan公式1.5 笛卡尔乘积1.6 有穷集合的基数第二章映射2.1 函数的一般概念——映射定义::映射(法则),映射(笛卡尔乘积),限制和扩张,部分映射,映射相等,单射,满射,双射,恒等映射2.2 抽屉原理2.3 映射的一般性质定义::象f(A),原象f-1(A)[定理2.3.1](1)f-1(C∪D)=f-1(C)∪f-1(D);(2)f-1(C∩D)=f-1(C)∪f-1(D);(3)f-1(CΔD)=f-1(C)Δf-1(D);(4)f-1(C C)=(f-1(C))C⊆⊇⊇[定理2.3.2]∪∪(5)f(A B)=f(A)f(B);(6)f(A∩B)f(A)∩f(B);(7) f(AΔB)f(A)Δf(B);(8) f(A\B)f(A)\f(B)2.4 映射的合成定义::映射的合成[定理2.4.1]合成符合结合律,但不符合交换律[定理2.4.2]设f:X→Y,则f∘I X=I Y∘f =f[定理2.4.3]设f:X→Y,g:Y→Z, 则(1)若f与g都是单射,则g∘f也是单射:f是单射,∀x1x2且x1≠x2 y1=f(x1),y2=f(x2)且y1≠y2有g(f(x1))≠g(f(x2))(2)若f与g都是满射,则g∘f也是满射:f满射,∀y必有x∈X使f(x)=y.∀z∈Z必有y∈Y使g(y)=z.则∀z∈Z必有x∈X使g(f(x))=z.(3)若f与g都是双射,则g∘f也是双射[定理2.4.4]设f:X→Y,g:Y→Z, 则(1)若g∘f是单射,则f是单射;∀x1,x2∈X且x1≠x2有g(f(x1)) ≠g(f(x2))(2)若g∘f是满射,则g是满射;反证:∃z∈Z使∀y∈Y,g(y)≠z则有∀x∈X有g(f(x)) ≠z推出矛盾(3)若g∘f是双射,则f是单射且g是满射[定理2.4.5]设f与g都是X到X的映射,则I m (f)⊆I m(g)的充分必要条件是存在一个映射h:X→X使得f=g∘h2.5 逆映射定义::逆映射,左逆映射,右逆映射[定理2.5.1]逆映射存在的充要条件是f是双射::⇒ Ix,Iy+定理2.4.4⇐构造g(y)=x当且仅当f(x)=y[定理2.5.2]逆映射唯一::假设不唯一,推出g=I x°g=(h°f)°g=h°(f°g)=h°I x=h[定理2.5.3] (gf)-1=f-1g-1,(f-1)-1=f:(gf)(f-1g-1)=g(ff-1) g-1= gg-1=I z, (f-1g-1) (gf)=f(gg-1)f-1= ff-1=I x[定理2.5.4](1)f是左可逆的充分必要条件是f为单射:⇒定义+定理⇐f:X→I m(f)的双射,建立g:I m(f)→X双射,在扩充到Y上,y∉I m(x)随便映射一个(2)f是右可逆的充分必要条件是f为满射:⇒定义+定理⇐构造2.6 置换定义::n次置换,k-循环置换,对换,奇置换,偶置换[定理2.6.1][定理2.6.2][定理2.6.3]置换α,β没有共同数字时可以交换[定理2.6.4]置换可进行唯一循环分解[定理2.6.5]置换分解成若干对换的乘积,分解个数的奇偶性不变[定理2.6.6]奇偶置换个数相等,都等于n!/22.7 二元和n元运算定义::有限序列,无限序列,子序列,二元运算,一元运算,n元运算,交换律,结合律,代数系的同构2.8 集合的特征函数定义::集合的特征函数第三章关系3.1 关系的概念定义::关系(映射),关系(笛卡尔乘积),定义域,值域,多部映射,关系(多部映射),多值二元关系3.2 关系的性质定义::自反,反自反,对称(R对称⟺R=R-1),反对称,传递,相容,逆3.3 关系的合成运算定义::关系的合成,[定理3.3.1]关系的合成不符合交换律,但符合结合律[定理3.3.2](1)R1°(R2∪ R3 )=(R1°R2)∪(R1°R3);(2)R1° (R2∩ R3 )⊆(R1°R2)∩(R1°R3);(3)(R2∪R3 )°R4 = (R2°R4) ∪(R3°R4);(4)(R2∩R3 ) °R4⊆(R2°R4) ∩(R3°R4) [定理3.3.3](1)(R∘S)-1 = S-1∘R-1:(2)R∘R-1 是对称的[定理3.3.4]R是传递关系⟺R°R⊆R[定理3.3.5]R0=I x;R1=R;R n+1=R n°R;R m°R n=R m+n;(R m)n=R mn[定理3.3.6]设X是一个有限集合且|X|=n,R为X上的任一二元关系,则存在非负整数s,t,使得0≤s<t≤2n^2且R s= R t[定理3.3.7]设R是X上的二元关系,若存在非负整数s,t,s<t,使得且R s= R t ,则(1)R s+k= R t+k ,k为非负整数(2)R s+kp+i= R s+i ,其中p=t-s,而k,i为非负整数(3)令S={R0,R,R2 ,…,R t-1},则对任意的非负的整数q,有R q ∈S[定理3.3.8]R对称且传递⟺R=R°R-13.4 关系的闭包定义::传递闭包(所有包含R的传递关系的交,可以类似定义自反传递闭包等),自反传递闭包,自反闭包,对称闭包[定理3.4.1]关系R的传递闭包是传递关系(如果R是传递关系,R+=R):[定理3.4.2]R+=∪R i=R∪R2∪R3∪…:: R+⊆∪R i只要证明∪R i是包含R的传递关系, ∪R⊆R+只要证明(a,b)∈R m,(b,c)∈R n.(a,c)∈R m+n,(a,c) ∈R+[定理3.4.3]R+=∪R n=R∪R2∪R3∪…R n::证明R k⊆∪R i,如果k>n,x仅有n个元素,由抽屉原理得存在b i=b j重复以上过程证明.[定理3.4.5]R*=R0∪R+3.5 关系矩阵和关系图定义:: (1)R是自反的,当且仅当B的对角线上的全部元素都为1;(2) R是反自反的当且仅当B的对角线上的全部元素都为0;(3) R是对称的当且仅当B是对称矩阵;(4) R是反对称的当且仅当b i j与b j i不同时为1,i≠j;(5) R是传递的当且仅当若b i j=1且b j k=1,则b i k=1; (6) R-1的矩阵是B T3.6 等价关系和集合划分定义::等价关系(1.自反2.对称3.传递),等价类,商集[定理3.6.3]3.7 映射按等价关系划分3.8 偏序关系和偏序集定义::偏序关系(自反,反对称,传递),偏序集,全序集,Hasse图,上下界,最大最小元素,链与反链第四章无穷集合及其基数4.1可数集定义::可数集(从自然数集N到集合A有一一映射),无限集(能与自身的真子集对等的集合),代数数,超越数[定理4.1.1]集合A为可数集⟺A的全部元素可以排成无重复项的序列[定理4.1.2]无限集中包含可数子集[定理4.1.3]两个可数集的并是可数集[定理4.1.4]有限个可数集的并是可数集[定理4.1.7]可数个可数集的并是可数集:写成无穷阶方阵,按对角线游历[定理4.1.8]有理数集Q是可数集[定理4.1.10]一列有限个集合的笛卡尔乘积为可数集4.2连续统集定义::连续统(与[0,1]实数集对等)[定理4.2.1]区间[0,1]内的全体实数构成不可数无穷集::康托对角线第二篇图论第六章图的基本概念6.1图论的产生与发展概述6.2基本定义定义::无向图,G(p,q),平凡图,零图,有向图,定向图,子图,生成子图,导出子图,图的同构,度(degv),δ(G),Δ(G),正则图(推论三次图的顶点个数为偶数)[定理6.2.1]欧拉定理:Σ(degv)=2q推论度为奇数的点的个数必为偶数6.3路、圈、连通图定义::通道,闭通道,迹,闭迹,路,圈(回路),连通图,支[定理6.3.1]uv有路⟺u≅v[定理6.3.2]degu+degv≥p–1⟹G连通::拆成两个支用结论反证,degu≤n1-1,degv≤p-n1-1推出与结论的矛盾[定理6.3.3]∀v∈V,degv为偶数⟹G中有圈::设最长路证明[定理6.3.4]∃u,v中有两条不同路⟹G有圈::6.4补图、偶图定义::补图,自补图,三角形,偶图,完全偶图(Km,n), 图上两点间的距离d(u,v)[定理6.4.1]R(3,3)≤6::抽屉原理+[定理6.4.2]偶图判断的充要条件:图上所有的圈的长度都为偶::⇒将圈上的奇偶序的点放入两个顶点划分中⇐取定一点按距离奇偶构造[定理6.4.3](Turan定理)p个顶点没有三角形的图至多有[p^2/4]::6.5欧拉图定义::欧拉闭迹,欧拉图,欧拉迹[定理6.5.1]欧拉图存在定理:G的每个顶点的度都为偶::⇒显然⇐结合定理6.3.3造N个圈Zi然后数归证明这些圈相接.推论::欧拉图的等价命题: 1)G是欧拉图2)∀v∈V,degv为偶数3)G的边能划分成若干不相交的圈.[定理6.5.2]欧拉迹存在定理:: ⇒从定理6.5.1获得⇐uv奇数度,加edge(u,v)得欧拉迹C,在C上去掉edge(u,v).6.6哈密顿图定义::哈密顿圈、哈密顿图[定理6.6.1]G是Hamilton⟹∀S∈V有ω(G-S)<|S|[定理6.6.2](Dirac定理)p个顶点的图G,δ(p)≥p/2,⟹G是一个哈密顿图.[定理6.6.3](Ore定理)p个顶点的图,∀u,v(u,v不邻接),均有degu+degv≥p⟹G是哈密顿图.[定理6.6.4]p个顶点的图,∀u,v(u,v不邻接),均有degu+degv≥p-1⟹G是哈密顿图.6.7图的邻接矩阵[定理6.7.1]图同构的邻接矩阵判定[定理6.7.2]ij顶点间长l的通道条数=A l(i,j)::数归l,[定理6.7.3]G(p,q),连通⟺(A+I)^(p-1)>0::⇒定理6.7.2⇐定理6.7.2第七章树和割集7.1树及其性质定义::树,极小连通图(推论树是极小连通图), 偏心率,树的半径,树的中心[定理7.1.1]树的六个等价命题:1)树;2)G中任两点有且只有一条路;3)G连通且p=q+1; 4)G无圈且p=q+1;5)G无圈且其中任意不相邻两点加边得唯一的圈;6)连通(p≥3且G非Kp)且其中任意不相邻两点加边得唯一的圈.推论非平凡树至少有两个度为1的顶点且非平凡树是偶图::偶图判断的构造证明法[定理7.1.2]树的中心的位置7.2生成树定义::生成树, 生成森林, 生成树的距离,生成树的基本变换[定理7.2.1]生成树存在⟺G连通::⟹显然⟸破圈法.推论G连通⟹q≥p-1[定理7.2.2](Cayley定理)Kp的生成树的个数=p(p-2)[定理7.2.3]生成树中去掉边集E1后必能找到另一不在原生成树中的边集E2使T-E1+E2为生成树[定理7.2.4]距离为k的两个生成树可以经过k次基本变换互相得到::数归,由定理7.2.3知,d(T0,T)=k去掉e1后必然有e2∉T0使(T0-e1)+e2=T1,而d(T1,T)=k-1得到归纳.7.3割点、桥和割集定义::割点,桥,割集(有极小性)[定理7.3.1]割点的等价命题:1)v是割点;2)∃u,w≠v使uw间所有路经过v;3)∃划分{U,W} UW间所有路经过v;[定理7.3.2]桥的等价命题:1)x是桥;2)x不在G的任何圈上3)∃u,v使x在连接uw所有路上;4)∃划分{U,W},使x在连接UW所有路上; [定理7.3.4]割集将图分成两个支(推论有k个支的图G去掉割集后有k+1个支)[定理7.3.5]割集必然包含生成树的某条边::反证[定理7.3.6]割集与G中的圈必有偶数条公共边::G1G2取定一点周游,e(u,v)(u∈G1,v∈G2)是圈与割集相交的边第八章连通度和匹配8.1顶点连通度和边连通度定义::κ(G), λ(G), n-连通,n-边连通[定理8.1.1]κ(G)≤λ(G)≤δ(G)[定理8.1.2]κ(G)=a,λ(G)=b,δ(G)=c的构造方法:构造两个Kc+1,用b条边连接这两个支[定理8.1.3]G(V,E)有p个顶点且δ(G)≥ [p/2]⟹λ(G)=δ(G)::[定理8.1.4][定理8.1.5]∀u,v∈V且u,v∈C⟺G是2-连通[定理8.1.6]8.2门格尔定理8.3匹配、霍尔定理定义::匹配,最大匹配,偶图G的完备匹配,相异代表系, 完美匹配[定理8.3.1](Hall定理)::[推论8.3.1]第九章平面图和图的着色9.1平面图及其欧拉公式定义::平面图,面,内部面,外部面[定理9.1.1]欧拉定理:平面图有p-q+f=2::通过f数归[推论9.1.1]每个面都由长为n的圈围成⟹q=n(p-2)/(n-2)::每条边都与两个面邻接⟹2q=nf拓展最大可平面图[推论9.1.2]G(p,q)的最大可平面图每个面都是三角形且q=3p-6[推论9.1.3]每个面都由长为4的圈围成⟹q=2p-4::拓展没有三角形的边极大图[推论9.1.4]G(p,q),q≤3p-6,G没有三角形q≤2p-4[推论9.1.5]K5和K3,3都是不可平面图::K5,f=7,由于每个面至少三条边, K3,3中每个圈至少为4[推论9.1.6]G可平面⟹ (G)≤5::反证+推论9.1.49.2非哈密顿平面图[定理9.2.1]Grinberg定理:G(V,E)是(p,q)平面哈密顿图,C是哈密顿圈.令fi为C的内部由i条边围成的面的个数,gi为C的外部由i条边围成的面的个数则(1)Σ(i-2)fi=p-2;(2) Σ(i-2)gi=p-2;(3) Σ(i-2)(fi-gi)=0;9.3库拉托斯基定理、对偶图定义::细分,同胚,初等收缩,对偶图[定理9.3.1](Kuratowski定理)G可平面⟺G没有同胚于K5或K3,3的子图[定理9.3.2](Wagner定理) G可平面⟺G没有收缩到K5或K3,3的子图9.4顶点的着色定义::n-可着色,色数(有极小性),χ(G)[定理9.4.2]Δ=Δ(G),G是(Δ+1)- 可着色的.[定理9.4.3-定理9.4.5]平面图可以4着色9.5边的着色定义::n-边着色,边色数(有极小性), χ’(G)第十章有向图10.1有向图的概念定义::有向图,弧,对称弧,定向图,带环图,多重有向图,有向图的反图,入度(id(v)),出度(od(v)),完全有向图,有向图的补图,有向图的同构[定理10.1.1]Σid(v)= Σod(v)=q且Σ(id(v)+od(v))=2q10.2有向路和有向圈定义::有向通道,有向闭通道,生成通道,有向迹,有向闭迹,生成(闭)轨迹,有向路,有向圈,有向回路,可达,半(弱)通道,强连通,强支,单连通,弱连通,有向图的连通[定理10.2.1]有向图D是强连通的⟺D有一条闭生成通道[定理10.2.2]uRv当且仅当uv可互达⟹R是V上的等价关系[定理10.2.3]有向图D的每个顶点都在D的一个强支中[定理10.2.4]一个没有有向圈的有向图至少有一个出度为0的顶点[定理10.2.5]有向图D没有圈⟺D中每条有向通道都是有向路[定理10.2.6]有向图D有有向圈⟺D的子图D1(V1,E1),∀v∈V1,id(v)>0,od(v)>0[定理10.2.7]连通有向图D,∀v∈V,od(v)=1,D中恰有一个有向圈10.3强连通图的应用10.4有向图的邻接矩阵定义::有向图的邻接矩阵,可达矩阵,关联矩阵10.5有向树与有序树定义::有向树,有根树,入树,父,子,祖先,真祖先,深度,高度,子树,有序树,m元有序树,正则m元有序树,正则二元树,二元树,满二元树,完全二元树(高为h的二元树,去掉深度为h一层,得到满树,而且h层从左向右排布)[定理10.5.1]有向图D是有根树⟺D没有弱圈且D中存在一个可以到达其他顶点的顶点(root)::⇒化为无向图证明没有弱圈,用除根以外的点入度为1证可达.⇐[定理10.5.3]高为h的二元树至多有2 (h+1)-1个顶点[定理10.5.4]高为h的完全二元树的顶点数满足2h≤p≤2(h+1)-110.6判定树10.7比赛图定义::比赛图[定理10.7.1]每个比赛图必有生成有向路(有哈密顿路)::。