离散数学：8-1 组合分析初步

请交作业六P154:10,15P155:19,20,22 P156:25,28,29P171:1,2,5,7,8P172：12,14P173：16,17作业讲评五P137:1(5)P138:12,14,15,19,20 P137:1(5)(5)1,3,3,3 n可以构成无向图的度数列，n但不能构成无向简单图的度数列。P138:12 画出3阶有向完全图所有非同构的子图，求生成子图、自补图 mn0123456123生成子图P138:14n由 2n-3=mn和握手定理 3n=2mn得 n=6,m=9n其非同构的简单图有两个P138:15 在K6的边上涂上红色或蓝色,证明:对于任意一种随意的涂法，总存在红色K3或蓝色K3n证：因K6任意一个顶点度数为5，不失一般性，对v1 当与v1邻接的5条边用红、蓝涂色时至少有3边涂同一种颜色，不妨设(v1,v2),(v1,v3)(v1,v4)为红色 若(v2,v3),(v2,v4)(v3,v4)有一条边为红色，则存在红色K3;若(v2,v3),(v2,v4)(v3,v4)均为蓝色，则存在蓝色K3.故，对于任意一种随意的涂法，总存在红色K3或蓝色K3。v1v2v3v4v6v5v1v2v3v4v6v5v1v2v3v4v6v5v1v2v3v4v6v5P138:19 求最短路径和距离badecgf713422812341072tabcdefg 1234567(+,)用用Dijkstra标号法标号法求求(+,)(+,)(+,)(+,)(+,)(0,)*(1,b)(7,b)(+,)(+,)(+,)(+,)*(4,c)(5,c)(4,c)*(+,)(+,)(12,a)(5,c)(+,)(4,c)*(5,c)*(12,a)(11,f)(7,e)(12,a)*(9,g)*P138:19 求最短路径和距离b-c-a (4)b-c (1)b-c-e-g-d(9)badecgf713422812341072tabcdefg 1234567(+,)(+,)(+,)(+,)(+,)(+,)(0,)*(1,b)(7,b)(+,)(+,)(+,)(+,)*(4,c)(5,c)(4,c)*(+,)(+,)(12,a)(5,c)(+,)(4,c)*(5,c)*(12,a)(11,f)(7,e)(12,a)*(9,g)*b-c-e (5)b-c-f (4)b-c-e-g (7)P138:20 活动活动 A B C D E F G H I J K L M紧紧前工序前工序 A A,B A,B A,B C,G D,E,F D,E D,E H,J I,L时间时间(天天)3 2 4 4 4 4 2 5 3 3 6 1 141237658ABCDEMFGHKIL3244414256319J3P138:20n 事项事项i 的的最早完成时间最早完成时间:n ES(1)=0n ES(2)=max0+3=3n ES(3)=max 0+2,3+0=3n ES(4)=max 0+4,3+2=5n ES(5)=max 3+4,3+4=7n ES(6)=max 3+4,7+0=7n ES(7)=max 5+5,7+3=10n ES(8)=max 7+3,10+1=11n ES(8)=max 7+6,11+1=1341237658ABCDEMFGHKIL32444142563193JP138:20n 事项事项i 的最晚完成时间的最晚完成时间:n LF(9)=13n LF(8)=min13-1=12n LF(7)=min 12-1=11n LF(6)=min 12-3=9n LF(5)=min 9-0,11-3,13-6=7n LF(4)=min 11-5=6n LF(3)=min 6-2,7-4,9-4=3n LF(2)=min 3-0,7-4=3n LF(1)=min 3-3,3-2,6-4=041237658ABCDEMFGHKIL3244414256319J3P138:20n 事项事项 j 的的缓冲时间缓冲时间SL(j):n SL(1)=0-0=0n SL(2)=3-3=0n SL(3)=3-3=0n SL(4)=6-5=1n SL(5)=7-7=0n SL(6)=9-7=2n SL(7)=11-10=1n SL(8)=12-11=1n SL(9)=13-13=0关键工序关键工序A、D、E、K41237658ABCDEMFGHKIL3244414256319J3关键路径关键路径1-2-5-9，1-2-3-5-9设T是n(n3)阶无向树，T*为T的对偶图n证明：T是简单图是简单图T是二部图是二部图T是平面图是平面图T不不是欧拉图是欧拉图T不不是哈密顿图是哈密顿图T*是平面图是平面图T*是欧拉图是欧拉图T*是哈密顿图是哈密顿图T*不不是简单图是简单图T*不不是二部图是二部图设T是n(n3)阶无向树，T*为T的对偶图n 证明：T是简单图树是连通无回路，树是连通无回路，树无平行边、环树无平行边、环所以，由所以，由简单图的定义简单图的定义得，得，T是简单图。是简单图。T是二部图是二部图 T无回路，无回路，T无长度为奇数的回路，无长度为奇数的回路，所以，由所以，由定理定理6.1知，知，T是二部图。是二部图。T是平面图是平面图 T无回路，无回路，T中没有可以收缩到（或同胚）中没有可以收缩到（或同胚）K5,K3,3的子图，的子图，所以，由所以，由库拉图斯基定理库拉图斯基定理知，知，T是平面图。是平面图。设T是n(n3)阶无向树，T*为T的对偶图n证明：T不是欧拉图 T 是是 n(n3)阶无向树，阶无向树，由由定理定理7.2知，知，T至少有至少有2片树叶，片树叶，它们都是奇数度的顶点它们都是奇数度的顶点所以，由所以，由定理定理6.4知，知，T不是欧拉图。不是欧拉图。T不是哈密顿图不是哈密顿图 T 是是n(n3)阶无向树，阶无向树，对它的每个割点，不满足哈密顿图的对它的每个割点，不满足哈密顿图的必要条件，必要条件，p(G V)|V|所以，由所以，由定理定理6.6知，知，T不是哈密顿图。不是哈密顿图。设T是n(n3)阶无向树，T*为T的对偶图n 证明：T*是平面图T*只有一个顶点，只有一个顶点，T*上所有的环均过该顶点，上所有的环均过该顶点，这些环是可以不相交的，这些环是可以不相交的，所以，所以，T*是平面图。是平面图。T*是欧拉图是欧拉图 T*只有一个顶点，只有一个顶点，T*上所有的环均过该顶点，上所有的环均过该顶点，T*无奇度数的顶点存在，无奇度数的顶点存在，所以，由所以，由定理定理6.4知，知，T*是欧拉图是欧拉图。T*是哈密顿图是哈密顿图 T*只有一个顶点，只有一个顶点，T*上所有的环均过该顶点，上所有的环均过该顶点，T*的每个环均是一条哈密顿回路的每个环均是一条哈密顿回路所以，所以，T*是哈密顿图。是哈密顿图。设T是n(n3)阶无向树，T*为T的对偶图n证明：T*不是简单图 T至少有两片树叶，它在至少有两片树叶，它在T*对应为环，对应为环，所以，由所以，由简单图的定义简单图的定义知，知，T*不是简单图不是简单图。T*不是二部图不是二部图T*只有一个顶点，只有一个顶点，T*上所有的环均过该顶点，上所有的环均过该顶点，而环是奇数长度的回路而环是奇数长度的回路所以，由所以，由定理定理6.1知，知，T*不是二部图不是二部图第8章 组合分析初步 8.1 加法法则和乘法法则8.2 基本排列组合的计数方法8.3 递推方程的求解与应用加法法则n使用条件：事件事件 A与与 B 产生方式不重叠产生方式不重叠n适用问题：分类选取分类选取.方式分别计数，再相加方式分别计数，再相加.n推广：推广：各事件各事件 Ai的产生方式不重叠的产生方式不重叠事件事件 A有有 m 种产生方式，事件种产生方式，事件 B 有有 n 种产生方种产生方式，则式，则“事件事件 A 或或 B”有有 m+n 种产生方式种产生方式.|A1 A2 Ak|=|A1|+|A2|+|Ak|n1A1n2A2nkAk乘法法则n 使用条件：事件事件A与与B产生方式相互独立产生方式相互独立n 适用问题：适用问题：分步选取分步选取.方式是连续的步骤，各步相方式是连续的步骤，各步相互独立，分别计数，然后相乘互独立，分别计数，然后相乘.n 推广推广：各事件各事件 Ai的产生方式相互的产生方式相互独立独立n 当当A1、A2、Ak”是不同的多个事件集合时，乘是不同的多个事件集合时，乘法法则也可以表示法法则也可以表示为为事件事件A有有 m 种产生方式，事件种产生方式，事件 B 有有 n 种产生种产生方式，则方式，则“事件事件 A 与与 B”有有 mn 种产生种产生方式方式|A1 A2 Ak|=|A1|A2|Ak|应用实例n例例1 求求 1400 的不同的正因子个数。的不同的正因子个数。n解：解：1400的素因子分解是的素因子分解是 1400=14100=23527 因此，因此，1400的任何正因子都具有下述形式：的任何正因子都具有下述形式：2i 5j 7k 其中其中 0 i 3,0 j 2,0 k 1 根据乘法法则，根据乘法法则，1400的正因子数是的正因子数是i,j,k的选法数：的选法数：N=(3+1)(2+1)(1+1)=248.2 基本排列组合的计数方法选取问题：设选取问题：设 n 元集合元集合 S，从，从 S 中选取中选取 r 个元素个元素.根据是否有序，是否允许重复可将该问题分为四根据是否有序，是否允许重复可将该问题分为四个子类型个子类型不重复不重复重复重复有序有序集合集合排列排列 P(n,r)多重集多重集排列排列无序无序集合集合组合组合 C(n,r)多重集多重集组合组合集合的排列n 从从 n 元集元集 S 中有序、不重复选取的中有序、不重复选取的 r 个元素称个元素称为为S 的一个的一个r 排列排列，nS 的所有的所有 r 排列的数目记作排列的数目记作 n S 的的 r-环排列数环排列数=n ABC,BCA,CAB 在环上只能算一种排列。在环上只能算一种排列。rnrnrnnrnnnPrn0)!(!)1(.)1()!(!rnrnrPrn rnPACB实例2解：解：固定a 和 b 中间选7个字母，有 种方法 将它看作将它看作大字母大字母与其余与其余 17的全排列的全排列,有有 18！种！种，7242P!182724PNu排列排列 26个字母，使得个字母，使得a与与b之间恰有之间恰有7个个字母，求方法数字母，求方法数.ab1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 181 2 3 4 5 6 7实例3(1)10个男孩，个男孩，5个女孩站成个女孩站成一排一排，若，若没女孩相邻没女孩相邻，有多少种方法？有多少种方法？解:共有共有10个男孩，所以不同的排列有个男孩，所以不同的排列有 共有共有11个位置由个位置由5个女孩选择排列，共有个女孩选择排列，共有 所以总共有(2)如果站成一个如果站成一个圆圈圆圈,有多少种方法？有多少种方法？共有共有10个男孩，不同的排列有个男孩，不同的排列有 共有共有10个位置由个位置由5个女孩选择，共有个女孩选择，共有 所以总共有1051010110PP 1 2 3 4 5 6 7 8 9 101010P511P1051011PP1010101P510P集合的组合n 从从 n 元集元集 S 中无序、不重复选取的中无序、不重复选取的 r 个元素称个元素称为为S 的一个的一个r 组合组合，nS 的所有的所有 r 组合的数目记作组合的数目记作例例3：rnrnrnrnrPCrnrn0)!(!rnC基本计数公式的应用解：解：把把1300分成分成A、B、C三个集合，三个集合，令令 A=x|x1(mod 3)=1,4,298，|A|=100 B=x|x2(mod 3)=2,5,299，|B|=100 C=x|x0(mod 3)=3,6,300，|C|=100将方法分类：将方法分类：(1)三个均取自同个一集合三个均取自同个一集合(A,B,C之一之一):(2)A,B,C三个集合各取三个集合各取1个：个：1100C3100C14851003311003100)(CCN例例4 从从1300中任取中任取3个数使得个数使得其和能被其和能被3整除整除，问，问有多少种方法？有多少种方法？基本计数公式的应用解解:1000!=1000 999 998 2 1 解题方法：解题方法：2 5=10将上面的每个因子分解，若分解式中共有将上面的每个因子分解，若分解式中共有 i 个个5,j 个个2，那么那么 min i,j 就是就是 0 的个数的个数.n 11000 中有中有n至少至少500 个是个是2 的倍数，的倍数，j 500;n200 个是个是 5 的倍数，的倍数，n 40 个是个是 25 的倍数（多加的倍数（多加 40个个5），），n 8 个是个是 125 的倍数（再多加的倍数（再多加8个个5），），n 1 个是个是 625 的倍数（再多加的倍数（再多加1个个5）i=200 +40+8+1=249.min i,j=249.例例5 求求1000！的末尾有多少个！的末尾有多少个0？n定理8.5设设多重集多重集 S=a1,a2,ak，则，则S的的r 排列排列数数为为kr。n例：有例：有10种画册，种画册，每种数量不限每种数量不限，现要取，现要取3本本送朋友，共有送朋友，共有103方法。方法。n推论设设多重集多重集 S=n1 a1,n2 a2,nk ak，并且对一，并且对一切切i=1,2,k,有有ni r,则则S的的r 排列数排列数为为kr。n例：有例：有10种画册，种画册，每种数量均大于每种数量均大于3，现要取，现要取3本送朋友，共有本送朋友，共有103方法。方法。多重集的排列n定理8.6 设设多重集多重集 S=n1 a1,n2 a2,nk ak，0 ni +且且n1+n2+nk=n，则，则S的的n排列排列为为 n 证明：证明：分步选取分步选取n先放先放 a1,有有 种方法；种方法；n再放再放 a2,有有 种方法，种方法，.,n放放ak有有 种方法。种方法。多重集的排列1nnC!.!21knnnnN 12111.kknnnnn nn nnNC CC 21nnnC kknnnnnC121.!.!knnnn21!()!rnnCrnr多重集的排列应用!21nnnN 10!3!2!5n 先放3面黄旗后放2面红旗：共有共有n 先放2面红旗后放3面黄旗：共有共有102235CC103325CCn例6：用2面红旗、3面黄旗依次悬挂在一根旗杆中，问可以组成多少种不同的标志？n解：相当于求多重集2红旗，3黄旗的排列数Nn此处此处n=5,n1=2,n2=3n按按定理定理8.6得得多重集的组合n 定理定理8.7 设设S=a1,a2,ak ，则，则S的的r 组合数组合数为为 n 证明设设S的任何一个的任何一个 r 组合的形式为组合的形式为 x1 a1,x2 a2,xk ak，其中其中x1+x2+xk=r,xi 为非负整数为非负整数.这个这个的非负整数解的个数的非负整数解的个数即即为为S的的r 组合数。组合数。下面证明这方程解的个数即为下面证明这方程解的个数即为T=(k-1)0,r 1 的排列数：的排列数：x1个个1 x2个个1 x3个个1 xk个个1r 个个1，k-1个个 0 的全排列数为的全排列数为rrkCkrkrN1)!1(!)!1()!(!)!(11krkrN110 11 01100111 2 3 k-11rr kC T的一个排列的一个排列实例7(多重集的组合)n 从5种不同的球(每种球至少有3个)，每次取3个球，问有多少种方法？n 解：(1)分步解法：3球同色：球同色：共有共有2球同色：球同色：共有共有3球不同色球不同色 共有共有15C1415CC 35Cn 解：(2)按定理定理8.7S=3 a1,3 a2,3 a3,3 a4 3 a5 则则S的的3 组合数组合数为为其中，其中，r=3,k=5 rrkCkrkrN1)!1(!)!1(35373135CCN多重集的组合n推论推论1 设设S=n1 a1,n2 a2,nk ak,且对且对 i=1,2,k有有ni r，则，则S的的r 组合数组合数为为 S的的 r 组合组合形式形式为为 x1 a1,x2 a2,xk ak，其中，其中 x1+x2+xk=r ,xi 为非负整数为非负整数.这个这个的非负整数解的个数的非负整数解的个数即即为为S的的r 组合数。组合数。)!(!)!(11krkrNrrkC1n相当于分别求nx+y+z=0nx+y+z=1nx+y+z=2的非负整数解的个数之和。的非负整数解的个数之和。n多重集的组合问题nk=3,r=0,1,210631241302201CCCCNrrrk10201031CCCrrk31311131CCCrrk62421231CCCrrkx y z x+y+z10 0 0020 0 1130 1 0141 0 0150 1 1261 0 1271 1 0280 0 2290 2 02102 0 02例8:x+y+z 2的非负整数解的个数作业 22P192：1，3P193：6，10