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

The Optimization of k-Unicyclicly Partitioning a Graph

图的划分问题曾引起图论界的广泛关注.在文献[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.