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

Path decomposition of hypercube Q_n and its algorithm

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

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.