Popov V.V. On Algorithm of Numbering the Spanning Trees in a Connected Graph

Details

Hits: 809

Abstract. Let G = (V,E) be a finite connected graph without multiple edges or loops. We consider the task about the numbering of all the spanning trees of G 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 G. 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 G. Here we concider the method based on lexicographical order on the set of all sequences of edges of G. 

We will remind that a spanning tree T of the graph G is a tree consisting of edges of G and connecting all the vertices of G.

We shall assume that V = {1, 2, . . . , n}, where n is a number of vertices of G. If a, b ∈ V , then (a, b) will be designated the edge with end-points a and b.
Let T be a spanning in G. Then the set of his edges can be written in the form

(a₁, b₁), (a₂, b₂), . . . , (a_n−1, b_n−1), (A)

where a_i < a_i+1 or a_i = a_i+1 and b_i < b_i+1, where i = 1, 2, . . . , n − 2. (B)

On a set of sequences of in the form of (A) with the additional condition (B) we will consider a lexicographic order. The smallest (with respect to this order) spanning tree will be the tree T0 with edges (1, 2), (1, 3), (1, 4), . . .,(1, m) provided (1, b) ∈ E for b = 2, 3, . . . , n. The greatest spanning tree T₁ will be (1, n), (2, n), (3, n), . . ., (n − 1, n) under a similar condition. Touching all sequences of a look (A) in ascending order between T0 and T1 and checking lack of cycles at the corresponding sets of edges, we will be able to get a list of all spanning trees. We will give results of work of the appropriate computer program. 

Example 1. For complite graph K_n on n vertices for n ≤ 9 the lists of all the spanning trees are obtained. Due to Kely theorem K_n has nⁿ⁻² spanning trees. For n = 9 thos number is equal 4 782 969.
Example 2. Let G be a graph on 12 vertices in figure 1 (in the left). Then G has 2 415 spanning trees.

On Algorithm of Numbering the Spanning Trees in a Connected Graph by Popov V.V. is licensed under a Creative Commons Attribution 4.0 International License.

Attachments:

1_Popov.pdf URL: https://mp.jvolsu.com/index.php/en/component/attachments/download/428

921 Downloads