摘要
20世纪 70年代 ,刘彦佩通过构造图的辅助图 ,得到判定图是否平面的充分必要条件 .图的标号三元图刻画了图的内在结构 ,也可以刻画图是否平面 .证明了图的辅助图是否平衡以及标号三元图是否平衡是等价的 ;并进一步指出 ,用辅助图来判定要优于用标号三元图 .
In the 1970s, Liu Yan-Pei obtained a sufficient and necessary condition to determine whether a graph is planar by auxiliary graph. The signed triple graph characterizes the inner construct of a graph. Meanwhile, using signed triple graph,one can decide whether a graph is planar or nonplanar. In this paper, the equivalence of auxiliary graph and signed triple graph is proved.Furthermore, it is pointed out that the method by auxiliary graph is superior to that by signed triple graph in view of complexity.
出处
《中国科学院研究生院学报》
CAS
CSCD
2004年第4期451-453,共3页
Journal of the Graduate School of the Chinese Academy of Sciences
基金
国家自然科学基金项目 ( 60 3 73 0 3 0 )资助
关键词
平面性
辅助图
三元图
planarity, auxiliary graph, triple graph
