图的k-单圈划分中的优化问题  

The Optimization of k-Unicyclicly Partitioning a Graph

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

机构地区：[1]北方交通大学应用数学系,北京100044

出　　处：《运筹学学报》2002年第2期79-84,共6页Operations Research Transactions

基　　金：国家自然科学基金资助(批准号:69973001)

摘　　要：图的划分问题曾引起图论界的广泛关注.在文献[4]中讨论了k-单圈划分.本文进一步研究基于k-单圈划分的优化问题,即在一个赋权图中求一个最小权可k-单圈划分的支撑子图,以及对一个不存在k-单圈划分支撑子图的图,如何添最少的边使得它有k-单圈划分的支撑子图.The problem of partitioning a graph has been long concered. In [4], k-unicyclic partition problem is discussed. More generally, we discuss the optimization of k-unicyclic partition in this paper. That is how to get a spanning subgraph which has a k-unicycle partition with minimum weight in a weighted graph, and how to add minimum edges to get a spanning supgraph with k-unicyclic partition in a graph, if the graph doesn't have a spanning subgraph with the partition.

关 键 词：优化问题 k-单圈划分 最小权 最少边 简单图 赋权图 

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