| 辅助图与标号三元图的等价性 |
| |
| 作者姓名： | 魏二玲 |
| |
| 作者单位： | 中国人民大学数学系, 北京 100872 |
| |
| 基金项目： | 国家自然科学基金项目(60373030)资助 |
| |
| 摘 要： | 20世纪 70年代,刘彦佩通过构造图的辅助图,得到判定图是否平面的充分必要条件.图的标号三元图刻画了图的内在结构,也可以刻画图是否平面.证明了图的辅助图是否平衡以及标号三元图是否平衡是等价的 ;并进一步指出,用辅助图来判定要优于用标号三元图.
|
| 关 键 词： | 平面性 辅助图 三元图 |
Equivalence of Auxiliary Graph and Signed Triple Graph |
| |
| Authors: | WEI Er-Ling |
| |
| Institution: | Department of Mathematics, Renmin University of China, Beijing 100872, China |
| |
| Abstract: | In the 1970s, Liu Yan-Pei obtained a sufficient and necessary condition to determine whether a graph isplanar by auxiliary graph.The signed triple graph characterizes the inner construct of a graph.Meanwhile, usingsigned triple graph, one can decide whether a graph is planar or nonplanar.In this paper, the equivalence of auxiliarygraph and signed triple graph is proved.Furthermore, it is pointed out that the method by auxiliary graph is superiorto that by signed triple graph in view of complexity. |
| |
| Keywords: | planarity auxiliary graph triple graph |
|
| 点击此处可从《》浏览原始摘要信息 |
| 点击此处可从《》下载免费的PDF全文 |
|
