ImageVerifierCode 换一换
格式:PPT , 页数:25 ,大小:1.48MB ,
资源ID:494516      下载积分:12 文钱
快捷下载
登录下载
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。 如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝    微信支付   
验证码:   换一换

加入VIP,省得不是一点点
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.wenke99.com/d-494516.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: QQ登录   微博登录 

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文(请在此处填写作品信息(此页非设计模板).ppt)为本站会员(ga****84)主动上传,文客久久仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知文客久久(发送邮件至hr@wenke99.com或直接QQ联系客服),我们立即给予删除!

请在此处填写作品信息(此页非设计模板).ppt

1、,容斥原理 若干应用,09011203王瑶09011204张梦微09011206张雯露,2018/10/15,1、欧拉公式2、棋盘多项式3、色多项式,2018/10/15,欧拉公式,2018/10/15,封面页 (设计好之后可以删掉这个文本框哦),欧拉函数 是求小于n且与n互素的数的个数。,若n分解为素数的乘积设1到n的n个数中为 倍数的集合为则有,。,用容斥原理求欧拉函数,2018/10/15,2018/10/15,封面页 (设计好之后可以删掉这个文本框哦),即比60小且与60无公因子的数有16个:7,11,13,17。19。23,29,31,37,41,43,47,49,53,59,此外尚

2、有一个1。,2018/10/15,封面页 (设计好之后可以删掉这个文本框哦),例.求不超过120的素数个数。,解:因 ,故不超过120的合数必然是2、3、5、7的倍数,而且不超过120的合数的因子不可能都超过11。,设 为不超过120的数 的倍数集, =2,3,5,7。,2018/10/15,2018/10/15,2018/10/15,2018/10/15,注意:27并非就是不超过120的素数个数,因为这里排除了2,3,5,7这四个数,又包含了1这个非素数。2,3,5,7本身是素数。故所求的不超过120的素数个数为:27+4-1=30。,2018/10/15,棋盘多项式,2018/10/15,

3、2.1 棋盘多项式( 特殊的禁位问题),x,x,x,x,x,n 个不同元素的一个全排列可看做n个相同的棋子在nn 的棋盘上的一个布局。布局满足同一行(列)中有且仅有一个棋子,排列41352对应于如图所示的布局。,2018/10/15,可以把棋盘的形状推广到任意形状:,布子规定同上,令rk (C)表示k个棋子布到棋盘C上的方案数。,2018/10/15,2018/10/15,规定 r0(C)=1,包括C=时。设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘;Ce是仅去掉该格子后的棋盘。在上面定义下,显然有,rk(C)=rk-1(Ci)rk(Ce),2018/10/15,2018/10/

4、15,设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘;Ce是仅去掉该格子后的棋盘。,例如:,2018/10/15,如果C由相互分离的C1,C2组成,即C1的任一格子所在的行和列中都没有C2的格子。则有:, R(C) = R(C1) R(C2),2018/10/15,R(C) = xR(Ci) + R(C e) (Ci是棋盘C的某一指定格子所在的行与列都 去掉后所得的棋盘;Ce是仅去掉该格子后的棋盘) R(C) = R(C1) R(C2) (相互分离的C1、C2,即C1的任一格子 所在的行和列中都没有C2的格子) 可以把较复杂的棋盘逐步分解成相对比较简单的棋盘,从而得到其棋盘多项式。

5、,2018/10/15,3,色多项式,2018/10/15,Def1:用x 种颜色对图G的顶点进行着色时,若图 G 的任意两个相邻顶点都分配到不同的颜色,则称此着色为图G的正常x顶点着色。 Def2:图G的不同x 着色的数目称为图G的色多项式,记为 P (G , x )。利用容斥原理求色多项式设G是任意图,用x 种颜色涂染G的顶点,对于每条边i ,设ai是边i 的端部顶点得到相同颜色的性质( |VG|= n |EG| = r )。,2018/10/15,证明:有色多项式的定义可知,我们所求的色多项式就是不具有性质 的对象数量,再由容斥原理可得,其中x 种颜色涂染 G 的顶点的所有着色的集合记为A,|A|=N=xn,2018/10/15,例 图G如图所示,现用x 种颜色涂染G的顶点,求,2018/10/15,2018/10/15,c,c,

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。