GENERATION OF ALL SPANNING TREES A COMBINATORIAL APPROACH

[摘要] This paper deals with all spanning tree generation of a simple, symmetric and connected graph. Since, number of spanning trees of a graph is asymptotically exponential it is our endeavor to generate, all trees in reasonable amount of time and space[1]. The method here is qualitatively and quantitatively better than existing methods. The reason behind the claim is minimum number of duplicate tree comparison and no circuit testing at all for its realization[1,6-11]. We are hopeful that betterment of the algorithm lies in the target of no duplicate tree generation.

[关键词] Spanning Tree;Fundamental Circuit Matrix;Degree of Freedom;Transition Vector;Gray Code.