无K3子图的图中1-因子计数

杨 利 民，年 四 洪

(1.大理大学 数学与计算机学院,云南 大理 671003；2.大连理工大学 数学科学学院,辽宁 大连 116024)

0 引 言

1-因子或完美匹配在量子化学、晶体物理学和计算机领域中有重要应用．1-因子或完美匹配是覆盖图的所有顶点的不交边的集合．Tutte在1947年给出1-因子或完美匹配存在的一个充分必要条件[1]．这个结果是图论中的奠基性的定理，在图论历史上有重要意义，然而如何判断1-因子或完美匹配的存在，仍是一个十分困难的问题．相比之下，计算1-因子的个数是更困难的．S(n)-因子计数理论包括S(n)-因子的表示公式和分支分析方法．通过利用已建立的S(n)-因子计数理论和组合数学方法，可以解决无K3子图的图中1-因子计数．

1 定义和引理

定义1令S(n)={Ki：1≤i≤n}，n≥1，并且Ki是有i个顶点的完全图，如果M是图G的一个子图，且M的任意分支都同构于S(n)={Ki：1≤i≤n}的某一元素，那么M叫作图G的一个S(n)-子图，如果M是图G的一个生成子图，那么M叫作图G的一个S(n)-因子．

恰有k个分支的S(n)-因子的个数记为N(G，k)．

S(n)-因子计数的表示公式如下．

图论中分支分析方法公式如下：

2 主要结果

用f(G)记图G中1-因子的个数．

定理1如果图G是无K3子图或三角形的任意图，那么f(G)=N(G,n/2)．

证明因为图G是无K3子图或三角形的任意图，所以它就没有K4，K5，…，Kn子图，从而S(n)-因子的元素只能是K1或K2，即每一个元素是顶点或边．N(G,n/2)是恰有n/2个分支的S(n)-因子的个数，N(G,n/2)的每一分支都是K2，即边，而1-因子是覆盖图G的不交边的集合，所以有公式f(G)=N(G,n/2)．

□

其中S(p,n/2)是第二类Stirling数．

因为图G是无K3子图或三角形，根据定理1，得到f(G)=N(G,n/2)，所以无K3子图的图G中1-因子的计数公式为

□

例1假设图G是一个完全2-部图Kn，n，那么

其中s(n，k)是第一类Stirling数，S(p，k)是第二类Stirling数．

通过定理2，得到完全2-部图Kn，n的1-因子的计数公式

□

推论1对于两类Stirling数有组合恒等式：

证明通过组合计数得到在完全2-部图Kn，n中1-因子的个数f(G)=n!．

根据例1，完全2-部图Kn，n的1-因子的计数公式

所以对于两类Stirling数有组合恒等式：

□

证明如果T是一棵树，那么T是无K3子图或三角形．通过定理2，得到树的1-因子的计数公式为

□

推论2对于两类Stirling数有组合恒等式：

其中Yp=s(n-1，p-1)，根据例2，得到

另一方面，在K1，n-1中1-因子的个数f(K1，n-1)=0．

综上所述，对于两类Stirling数有组合恒等式：

□

因为图G是一棵树，且对∀v∈V，o(G-v)=1，于是在图G中存在1-因子[1]，得到f(G)≥1．

□

□

以下阐述图的分支分析方法计算无K3子图的1-因子的计数．

定理3如果图G是有n个顶点的图，且为无K3子图，P是图G的一个固定顶点，通过顶点P的所有完全图是Ki1，Ki2，…，Kir，那么图G中的1-因子的计数公式为

其中G-V(Kij)是删掉顶点V(Kij)和与V(Kij)相关联的边所得到的图．

证明因为图G是无K3子图，根据定理1，

f(G)=N(G,n/2)

□

定理4假设图G是无K3子图，1-因子存在的充分必要条件是N(G,n/2)≥1．

证明略．

复杂性：计算N(G,n/2)．

定理5假设图G是无K3子图，1-因子不存在的充分必要条件是N(G,n/2)=0．

证明略．

