ImageVerifierCode 换一换
格式:PPTX , 页数:32 ,大小:771.88KB ,
资源ID:844913      下载积分:11 金币
验证码下载
登录下载
邮箱/手机:
验证码: 获取验证码
温馨提示:
支付成功后,系统会自动生成账号(用户名为邮箱或者手机号,密码是验证码),方便下次登录下载和查询订单;
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝    微信支付   
验证码:   换一换

开通VIP
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.zixin.com.cn/docdown/844913.html】到电脑端继续下载(重复下载【60天内】不扣币)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录   QQ登录  
声明  |  会员权益     获赠5币     写作写作

1、填表:    下载求助     留言反馈    退款申请
2、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
3、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
4、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
5、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
6、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
7、本文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。

注意事项

本文(图论着色的计数与色多项式.pptx)为本站上传会员【胜****】主动上传,咨信网仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知咨信网(发送邮件至1219186828@qq.com、拔打电话4008-655-100或【 微信客服】、【 QQ客服】),核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载【60天内】不扣币。 服务填表

图论着色的计数与色多项式.pptx

1、1 图论及其应用图论及其应用应用数学学院应用数学学院2本次课主要内容本次课主要内容(一一)、色多项式概念、色多项式概念(二二)、色多项式的两种求法、色多项式的两种求法着色的计数与色多项式着色的计数与色多项式(三三)、色多项式的性质、色多项式的性质3 所谓色计数,就是给定标定图所谓色计数,就是给定标定图G和颜色数和颜色数k,求出正常顶求出正常顶点着色的方式数。方式数用点着色的方式数。方式数用Pk(G)表示。表示。(一一)、色多项式概念、色多项式概念 可以证明:可以证明:Pk(G)是是k的多项式,称为图的多项式,称为图G的色多项式。的色多项式。知道图的色多项式,就可以求出色数为知道图的色多项式,就

2、可以求出色数为k时的着色方式数。时的着色方式数。由点色数由点色数 和色多项式和色多项式Pk(G)的定义可得:的定义可得:(1)若若 ,则,则Pk(G)=0;(2)若若G为空图,则为空图,则Pk(G)=kn。(3)Pk(Kn)=k(k-1)(k-n+1)。4 1、递推计数法、递推计数法(二二)、色多项式的两种求法、色多项式的两种求法 定理定理1 设设G为简单图,则对任意为简单图,则对任意 有:有:证明:设证明:设e=uv。则对。则对G-e的着色方式数可以分为两部分:的着色方式数可以分为两部分:(1)u与与v着不同颜色。此时,等于着不同颜色。此时,等于G的着色方式数;的着色方式数;(2)u与与v着

3、同色。此时,等于着同色。此时,等于Ge 的着色方式数;的着色方式数;所以,得:所以,得:5 推论:设推论:设G是单图,是单图,e=uv是是G的一条边,且的一条边,且d(u)=1,则:则:证明:因为证明:因为G是单图,是单图,e=uv,d(u)=1,所以所以Ge=G-u。另一方面,另一方面,Pk(G-e)=kPk(G-u)所以,所以,注:对递推公式的使用分析:注:对递推公式的使用分析:6 (1)当图当图G的边数较少时,使用减边递推法:的边数较少时,使用减边递推法:(2)当图当图G的边数较多时,使用加边递推法:的边数较多时,使用加边递推法:例例1 求出下面各图的色多项式。求出下面各图的色多项式。G

4、1G3G27 (1)G1 也可由推论:也可由推论:G18 (2)G29 (3)G310 注:递推计数法的计算复杂度是指数型的。注:递推计数法的计算复杂度是指数型的。2、理想子图计数法、理想子图计数法 (1)预备知识预备知识 定义定义1:设:设H是图是图G的生成子图。若的生成子图。若H的每个分支均为的每个分支均为完全图,则称完全图,则称H是是G的一个理想子图。用的一个理想子图。用Nr(G)表示表示G的具的具有有r个分支的理想子图的个数。个分支的理想子图的个数。例例2 求求N4(G),N5(G)。G11 解:通过观察枚举求解:通过观察枚举求Nr(G)G 1)N4(G):G12 N4(G)=6 2)

