广东工业大学学报 ›› 2006, Vol. 23 ›› Issue (1): 134-138.

• 综合研究 • 上一篇    

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

  

  1. 广东工业大学应用数学学院 广东广州510090；
  • 出版日期:2006-02-02 发布日期:2006-02-02

A Constructing Method for All the Maximal Outerplanar Graphs

  1. (Faculty of Applied Mathematics,Guangdong University of Technology,Guangzhou 510090,China)
  • Online:2006-02-02 Published:2006-02-02

HTML

PDF (PC)

2194

摘要： 提出了一种判定图同构的方法,其原理是赋予每个无标号极大外平面图一个n×(n-3)阶0-1矩阵.证明了矩阵与极大外平面图一一对应,矩阵相同的图彼此同构.构造所有可能的n阶极大外平面图,并用上述方法除去其中同构者,所有n阶无标号极大外平面图都被构造出来了,同时得到其总个数,解决了有关极大外平面图同构与计数问题. 

关键词: 图论； 极大外平面图； 同构； Hamilton圈；

Abstract: 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.

Key words: graph theory； maximal outerplanar graphs； isomorphic graph； Hamilton cycle；

[1] 周建,林翠琴.  n阶极大外平面图的构造法[J]. 清华大学学报(自然科学版). 2000(11)

[2] 王绍文.  极大平面图结构研究[J]. 光子学报. 1998(02)

[1] 卢开澄 著.图论及其应用[M]. 清华大学出版社, 1981

[1] Hu Guanzhang.Catalan number and enumeration of maximal outerplanar graphs. Tsinghua Science and Technology . 2000
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2017 《广东工业大学学报》编辑部
地址：广州市东风东路729号广东工业大学 邮编：510090
电话：020-37626653,020-37626139,020-37626396
邮箱：xbzrb@gdut.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发