2类图完美匹配计数公式的嵌套递推求法
|
摘要
把图2-nD_8和2-nD_6的完美匹配按饱和某个顶点的完美匹配进行分类,求出每一类完美匹配数目的递推关系式,再利用这些递推式之间的相互关系,得到这两类图的完美匹配数目的递推关系式,最后从递推式中解出这两类图的完美匹配数目的计算公式.
The perfect matching of graphs 2-nD_8 and 2-nD_6 has been classified according to the perfect matching of a certain vertex of saturation, and the recursive relation of each kind of perfect matching number been obtained. Then the interrelationship between these recursive formulas has been used to eliminate those that are not needed. The recursive relation has been used to obtain the recursive relation of the perfect matching number of the two kinds of graphs. Finally, the formula for calculating the perfect matching number of the two graphs has been solved from the recursive formula.
The perfect matching of graphs 2-nD_8 and 2-nD_6 has been classified according to the perfect matching of a certain vertex of saturation, and the recursive relation of each kind of perfect matching number been obtained. Then the interrelationship between these recursive formulas has been used to eliminate those that are not needed. The recursive relation has been used to obtain the recursive relation of the perfect matching number of the two kinds of graphs. Finally, the formula for calculating the perfect matching number of the two graphs has been solved from the recursive formula.
引文
[1] Valiant L G.The Complexity of Computing the Permanent [J].Theoretical Compute Science,1979,8(2):189-201.
[2] LOVáSZ L,PLUMMER M.Matching Theory [M].New York :North-Holland Press,1986.
[3] ZHANG H P.The Connectivity of Z-Transformation Graphs of Perfect Matchings of Polyominoes [J].Discrete Mathematics,1996,158(1-3):257-272.
[4] YAN W G,ZHANG F J.Enumeration of Perfect Matchings of a Type of Cartesian Products of Graphs [J].Discrete Applied Mathematics,2006,154(1):145-157.
[5] LI S L,YAN W G.The Matching Energy of Graphs with Given Parameters [J].Discrete Applied Mathematics,2014,162:415-420.
[6] DONG F M,YAN W G,ZHANG F J.On the Number of Perfect Matchings of Line Graphs [J].Discrete Applied Mathematics,2013,161(6):794-801.
[7] CHANG A,SHIU W C.On the kth Eigenvalues of Trees with Perfect Matchings [J].Discrete Mathematics and Theoretical Computer Science,2007,9(1):321-332
[8] 唐保祥,任韩.2类偶图完美匹配的数目 [J].西南大学学报(自然科学版),2012,34(10):91-95.
[9] 唐保祥,任韩.3类特殊图完美对集数的计算 [J].南开大学学报(自然科学版),2014,47(5):11-16.
[10] 唐保祥,任韩.4类图完美匹配的计数 [J].武汉大学学报(理学版),2012,58(5):441-446.
[11] 唐保祥,任韩.几类特殊图完美匹配数目的递推求法 [J].西南师范大学学报(自然科学版),2014,39(2):9-13.
[12] 唐保祥,任韩.两类图完美匹配的计数公式 [J].吉林大学学报(理学版),2016,54(4):790-792 .
[13] 唐保祥,任韩.2类图完美匹配数目的解析式 [J].中山大学学报(自然科学版),2016,55(4):15-17.
[14] 唐保祥,任韩.2类特殊图中的完美匹配数 [J].浙江大学学报(理学版),2017,44(3):266-269.
[15] 黄丽娜,李沐春,刘海忠.图的邻点可区别V-全色数的一个上界 [J].西南大学学报(自然科学版),2017,39(12):81-85.
[16] 王文霞.无向无权图同构判别算法 [J].西南师范大学学报(自然科学版),2017,42(3):141-145.
[2] LOVáSZ L,PLUMMER M.Matching Theory [M].New York :North-Holland Press,1986.
[3] ZHANG H P.The Connectivity of Z-Transformation Graphs of Perfect Matchings of Polyominoes [J].Discrete Mathematics,1996,158(1-3):257-272.
[4] YAN W G,ZHANG F J.Enumeration of Perfect Matchings of a Type of Cartesian Products of Graphs [J].Discrete Applied Mathematics,2006,154(1):145-157.
[5] LI S L,YAN W G.The Matching Energy of Graphs with Given Parameters [J].Discrete Applied Mathematics,2014,162:415-420.
[6] DONG F M,YAN W G,ZHANG F J.On the Number of Perfect Matchings of Line Graphs [J].Discrete Applied Mathematics,2013,161(6):794-801.
[7] CHANG A,SHIU W C.On the kth Eigenvalues of Trees with Perfect Matchings [J].Discrete Mathematics and Theoretical Computer Science,2007,9(1):321-332
[8] 唐保祥,任韩.2类偶图完美匹配的数目 [J].西南大学学报(自然科学版),2012,34(10):91-95.
[9] 唐保祥,任韩.3类特殊图完美对集数的计算 [J].南开大学学报(自然科学版),2014,47(5):11-16.
[10] 唐保祥,任韩.4类图完美匹配的计数 [J].武汉大学学报(理学版),2012,58(5):441-446.
[11] 唐保祥,任韩.几类特殊图完美匹配数目的递推求法 [J].西南师范大学学报(自然科学版),2014,39(2):9-13.
[12] 唐保祥,任韩.两类图完美匹配的计数公式 [J].吉林大学学报(理学版),2016,54(4):790-792 .
[13] 唐保祥,任韩.2类图完美匹配数目的解析式 [J].中山大学学报(自然科学版),2016,55(4):15-17.
[14] 唐保祥,任韩.2类特殊图中的完美匹配数 [J].浙江大学学报(理学版),2017,44(3):266-269.
[15] 黄丽娜,李沐春,刘海忠.图的邻点可区别V-全色数的一个上界 [J].西南大学学报(自然科学版),2017,39(12):81-85.
[16] 王文霞.无向无权图同构判别算法 [J].西南师范大学学报(自然科学版),2017,42(3):141-145.