一种极大外平面图的构造法  

A Constructing Method for All the Maximal Outerplanar Graphs

作　　者：陈学松[1] 

机构地区：[1]广东工业大学应用数学学院,广东广州510090

出　　处：《广东工业大学学报》2006年第1期134-138,共5页Journal of Guangdong University of Technology

摘　　要：提出了一种判定图同构的方法,其原理是赋予每个无标号极大外平面图一个n×(n-3)阶0-1矩阵.证明了矩阵与极大外平面图一一对应,矩阵相同的图彼此同构.构造所有可能的n阶极大外平面图,并用上述方法除去其中同构者,所有n阶无标号极大外平面图都被构造出来了,同时得到其总个数,解决了有关极大外平面图同构与计数问题.Here a method enduing a matrix to each maximal outerplanar graph of order n is proposed to decide whether graphs are isomorphic, and it is proved that the matrix and the maximal outerplanar are one to one. After constructing all the possible maximal outerplanar graphs, the isomorphic ones are deleted and all the maximal outerplanar graphs are got. At the same time, the number of all the maximal outerplanar graphs of order n is obtained. This paper solves the problem how to decide whether graphs are isomorphic and how to compute all the maximal outerplanar graphs.

关 键 词：图论 极大外平面图 同构 HAMILTON圈 

分 类 号：O157.6[理学—数学]