5、N5(G):G N5(G)=513 定理定理2 设设qr(G)表示将单图表示将单图G的顶点集合的顶点集合V划分为划分为r个不个不同色组的色划分个数,则:同色组的色划分个数,则:证明:一方面,设证明:一方面,设G的任一的任一r色划分为:色划分为:V1,V2,Vr。于是,对于于是,对于1ir,ir,是是 的完全子图。的完全子图。因为因为ViVj=(ij),(ij),所以所以 是是 的理想子图。的理想子图。这说明:这说明:G的任一的任一r色划分必然对应色划分必然对应 的一个理想子图。的一个理想子图。容易知道,这种对应是唯一的;容易知道,这种对应是唯一的;14 另一方面,对于另一方面,对于 的任一具有

6、的任一具有r个分支的理想子图,个分支的理想子图,显然它唯一对应显然它唯一对应G中一个中一个r色组。色组。所以,我们得到:所以,我们得到:上面定理上面定理2实际上给我们提供了色多项式的求法:用实际上给我们提供了色多项式的求法:用k种颜种颜色对单图色对单图G正常着色,可以这样来计算着色方式数:色组为正常着色,可以这样来计算着色方式数:色组为1的方式数的方式数+色组为色组为2的方式数的方式数+色则为色则为n的方式数。即有如下的方式数。即有如下计数公式:计数公式:(2)色多项式求法色多项式求法-理想子图法理想子图法15 定义定义2:设:设G是单图,令是单图,令Ni(G)=ri,ki=xi 。称。称 为

7、图为图G的伴随多项式。的伴随多项式。于是,求于是,求Pk(G)就是要求出就是要求出 的伴随多项式。的伴随多项式。用理想子图法求用理想子图法求Pk(G)的步骤如下:的步骤如下:(1)画出画出G的补图的补图 (2)求出关于补图的求出关于补图的 (3)写出关于补图的伴随多项式写出关于补图的伴随多项式16 (4)将将 代入伴随多项式中得到代入伴随多项式中得到Pk(G)。例例3 求下图求下图G的色多项式的色多项式Pk(G)。G 解:解:(1)G的补图为:的补图为:(2)求出关于补图的伴随多项式系数求出关于补图的伴随多项式系数ri(1i6)i6)17 1)r=6 2)r=5 3)r=418 4)r=3 5

8、)r=2 6)r=1 (3)写出关于补图的伴随多项式写出关于补图的伴随多项式19 (4)将将 代入伴随多项式中得到代入伴随多项式中得到Pk(G)。可以作如下计算:可以作如下计算:由此可以断定:由此可以断定:。最优着色方式数有。最优着色方式数有12种。种。20 使用理想子图法求色多项式,还可以通过如下定理进使用理想子图法求色多项式,还可以通过如下定理进行改进。行改进。定理定理3 若若G有有t个分支个分支H1,H2,Ht,且且Hi的伴随多项式为的伴随多项式为h(Hi,x),i=1,2,t,则:则:该定理说明,在求该定理说明,在求 的伴随多项式时,可以分别求的伴随多项式时,可以分别求出它的每个分支的

9、伴随多项式,然后将它们作乘积。出它的每个分支的伴随多项式,然后将它们作乘积。例例4 求下图求下图G的色多项式的色多项式Pk(G)。21 解解:(1)画出画出G的补图的补图G2154351432H3H2H1 (2)求出补图中个分支的伴随多项式求出补图中个分支的伴随多项式 (3)求出补图的伴随多项式求出补图的伴随多项式22 (4)求出求出G的色多项式的色多项式 注:在例注:在例4中,中,k=3时,时,P3(G)=6,由此可以推出由此可以推出G的点的点色数为色数为3.求出了色多项式,可以由多项式推出点色数。但是,求出了色多项式,可以由多项式推出点色数。但是,求色多项式的计算量是很大的。递推方法是指数

10、类计算求色多项式的计算量是很大的。递推方法是指数类计算量,而理想子图法中主要计算量是找出所有理想子图,量,而理想子图法中主要计算量是找出所有理想子图,这也不是多项式时间算法。这也不是多项式时间算法。23 下面,我们对定理下面,我们对定理3作证明。作证明。定理定理3 若若G有有t个分支个分支H1,H2,Ht,且且Hi的伴随多项式为的伴随多项式为h(Hi,x),i=1,2,t,则:则:分析:由伴随多项式定义:分析:由伴随多项式定义:所以,我们只需要证明所以,我们只需要证明 等于等于 的的k次项系数即可。次项系数即可。设设24 一方面:一方面:该多项式中该多项式中 xk 的系数的系数rk为:为:另一

