图论27电子科大杨春.pptx

该【图论27电子科大杨春 】是由【小屁孩】上传分享，文档一共【33】页，该文档可以免费在线阅读，需要了解更多关于【图论27电子科大杨春 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。Email:yc517922@图论及其应用任课教师:杨春数学科学学院12021/10/10本次课主要内容(一)、色多项式概念(二)、色多项式的两种求法着色的计数与色多项式(三)、色多项式的性质22021/10/10所谓色计数,就是给定标定图G和颜色数k,求出正常顶点着色的方式数。方式数用Pk(G)表示。(一)、色多项式概念可以证明:Pk(G)是k的多项式,称为图G的色多项式。由点色数和色多项式Pk(G)的定义可得:(1)若,则Pk(G)=0;(2)若G为空图,则Pk(G)=kn。(3)Pk(Kn)=k(k-1)…(k-n+1)。32021/10/101、递推计数法(二)、色多项式的两种求法定理1设G为简单图,则对任意有:证明:设e=uv。则对G-e的着色方式数可以分为两部分:(1)u与v着不同颜色。此时,等于G的着色方式数;(2)u与v着同色。此时,等于G·e的着色方式数;所以,得:42021/10/10推论:设G是单图,e=uv是G的一条边,且d(u)=1,则:证明:因为G是单图,e=uv,d(u)=1,所以G·e=G-u。另一方面,Pk(G-e)=kPk(G-u)所以,注:对递推公式的使用分析:52021/10/10(1)当图G的边数较少时,使用减边递推法:(2)当图G的边数较多时,使用加边递推法:例1求出下面各图的色多项式。G1G3G262021/10/10(1)G1也可由推论:G172021/10/10(2)G282021/10/10(3)G3——92021/10/10注:递推计数法的计算复杂度是指数型的。2、理想子图计数法(1)预备知识定义1:设H是图G的生成子图。若H的每个分支均为完全图,则称H是G的一个理想子图。用Nr(G)表示G的具有r个分支的理想子图的个数。例2求N4(G),N5(G)。G102021/10/10