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

 
 
Popov Vladimir Valеntinovich
 
Candidate of Physical and Mathematical Sciences, Associate Professor, Department of Computer Sciences and Experimental Mathematics, Volgograd State University
This email address is being protected from spambots. You need JavaScript enabled to view it. , This email address is being protected from spambots. You need JavaScript enabled to view it.
Prosp. Universitetsky, 100, 400062 Volgograd, Russian Federation

 

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

(a1, b1), (a2, b2), . . . , (an−1, bn−1), (A)

where ai < ai+1 or ai = ai+1 and bi < bi+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 T1 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 Kn on n vertices for n ≤ 9 the lists of all the spanning trees are obtained. Due to Kely theorem Kn has nn−2 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.

Example 3. Let P be a set of square tops, and also its center. Then there are 45 spanning trees on top of P.
Example 4. Let P consists of square tops, and also middle of its parties. Then there are 3 273 spanning trees on top of P.
 
Key words: connected graph, planar graph, spanning tree, the number of spanning trees, triangulation, the number of triangulations.

Creative Commons License
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.

Citation in EnglishScience Journal of Volgograd State University. Mathematics. Physics. №2 (27) 2015 pp. 6-16 

 

 

 

 

Attachments:
Download this file (1_Popov.pdf) 1_Popov.pdf
URL: https://mp.jvolsu.com/index.php/en/component/attachments/download/428
530 Downloads