论文部分内容阅读
在平面上嵌入一棵树T，T的每个内部顶点的度数至少为3并且T至少有一个内部顶点。作一个圈C连接T的所有叶顶点，T的所有叶顶点组成C上的所有顶点。这样得到的平面图称为Halin图。树T称为Halin图的特征树，圈C称为Halin图的伴随圈。通常用H=7∪C表示一个Halin图。
本文主要研究了Halin图及小树宽图的几个相关算法。论文第一章主要介绍相关概念和术语。对Halin图和小树宽的历史和研究现状做了介绍。第二到四章详细介绍了利用动态规划和压缩扇的方法求解Halin图中的三个问题，并设计了线性时间的算法解决这些问题。第五章研究了小树宽图上的全一问题。
本文主要研究了Halin图中的以下三个算法：
(1)找最大权对集问题是著名的分派问题，并能得到最佳利益。在一个赋权一般图上求解一个最大权完美对集的问题的算法的时间复杂度是O(|V|E|log|V|)。第二章解决了在一个赋权Halin图上，寻找具有最大权的对集和完美对集、几乎完美对集等问题，并给出线性时间的算法。
(2)图G=(V,E)，正整数K≤|V|。G的顶点是否能划分成K个不相交的集合V<,1>，V<,2>…V<,K>，使得对于i∈{1，…，K}，由V<,i>诱导的子图是一个完美对集。这个问题是一个NP完全问题。本文第三章首先证明出在Halin图上2≤K≤4，然后给出相关算法。算法的时间复杂度是0(|V|)。
(3) 一个网络可以表示为无向图G=(V, E，d)其中V是顶点的集合， E是边的集合，d是边的费用函数d：E→R。S是V的子集， 2≤|S|≤|V|。Steiner树问题就是寻找G的一棵子树T<,S>=(V，E，d)，S V V,E’E,并且使花费d(Ts)=∑<,e∈E’>d(e)最小。求Steiner树问题是NP完全问题。本文第四章中把这个问题限制到Halin图上，并给出线性时间算法。
Halin图实际上是一种树宽≤3的图。树宽是一种测量图与树的相似度的参数。许多图都有常数上界的树宽。例如，树和森林的树宽≤1，系列平行图和外平面图的树宽≤2，Halin图的树宽≤3。最后我们把Halin图扩展到小树宽(≤4)的图上，进行最小全一问题的求解。
全一问题可以如下描述：假定一个n×n的棋盘的每个方格内安装有一个电灯和一个按钮。按下某个方格内的按钮，将使这个方格内的电灯由亮变灭或者由灭变亮，而且会使与这个方格有边相邻的方格内的电灯也同样改变。
如果初始状态所有电灯都是灭的，那么是否可以通过按下一组按钮，使得最终棋盘上的所有电灯都处于亮的状态?这个问题也被称为全一问题。如何求得一组最少的按钮使得最终所有电灯都处于亮的状态?这个问题被称为最小全一问题。
在一般图中，最小全一问题是NP完全问题，第五章描述在小树宽图上对其进行求解，给出线性时间算法。
在第六章，我们总结了本文研究的几个算法，并提出了我们以后将要进行的工作。