Enumeration Of Spanning Trees And Calculations On Many Kinds Of Deterministic Networks

As an important topological attribute,spanning tree is an intersection point among of graph theory,combinatorial mathematics and linear algebra.It is related to other dynamics.Deterministic networks are important,and closely related to applications.Since deterministic networks are formed by deterministic ways,its advantage is to obtain some analytical expressions of topology and dynamics.Presently enumeration of spanning trees has gained increasing attention and there are a lot of computational methods.Apart from the matrix-tree theorem(complexity is high with increasing of network order),each method has its own advantages and disadvantages.This dissertation chooses two family of deterministic networks as network models,using the electrically equivalent transformations and product of nonzero eigenvalues of Laplacian matrix to calculate their enumeration of spanning trees and investigate other topological properties on the entropy of spanning trees.Our works are as follows:In chapter 1,it introduces the background of complex networks and gives a detailed contents for deterministic networks,fractal networks and enumeration of spanning trees.In chapter 2,a class of deterministic fractal network model are presented,its spanning trees is calculated by the electrical equivalent transformations.By the electrical equivalent transformations,we obtain the rules of weighted generating function,then we derive the analytical expressions for enumeration of spanning trees.The correctness of the analytical solutions was verified by the matrix tree theorem.At last,the model of fractal network is expanded.For controlling the scale of the network,the network parameters are introduced.The expression of spanning trees enumeration,network parameters and iteration steps are analyzed,and the entropy of the spanning trees of the network is also calculated.Results show that its entropy equal to zero,means that these network structures are more regular.In chapter 3,we choose a kind of generalized Peterson network as the research object to calculate its spanning trees numbers.Using the self-similarity of the network,the relationship between the Laplacian matrix and initial state Laplacian matrix can be obtained and we can obtain the product of its non-zero eigenvalues and the analytical expression of spanning trees by calculating.Finally,the average degree of the prisms,the prism network and the entropy of the spanning trees are respectively calculated,and the changes of the entropy of the spanning trees under the same average degree of the network are compared.It is found that the entropy of the spanning trees of the prisms is the largest and the structural stability is poor.In chapter 4,it summarizes the conclusions and gives further steps in the future.