超方体Qn的路分解及其算法

计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (6): 64-68.

超方体Qn的路分解及其算法

程芳，叶永升，高洁，史彩霞

淮北师范大学数学科学学院，安徽淮北 235000

出版日期:2015-03-15 发布日期:2015-03-13

Path decomposition of hypercube Qn and its algorithm

CHENG Fang, YE Yongsheng, GAO Jie, SHI Caixia

School of Mathematical Sciences, Huaibei Normal University, Huaibei, Anhui 235000, China

Online:2015-03-15 Published:2015-03-13

摘要/Abstract

摘要： 在超方体[Qn]的路分解的研究中，证明了[Qn]存在[{Pn+1}]-分解的定理；分别给出了[Qn]存在[{P4}]-分解的充分必要条件和存在[{P3,P4}]-分解的充分条件；结合超方体的性质和路分解结论，设计出超方体的路分解算法程序。

关键词: 超方体[Qn], 路分解, 1-因子

Abstract: In the study on path decomposition of the hypercube [Qn], it is proved that a [{Pn+1}]-decomposition exists. This paper gives a sufficient and necessary condition of [{P4}]-decomposition and a sufficient condition of [{P3,P4}]-decomposition for hypercube respectively. By properties of hypercube and path decomposition conclusions, its path decomposition algorithm is proposed.

Key words: hypercube [Qn], path decomposition, 1-factor

程芳，叶永升，高洁，史彩霞. 超方体Qn的路分解及其算法[J]. 计算机工程与应用, 2015, 51(6): 64-68.

CHENG Fang, YE Yongsheng, GAO Jie, SHI Caixia. Path decomposition of hypercube Qn and its algorithm[J]. Computer Engineering and Applications, 2015, 51(6): 64-68.