1. 引言
图的多项式包含着关于图的各种信息,并且被用来分析图和网络的特性。其中被研究最多的就有色多项式和流多项式。色多项式最早是在1912年由Birkhoff开始研究的,主要为了攻克四色问题,具体见文献 [1] 。围绕流多项式也有很多重要的理论问题,例如五流猜想和其他流存在性定理。李慰萱等 [2] 求出了以顶点个数、边数和内部面是
圈的内部面的个数为参数的外平面图的色多项式的显式。Boris Brimkov等 [3] 推出了轮图的色多项式及其对偶图的色多项式和流多项式。本文主要在前人研究的基础上,推导出了Farey图及其对偶图的色多项式(包括点色多项式和面色多项式)、流多项式。
2. 预备知识
表示一个图;其中
为
的顶点集,
为
的边集。
定义1 [4] :设
为一个图,
、
和
分别为
的顶点数、边数和连通分支数。令
,
分别称
和
为图
的秩和零度。
定义2 [4] :令
为一个图,
为图
的一个生成子图,则
的Tutte多项式可以定义为
,其中
和
分别为
的秩和零度。
定义3 [5] :图
的一个
着色是指
种颜色
对
的各顶点的一个分配,且任意两个相邻的顶点都分配到不同的颜色;定义色多项式
是图
的不同
着色的数目。
定义4 [3] :平图
的一个
面可着色是指
种颜色
对面的集合
中元素的一种分配,使得有公共边的两个面的颜色不同;定义面色多项式
是图
的不同
面可着色的数目。
定义5 [3] :设
是一个图,
为
的任意一个定向,
为一个Abelian加法群。若映射
满足:对于
中的任意顶点
,都有流进
的流量与流出
的流量相等,则称映射
为图
上的一个
流。若对于任意弧
,有
,则称
为一个处处非零的
流。若
为一个
阶群,图
中处处非零的
流的数目是关于
的一个多项式,这个多项式称为
的流多项式,记为
。
定义6 [5] :给出平图
,可以定义另一个图
如下:对于
的每个面
都有
的顶点
与之对应;
中顶点
和
由边
连接,当且仅当
中与顶点
和
对应的面
和
被
分隔。图
称为
的对偶图。
引理1 [6] :设
是一个图,则
其中
、
、
分别是
的顶点数、边数和连通分支的个数。
引理2 [3] :若图
为平面图,则
。
3. Farey图的色多项式和流多项式
Farey图是一类自相似的外平面图,可以由2种方法构造得到。
1) 迭代构造法 [4] (见图1):设
为第
代Farey图。
Figure 1. Iterative construction method of Farey graphs
图1. Farey图迭代构造法
a)
时,
。
b)
时,
可以通过下面的迭代得到:
在第
步加的每条边
,对应一个新的顶点
,并将
的顶点与顶点
相连,便得到图
。
2) 递归构造法 [4] (见图2):设
为第
代Farey图,且
有两个特殊的顶点,分别设为
和
。
Figure 2. Recursive construction method of Farey graphs
图2. Farey图递归构造法
a)
时,
。由一条边连接点
和
得到。
b)
时,
可以通过两个
得到:用
和
分别表示这两个
。记
中的两个特殊的点分别为
和
。
记
中的两个特殊的点分别为
和
。将点
和
两点重合得到一个新的点,记为
。再将
和
用一条新边相连,将
和
分别记为
和
。这样便得到图了
。
推论1 [4] :为了表示方便,用
表示Farey图
的Tutte多项式
,对于每个
,Farey图
的Tutte多项式为
, (1)
其中
和
都是整系数多项式且满足以下递归关系
, (2)
, (3)
初始条件为
,
。 (4)
定理1 [4] :Farey图
的色多项式为
。
定理2:Farey图
的流多项式为
其中
,且
时,
,初始值
。
证明:为了表示方便,设
并代入引理1,得
。 (5)
其中
、
、
分别是
的顶点数、边数和连通分支的个数。
我们先求
,为了好表示,我们令
,所以我们要将
表示出来。将
代入推论2中的式子(1)、(2)、(3)、(4)得
, (6)
其中
和
都是整系数多项式且满足以下递归关系
, (7)
, (8)
初始条件为
,
。 (9)
由(8)、(9)得
(10)
由(6)、(10)得
(11)
由(7)、(10)得
化简得
(12)
由(12)变换得
,
对
时,引入中间变量
,故可以推出
, (13)
由(7)、(9)可推得
,令
,代入
,得初始值
, (14)
因为
,所以
,故有
(15)
将(16)代入(11)得
(16)
由Farey图
的结构,我们不难计算出
的顶点数、边数和连通分支个数分别为
,
,
,令
,由(5)、(16)、(13)、(14)式得
时,
, (17)
其中
,
。
又因为
,时
,所以
,令
,则
时,也满足(17)式,综上,定理得证。
定理3:Farey图
的面色多项式为
其中
,且
时,
,初始值
。
证明:由引理2得,
。再由对偶图的定义可知
,
所以
,
在定理2中已经推导出
的结果,代入
,定理得证。
4. Farey图的对偶图的色多项式和流多项式
定理4:Farey图
的对偶图
点色多项式为
其中
,且
时,
,初始值
。
证明:由对偶图的定义可知
,又因为定理3,此定理得证。
定理5:Farey图
的对偶图
的面色多项式为
。 (20)
证明:由对偶图的定义可知,
的对偶图
,和
的对偶图
存在以下关系式,
, (18)
又因为
是连通图,所以
,
故
, (19)
又因为定理1,此定理得证。
定理6:Farey图
的对偶图
的流多项式为
证明:由引理2得,
。又因为式子(19)、(18)、(20)
所以定理得证。