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