带端点约束支撑树的全部解

All Solutions of Spanning Trees with Constraint of End-Vertices

自从Ｇ．Ｋｉｒｃｈｈｏｆｆ把支撑树应用于电网络分析之后，支撑树全部解的性质得到广泛的研究．然而，在实际网络分析中往往需要求出网络的具有某种特征的全部支撑树．本文以集合乘积图Ｇ购工具研究了带端．点约束支撑树全部解的性质及其算法．

As we know, all solutions of spanning trees of a network are of important significance in computer network analysis. However, many problems in practice frequcntly require finding a class of spanning trees satisfying.ccrtain conditions.In this paper, we study spanning trees with constraint of end-vcrtices by introducing set eroduct graphs G in which the Descartes product is the vertex set of G and any two vertices α. are adjacent if and only if 2.The main results of this paper are as follows:1) It is proved that G is an edge-Hamilton graph. As an immediate conscqpence of thit resuly we show that the tree graph J((s)(G) composed of all spanning trees with constraint of end-vertices is also an edge-Hamilton graph; thus Cummins work[1] is extended.2) According to the propertics of G an algorithm producing all spanning trees subject to end-venices is presented.