本论文研究了图论领域的两个问题及其应用：小树宽图和对集可扩图。 近二十五年来，树宽这一概念在图论算法研究的许多方面起到了重要的作用。小树宽图在众多领域都有应用。许多通信网络的拓扑结构都是小树宽图。在化学领域，对LIGAND数据库里面9712种化合物计算树宽后发现：除一个外，其余物质结构图的树宽都不大于3；例外物质的树宽为4。使用常用编程语言(例如C语言)编写的不含goto语句的程序，其控制流图的树宽以一个小常数为上界。 Halin图的树宽不大于3。由于Halin图是对环形和树形网络一种非平凡的概括，本文研究了Halin图中与网络路由相关的几个问题。 第二章解决了Halin图中费用最优的Hamilton路的问题。Hamilton路问题有三个版本：不指定端点、指定一个端点和指定两个端点。论文给出了求解三个版本最优Hamilton路的线性时间算法。 第三章探讨了Halin图中圈覆盖问题。一个图的圈覆盖是一组圈使得图中所有的选定顶点至少在这组圈的一个圈中。圈覆盖问题起源于环形光纤通信网络的设计：采用一系列的圈去覆盖要传输数据的子网络。除了两个版本的最优圈覆盖问题以外，本文还解决了用一个费用最优的2-边连通子图去覆盖给定顶点集的问题。针对本章的三个问题，论文都给出了线性时间的算法。 第四章研究了并行计算环境中树分解的根选取问题。树分解是图论中最重要的几个分解之一。在小树宽图上求解问题，第一步就是求解给定图的树分解。并行计算树分解的一个先决条件就是为树分解选定一个根。并且根的选择会影响处理时间。论文给出了求解使完成时间最早的根的算法，算法的时间复杂度为O(d|V(T)|)，其中d是树T中最长路的长度。第五章给出了判定1-可扩图的算法。最坏情况下，算法是O(|V||E|)时间的。该算法的复杂度与目前最快的由Carvalho和Cheriyan提出的算法是一样的。但是本文的算法要比后者简单很多。此外，论文给出了算法实现的细节。 第六章研究了(n，K,d)-偶图。论文给出了求解使得给定图为(n，K0，0)-偶图的最大正整数K0的算法。算法的时间复杂度为O(|V||E|)。此问题在设计任务管道和处理机之间的线路有应用：刻划了某些任务要指定处理机，但同时有些处理机不可用的情形。论文给出了有关(n，K,0)-图连通度的结论。此外，论文还给出了判定(0，1，d)-图的算法，其时间复杂度为O(IV||E|)。 第七章解决如何加最少的边把给定偶图扩展为1-可扩偶图的问题。鉴于Gabow和Jordan给出了如何加最少的边把有向偶图扩展为强连通图的算法；并且当给定图的一个完美对集时，1-可扩偶图可以转换为有向强连通偶图。本文主要证明了需要添加的最小边数不依赖于完美对集的选取。 第八章对本文进行了总结，并给出了几个有待进一步研究的问题。