The Asymptotic Behaviors Of Enumerations For Trees And Their Applications

Tree is a sort of very important graph in graph theory. Until now, it is an activeresearch field. In applications, many problems are related to the trees. As all the othersorts of graphs, we mostly concentrate on the structure properties.Inthisthesis, weshallinvestigatethestructureenumerationproblemsoftreesfromprobabilistic point of view, namely, the asymptotic properties of the enumerations. Let（?）_n be the set of trees with n vertices. Suppose each tree in （?）_nis equally likely. Thus,we can define a probability space and each subset in （?）_nis an event. We take a ran-dom variable X_n（T_n）（or X_n for short） on this space and investigate the correspondingdistribution.Suppose X_n is the number of vertices taking a given degree in the tree. It has beenshown that in the probability space （?）_n, Xnis asymptotically normal with mean～μnand variance～σn. Hence, the number of vertices of a given degree is （μ+o（1））n foralmost all trees.For complicated cases, we define the pattern as a given small tree with specifyingtheinnernodes（degreelargerthanone）andouternodes（degreeofone）. Thenumberofa given pattern in a tree is the number of subtrees such that the degrees of all inner ver-tices match the degrees of corresponding vertices in the tree. Specifically, the numberof a star pattern is the number of vertices of a fixed degree, whose corresponding distri-bution is normal. But for an arbitrary pattern, it has not been shown the correspondingdistribution is asymptotically normal as for a star pattern, even many observations onspecial patterns demonstrated this property. And, for rooted trees, this property alsoholds, if we define the similar probability space on rooted tree set. However, for anypattern in Tn, we only had that the limiting distribution is with density （A₀+B₀t²）e^C0t2,where A₀, B₀,C₀are some constants. The mean and variance of the number of the pat-tern are still linear to n as the case for star pattern. Clearly, if we show B0=0, then thedistribution is normal. But this problem seems to be much difficult.Then, in this thesis, for the double-star pattern, we shall verify the property above through a traditional method, which includes a complex computing process. For furtherstudy, we solved this problem completely with a new idea. We get that for almost everytree, the number of corresponding rooted trees is （μ（R）+o（1））n. In conjunction withthe normally distributed results for rooted trees, the limiting distribution for any patternis also normal in （?）_nFurthermore, we contribute to another tree set （?）_n^△which denotes the set of treeswith bounded maximum degree. We also explore the properties of patterns. In ad-dition, we turn to the number of a given small tree, namely, the number of the corre-sponding subtrees （the degrees of the corresponding vertices are no longer required tobe matching） in the tree. Actually, when we turn to the number of a given small tree in（?）_n, the problem is much difficult. But in （?）_n, we can also set up similar results as forpatterns.In applications, we use these asymptotic results to estimate the values of somechemical indices, the general Randi index, the general Zagreb index and the Estradaindex, for almost all trees in （?）_n or （?）_n^△. Indeed, we establish the overall propertiesof these indices from the probabilistic point of view, while the former researchers justconsidered the lower and upper bounds or the exact values of some special graphs.The first Chapter is the introduction. We introduce the background and historyon the results for trees and give some notions and notations which will appear in thefollowing chapters. Moreover, we present the principal results of this thesis in this part.The second Chapter is devoted to give some preliminary knowledge including thegenerating function, probability, combinatoricsandthemainlemmasused in thisthesis.In the third Chapter, through a traditional method in [1], we show for a double-star pattern, the occurrence number in （?）_n is asymptotically normally distributed. Then,we apply this result to establish that for almost all trees in （?）_n, the general Ranci indexrestrictingon thepowervariableα≤0satisfies（λ_α ε）n≤R_α（T_n）≤（λ_α+ε）n whereε is any positive number. And we demonstrate that the conjecture: R（G）≥D（G） forany graph G, proposed by Fajtlowicz in [2] holds for almost all trees in （?）_n, whereD（G） denotes the average distance. And analogously, we also give an estimation on thegeneral Zagreb index.In the forth Chapter, we illustrate the limiting distribution is normal in （?）_n for any pattern by formulating the asymptotical number of the associated rooted trees for a tree.In the fifth Chapter, we show the number of a star （a double-star） pattern in （?）_nis also with both mean and variance linear to n. Especially, the distribution for the starpattern is still shown to be asymptotically normal. Then, for the general Zagreb index,wegetDα=（dα（△）+o（1））n a.e., where dα（△） isaconstantin （?）_n^△. AndforthegeneralRandi index, we have Rα=（rα（△）+o（1））n a.e..In the last Chapter, we turn to the number of any given small tree H in （?）_n andobtain that the corresponding distribution is similarly with mean （μH+o（1））n and vari-ance （σ_H^t+o（1））n. As an application, we provide an estimate on the Estrada index that（μ_△-ε）n <EE（（?）_n^△）<（μ_△+ε）n for almost all trees in （?）_n^△. And we illustrate thatEE（（?）_n^△）≈aD2+b a.e., where a, b are some constants.