11、方面:设另一方面:设Mj是是Hj中具有中具有ij个分支的个分支的Hj的理想子图。的理想子图。当当i1+i2+it=k时,时,M1 M2 Mt必是必是G的具有的具有k个个分支的理想子图。分支的理想子图。25 在给定的在给定的i1,i2,it且且i1+i2+it=k情形下,对应的情形下,对应的G的的具有具有k个分支的理想子图个数为:个分支的理想子图个数为:所以,所以,G的具有的具有k个分支的理想子图的总个数为:个分支的理想子图的总个数为:所以得:所以得:26(三三)、色多项式的性质、色多项式的性质 定理定理4 n阶单图阶单图G的色多项式的色多项式Pk(G)是常数项为是常数项为0的首的首1整系数多项

12、式,且各项系数符号正负相间。整系数多项式,且各项系数符号正负相间。证明:对证明:对G的边数进行数学归纳证明。的边数进行数学归纳证明。当当m=0时,时,Pk(G)=kn,命题结论成立。命题结论成立。设设m=k时,命题结论成立。时,命题结论成立。考虑考虑m=k+1的单图的单图G。(m1)取单图取单图G的任意一条边的任意一条边e,考虑考虑G-e与与Ge。对于对于G-e来说,由归纳假设,可设其色多项式为:来说,由归纳假设,可设其色多项式为:27 同样,可设同样,可设Ge的色多项式为:的色多项式为:由色多项式递推公式得:由色多项式递推公式得:注注:(1)定理的逆不成立定理的逆不成立!28 例例5 (1)

13、用递推公式证明:设用递推公式证明:设G=(n,m)是单图,则在其是单图,则在其色多项式色多项式Pk(G)中中kn-1的系数是的系数是-m。(2)不存在以不存在以k4-3k3+3k2为其色多项式的单图。为其色多项式的单图。证明:证明:(1)采用对边数进行数学归纳证明。采用对边数进行数学归纳证明。当当m=1时,时,Pk(G)=Pk(G-e)-Pk(Ge)=kn-kn-1.显然,结论显然,结论成立。成立。设命题对少于设命题对少于m条边的条边的n阶单图成立。考虑单图阶单图成立。考虑单图G=(n,m).由递推公式:由递推公式:Pk(G)=Pk(G-e)-Pk(Ge).由假设可令由假设可令:Pk(G-e)

14、=kn+a1kn-1+an-1kn-1,且,且a1=-m+1;Pk(Ge)=kn-1+b1kn-2+bn-2kn-2,且,且b1=-m+1;29 所以:所以:Pk(G)=kn+(a1+1)kn-1+(a2+b1)kn-2+bn-2kn-2 所以,所以,a1+1=-m。(2)不存在以不存在以k4-3k3+3k2为其色多项式的单图。为其色多项式的单图。事实上,一方面,如果它是某单图的色多项式,则由事实上,一方面,如果它是某单图的色多项式,则由多项式本身可以得到点色数为多项式本身可以得到点色数为1;另一方面,由另一方面,由(1)和多项式本身,如果多项式是某单图和多项式本身,如果多项式是某单图的色多项

15、式,则的色多项式,则m(G)=3,于是点色数至少为于是点色数至少为2.上面推导导出了矛盾!上面推导导出了矛盾!注注:(2)同构的图具有相同的色多项式,但逆不真。同构的图具有相同的色多项式,但逆不真。30 例例6 求证:下面图求证:下面图G1与与G2非同构但具有相同的色多项式。非同构但具有相同的色多项式。G1G2u1v1 证明:因为证明:因为G1和和G2中分别有一个唯一的中分别有一个唯一的4度顶点:度顶点:u1与与v1。但是它们邻点状况不相同。但是它们邻点状况不相同:u1有有4个个2度邻点。而度邻点。而v1只有只有两个两个2度邻点。所以度邻点。所以G1与与G2不同构。不同构。通过直接计算得:通过直接计算得:Pk(G1)=Pk(G2)=10k3+5k4+k5 对于图的色多项式,还有许多结论和进一步研究的问题。对于图的色多项式,还有许多结论和进一步研究的问题。例如:教材上的例如:教材上的Read猜想就是一个待研究问题。猜想就是一个待研究问题。31 作业作业 P187-190 习题习题7:28,31,32,3332Thank You!

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        获赠5币

©2010-2024 宁波自信网络信息技术有限公司  版权所有

客服电话:4008-655-100  投诉/维权电话:4009-655-100

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :gzh.png    weibo.png    LOFTER.png 

客服