Q^n方体中最大导出环问题的算法

An Algorithm for the Problem of the Largest Induced Cy cle in Q^n

研究了求 n方体 Qn中最大导出环 Sn的算法问题 .目前只知道 |S2 |=4,|S3 |=6,|S4 |=8,|S5|=14 ,|S6|=2 6,这些结果的获得全部是采用数学推理证明形式 .从给出优化的计算机回溯算法角度 ,通过计算机运行 ,来解决求Qn中最大导出环问题 .利用所给出的回溯算法 ,我们得到了 Q7的一个最大导出环为 48.证明了 |S7|≥

Let S n de note the longest induced cycle in Q-n,we know that ｜S 2｜=4,｜ S 3｜=6,｜S 4｜=8,｜S 5｜=14,｜S 6｜=26 .In this paper,a search Backward Algorithm is shown,by which we get one of the longest induced cycle in Q-nwhich is equal to 48 and we also prove that ｜ S 7｜≥48.