通道布线问题是超大规模集成电路中的一个关键问题。双层通道布线[1,2]的线网结构可以用垂直约束和水平约束进行描述,鉴于该特殊结构,能够将图论的思想运用到双层通道布线中。本文在前人的基础上,对垂直约束图中含有圈的情况进行了讨论,其中在含有一个圈的通道布线问题中,主要利用寻找并消除临界网的方法给出布线的一个新的算法,该算法能够得到轨道的一个下界。在含有多个圈时,主要从结点的两类约束图入手来研究布线算法,通过对垂直约束图中含有有向圈的一类通道布线问题进行研究,设计出包含一对和两对空结点情况下的布线算法,该方法能够得到更好的轨道高度。并且对具体的布线过程进行了详细的描述。Wiener指数[3]也是图论的一个重要的应用,它在理论化学中运用十分广泛。Wiener指数指一个图中所有点对的距离之和,用如下式子表示:(?)Wiener指数主要体现为分子结构的特征,属于拓扑指数。在很多领域都有广泛的应用,诸如物理、化学、生物、通讯等。本文主要在已知一个连通图的顶点数和色数或顶点数和团数情况下,讨论所有点对的距离平方和的上下界问题,即(?)该指数建立在Wiener指数的基础上,对分子结构特征具有一定的研究意义。