﻿ 2类特殊图中的完美匹配数
 文章快速检索 高级检索
 浙江大学学报(理学版)  2017, Vol. 44 Issue (3): 266-269  DOI:10.3785/j.issn.1008-9497.2017.03.003 0

### 引用本文 [复制中英文]

[复制中文]
TANG Baoxiang, REN Han. The number of perfect matchings in two types of particular graphs[J]. Journal of Zhejiang University(Science Edition), 2017, 44(3): 266-269. DOI: 10.3785/j.issn.1008-9497.2017.03.003.
[复制英文]

### 文章历史

2类特殊图中的完美匹配数

1. 天水师范学院 数学与统计学院, 甘肃 天水 741001;
2. 华东师范大学 数学系, 上海 200062

The number of perfect matchings in two types of particular graphs
TANG Baoxiang1 , REN Han2
1. School of Mathematics and Statistics, Tianshui Normal University, Tianshui 741001, Gansu Province, China;
2. Department of Mathematics, East China Normal University, Shanghai 200062, China
Abstract: Perfect matching counting problems for graphs have been proven to be NP-hard, so it is very difficult to get the number of perfectly matched general graph. The counting formula of the perfect matching for graphs 4-1-nC10and 2-nT2 was made by applying partition, summation and re-recursion. The number of all perfect matchings of many graphs can be calculated by the method presented in this paper. The given method is also able to implement the possibility to obtain the number of all perfect matchings with perfect matching graphs.
Key words: partition    recurrence relation    perfect matching
0 引言

n个长为10的圈记为

 ${C^i} = {u_{i1}}{u_{i2}}{u_{i3}}{v_{i2}}{w_{i3}}{w_{i2}}{w_{i1}}{w_{i4}}{v_{i1}}{u_{i4}}\left( {i = 1, 2, ..., n} \right).$

 图 1 4-1-nC10图 Fig. 1 Graph of 4-1-nC10

n个长为2的梯子T2i, 其顶点集为V(T2i)=ui1, ui2, ui3, vi1, vi2, vi3(i=1, 2, …, n).连接梯子T2iT2i+1的顶点vi1ui+1, 1vi3ui+1, 3(i=1, 2, …, n-1)，再连接梯子T21的顶点u11u13T2n的顶点vn1vn3，得到的图记为2-nT2, 如图 2所示.

 图 2 2-nT2图 Fig. 2 Graph of 2-nT2
1 结果及其证明

 $f\left( n \right) = {2^{n-2}} \cdot {\left( {2 + \sqrt 2 } \right)^{n + 1}} + {2^{n-2}} \cdot {\left( {2-\sqrt 2 } \right)^{n + 1}} + 1.$

 图 3 G1图 Fig. 3 Graph of G1
 图 4 G2图 Fig. 4 Graph of G2
 图 5 G3图 Fig. 5 Graph of G3

G1, G2, G3图的完美匹配数分别为a(n), b(n), c(n), 则a(n)=b(n).

G1图的完美匹配按饱和顶点u1可划分为以下6种情形:

 $a\left( n \right) = 4a\left( {n-1} \right) + 2c\left( {n-1} \right).$ (1)

G3图的完美匹配按饱和顶点u1可分以下8种情形求得：

 $c\left( n \right) = 4a\left( {n-1} \right) + 4c\left( {n-1} \right).$ (2)

4-1-nC10图的完美匹配按饱和顶点u11可分以下5种情形求得:

 $f\left( n \right) = 2a\left( {n-1} \right) + 2c\left( {n-1} \right) + 1.$ (3)

 $f\left( n \right) = 16a\left( {n-2} \right) + 12c\left( {n-2} \right) + 1,$ (4)

 $f\left( {n-1} \right) = 2a\left( {n-2} \right) + 2c\left( {n-2} \right) + 1,$ (5)

 $f\left( n \right) = 8f\left( {n-1} \right)-4c\left( {n-2} \right) - 7.$ (6)

 $c\left( n \right) = 2f\left( n \right)-2,$ (7)

 $f\left( n \right) = 8f\left( {n-1} \right)-8f\left( {n-2} \right) + 1.$ (8)

 $f\left( n \right) = {c_1}{\left( {4 + 2\sqrt 2 } \right)^n} + {c_2}{\left( {4-2\sqrt 2 } \right)^n}.$ (9)

f(2)=2a(1)+2c(1)+1.

 图 6 图 4-1-1×C10的所有完美对集 Fig. 6 All perfect matchings of 4-1-1×C10 graph

 图 7 G4图 Fig. 7 Graph of G4

 图 8 G5图 Fig. 8 Graph of G5

f(2)=2×8+2×12+1=41.

 $f\left( n \right) = {2^{n-2}} \cdot {\left( {2 + \sqrt 2 } \right)^{n + 1}} + {2^{n-2}} \cdot {\left( {2-\sqrt 2 } \right)^{n + 1}} + 1.$

 图 9 G6图 Fig. 9 Graph of G6

 $d\left( 1 \right) = 3, 所以d\left( n \right) = {3^n}.$ (10)

2-nT2图的完美匹配按饱和顶点u11可分以下4种情形求得:

 $g\left( n \right) = 3d\left( {n-1} \right) + 1.$ (11)

 [1] LOVÁSZ L, PLUMMER M. Matching Theory[M]. New York: North-Holland Press, 1986. [2] KRÁL D, SERENI J S, STIEBITZ M. A new lower bound on the number of perfect matchings in cubic graphs[J]. Discrete Math, 2009, 23: 1465–1483. [3] KARDOS F, KRÁL D, MISKUF J, et al. Fullerene graphs have exponentially many perfect matchings[J]. Journal of Mathematical Chemistry, 2009, 46: 443–447. DOI:10.1007/s10910-008-9471-7 [4] 唐保祥, 任韩. 几类图完美匹配的数目[J]. 南京师大学报:自然科学版, 2010, 33(3): 1–6. TANG B X, REN H. The number of perfect matching for three specific types of graphs[J]. Journal of Nanjing Normal University: Natural Science Edition, 2010, 33(3): 1–6. [5] 唐保祥, 李刚, 任韩. 3类图完美匹配的数目[J]. 浙江大学学报:理学版, 2011, 38(4): 387–390. TANG B X, LI G, REN H. The number of perfect matching for three specific types of graphs[J]. Journal of Zhejiang University: Science Edition, 2011, 38(4): 387–390. [6] 唐保祥, 任韩. 3类特殊图完美对集数的计算[J]. 南开大学学报:自然科学版, 2014, 47(5): 11–16. TANG B X, REN H. The enumeration of perfect matchings in three types of special graphs[J]. Acta Scientiarum Naturalium Universitatis Nankaiensis, 2014, 47(5): 11–16. [7] 唐保祥, 任韩. 4类图完美匹配数目的递推求法[J]. 数学杂志, 2015, 353(2): 626–634. TANG B X, REN H. Recursive method for finding the number of perfect matchings of the four types of graphs[J]. Journal of Mathematics, 2015, 353(2): 626–634. [8] 唐保祥, 任韩. 4类图完美匹配的计数[J]. 武汉大学学报:理学版, 2011, 58(5): 441–446. TANG B X, REN H. The number of perfect matchings in four types of graphs[J]. Journal of Wuhan University: Natural Science Edition, 2011, 58(5): 441–446. [9] 唐保祥, 任韩. 5类图完美匹配的计数[J]. 中山大学学报:自然科学版, 2012, 51(4): 31–37. TANG B X, REN H. The number of perfect matchings in five types of graphs[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2012, 51(4): 31–37.