论文部分内容阅读
图论是数学的一个分支，特别是离散数学的一个重要的分支，它在物理、化学、天文、地理、生物学，尤其是计算机科学中有广泛的应用.图的标号问题是图论中极有趣的研究课题之一，有着较好的研究价值和广阔的应用前景. 论文主要对图的标号问题进行研究.利用计算机求解并结合数学证明的方法对有向图优美性和广义Petersen图P（n,k）的(a，d)-反边幻标号问题，具体工作如下: 1991年马克杰教授提出的猜想:当mn≡0(mod2)有向图m(C)n是优美图，论文证明了对任意的n≥3，有向图4(C)n是优美图. 2000年，Mirka Miller和Martin Baca提出的猜想;当n≡0(mod2),n≥6，2≤k≤n/2-1时，广义Petersen图P（n，k）有(3n+6/2，3）-反边幻标号;论文证明了广义Petersen图P（n，7），当n≥16时，有（3n+6/2，3）-反边幻标号，用这种方法陆续找到对于偶数n≥2k+2，广义Petersen图P(n，9)，P（n，11），P（n，13），P（n，15）有（3n+6/2，3）-反边幻标号.并通过计算机大量计算搜索证明了当3≤k≤n/2-1时，Mirka Miller和Martin Baca提出的猜想:广义Petersen图P（n，k）有(3n+6/2,3)-反边幻标号成立，其中n为偶数.