图的优美性是图的一个重要性质,有着广泛的应用.优美图是图论中极有趣的研究课题之一.马克杰和冯成进已经证明了:所有的齿轮图都是优美图.研究图的优美性其实就是寻找图的优美标号.已经证明判定任意一个图是否为优美图是一个NP-困难问题,即对于给定的一个图,判定它是否为优美图,不存在一个有效算法.在论文中,我们利用构造的方法,具体找出任一齿轮图的冠的一个优美标号,从而证明了所有齿轮图的冠是优美图.
科研之友
微信
新浪微博
Facebook
分享链接
