关于图的单圈划分  

Unicycle Partition of A Graph

作　　者：傅超[1] 刘彦佩[1] 

机构地区：[1]北方交通大学理学院,北京100044

出　　处：《北方交通大学学报》2001年第3期19-23,共5页Journal of Northern Jiaotong University

摘　　要：图的划分问题曾引起图论界的广泛关注 ,本文讨论了一般的单圈划分问题 ,利用禁用构形刻划了一个图存在单圈划分的条件 ,并进一步得到一个算法 ,有效地解决了判定一个图是否存在单圈划分 ,若存在则求其单圈划分的问题 .The problem of partitioning a graph has been long concerned. We discuss the general unicycle partition problem in this paper. By way of forbidden configurations, it is characterized when a graph has a unicycle partition. Furthermore, an efficient algorithm is reached to decide whether a unicycle partition of a graph exists or not, and if it exists, we can get it.

关 键 词：单圈划分 二入定向 禁用构形 图论 连通分支 单圈图 可拓路算法 

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