Об алгоритме перечисления остовов связного графа

On algorithm of numbering the spanning trees in a connected graph

Let ?? = (??,??) be a finite connected graph without multiple edges or loops. We consider the task about the numbering of all the spanning trees of ??. In [2, p. 180, p. 191] described a method of solution of this task, based on the properties of minors of an incidence matrix of ??. In the same place (p. 191-193) gave algorithm of four Japanese mathematicians (Kasahara Y., Tezuka K., Ling Shun Tong, Kitahashi T., [6]), reduced the task to removal of brackets in the product of formal sums of edges of ??. Here we concider the method based on lexicographical order on the set of all sequences of edges of ??. We will remind that a spanning tree ?? of the graph ?? is a tree consisting of edges of ?? and connecting all the vertices of ??. We shall assume that ?? = {1, 2,..., ??}, where ?? is a number of vertices of ??. If ??, ?? ? ??, then (??, ??) will be designated the edge with end-points ?? and ??. Let ?? be a spanning in ??. Then the set of his edges can be written in the form (??1, ??1), (??2, ??2),..., (?????1, ?????1), (??) where ????