Degree Sequence Of Tree And Hypertree

"Graphic Degree Sequence Problem" is one of the most famous but complex problems in the graph theory. There have been a lot of conclusions about it from the domestic and foreign researchers, but the research involved in "Graphic Tree Degree Sequence Problem "or "Graphic Hypertree Degree Sequence Problem " is actually few. For the linear hypertree in hypergraph, as a result of its own structural particularity, has not obtained its effective algorithm of hang edge number and counting results of the marked special generalized linear hypertree with circle at present. In view of this background, this thesis has done the following works separately in the tree, the narrowed hypertree and the generalized hypertree.Firstly, after analyzing the relations of the tree with the leaves, the thesis introduces necessary and sufficient conditions of the graphic tree degree sequence and a series of inferences by introducing the branch vertices and using constructive proof method. The results are extended to the case of the forest and the arborescence by the similar method. Secondly, according to the extended ideas which frequently used in the hypergraph research, by analyzing the relations of the hypertree with its isolated vertices, the research methods in graphic tree degree sequence of graph theory are applied to the narrowed hypertree and the generalized hypertree. The main method in this thesis is using bipartite graph of hypertree as the research bridge to achieve the goal, the description of the feature structures of the vertices and edges in linear hypertree. In the research of non-linear hypertree, the vertice subdivision of the bipartite graph of the hypergraph is defined, which is based on the idea of edge subdivision in the graph theory. Hence several related theorems about graphic hypertree degree sequence and a series of inferences are proved. By discussing the different definitions in circle structure, the thesis presents some significant propositions about the generalized hypertree and the narrowed hypertree, which further uncover the relationships between linear hypertree and its degree sequence.Then, the thesis considers the special relations between the hang edges and the isolated vertices of the linear hypertree, and presents a feasible effective algorithm for computing hang edge number whose time complexity is just ( ( ))0 E T2. By using theproperties of the linear hypergraph and the generalized hypertree, the author obtains both bounds on the number of marked generalized linear hypertrees with circle, and...