例3假设图1被构造如下，其中Cn是n个顶点的圈，且n是偶数，圈Cn的个数是q，那么f(G)=2q．

图1 毽子图Fig.1 Shuttlecock picture

证明利用分支分析方法，对固定顶点O进行分析，通过顶点O的所有完全图是O，OV0，OV1，…，OVq，即K1和(q+1)K2．图1无K3子图．

情况1O作为K1，删掉顶点O，于是有q个圈Cn和一个圈Cn+1，它们两两不相交，

N(G-V(K1),k-1)=N(Cn+1∪Cn∪…∪Cn,k-1)

情况2过O点的完全图为OV0，删掉OV0，于是有q个圈Cn和一个路Pn-1，它们两两不相交，

N(G-V(K1),k-1)=N(Pn-1∪Cn∪…∪Cn,k-1)

情况3过O点的完全图为OV1，OV2，…，OVq，删掉OV1，OV2，…，OVq，因为OV1，OV2，…，OVq是对称的，于是

N(G-V(OV1),k-1)=

N(G-V(OV2),k-1)=…=

N(G-V(OVq),k-1)=

N(Cn+1∪Pn-2∪Cn∪…∪Cn,k-1),

N(G-V(OV1),k-1)+N(G-V(OV2),k-1)+

…+N(G-V(OVq),k-1)=

qN(Cn+1∪Pn-2∪Cn∪…∪Cn,k-1)

利用引理2和5，有

N(G-V(K1),k-1)+

N(G-V(OV0),k-1)+

N(G-V(OV1),k-1)+

N(G-V(OV2),k-1)+…+

N(G-V(OVq),k-1)=

N(Cn+1∪Cn∪…∪Cn,k-1)+

N(Pn-1∪Cn∪…∪Cn,k-1)+

qN(Cn+1∪Pn-2∪Cn∪…∪Cn,k-1)=

N(Cn,l3)…N(Cn,lq+1))

图1中顶点的个数是(q+1)n+2．根据定理3、引理3和引理4[5-6]，

f(G)=0+2q+q×0=2q．

图1中存在1-因子，且为2q个．

□

例4假设图2被构造如下，其中Pn是长度为n且有n+1个顶点，Pn的个数是q，那么f(G)=0．

图2 棒图Fig.2 Bar graph

证明类比于例3，利用图的分支分析方法，对固定点O进行分析．通过顶点O的所有完全图是K1和q个K2．图2无K3子图．

情况1O作为K1，为一个完全分支，删掉K1，有q个路Pn-1，并且两两不相交，于是

N(G-V(K1),k-1)=N(Pn-1∪Pn-1∪…∪

Pn-1,k-1)

情况2O含于K2，作为一个完全分支，删掉K2，有一个路Pn-2和q-1个路Pn-1，因为q个完全图K2是对称的，于是

qN(G-V(K2),k-1)=qN(Pn-2∪Pn-1∪…∪

Pn-1,k-1)

综上所述，根据引理2和5，得到

N(G-V(K1),k-1)+

qN(G-V(K2),k-1)=

N(Pn-1∪Pn-1∪…∪Pn-1,k-1)+

qN(Pn-2∪Pn-1∪…∪Pn-1,k-1)=

N(Pn-1,lq)+

图2中顶点的个数是qn+1，由于图2无K3子图，根据定理3和引理3，有

当q或n是偶数时，qn+1是奇数，在图2中，f(G)=0．

当q和n都是奇数时，qn+1是偶数，在图2中，f(G)=0+q×0=0[7]．

在图2中，对任意q和n，不存在1-因子．

□

注构造这两类图，1-因子可能无限或为零．

定理6对任意自然数N，存在连通图使得它的1-因子个数大于自然数N．

证明构造一个图，如例3的图1，根据例3的结果，该图的1-因子个数f(G)=2q．

□

3 结 语

1-因子或完美匹配的计数是十分困难和有价值的问题．本文利用S(n)-因子计数理论和组合数学方法研究了无K3子图的图中的1-因子计数，取得了一定的进展，对于组合学和图论具有一定参考价值．