Molecular Diagram In Zagreb With The Hosoya Topological Index Inverse Problem And Algorithm Research

Topological indices can reflex chemical and physical properties of molecules statistically. Since different topological indices have different structural interpretations, many kinds of topological indices are invented in chemistry. Combinatorial chemistry is a new powerful technology in the fields of drug design and molecular reconization. It aims at discovery of compounds that have a certain chemical and biological activity. For finding the desired molecules, first, we get the value of the topological indices, a number. Second, we build the database of molecular graphs with the index value. Finally, we choose the wanted molecular graphs, and try to synthesize them. The process is the inverse problem for computing the value of topological indices for a given (known) molecular graph. The inverse problem plays an important role in the field of drug design and molecular systemization.Solving the inverse problem for the Zagreb index and Hosoya index is the main topic of this thesis. We determine those natural numbers for which there are corresponding graphs with the index value equal to them, and those for which there are not any graphs with the index value equal to them. Among the trees, the problem above is also completely solved.Among all the graphs with n vertices or m edges and some special graphs, the graphs that have minimal or maximal value of the topological index are found. We propose some new ideas for finding the graphs, which has minimal or maximal value of the topological index among all the graphs with n vertices and m edges. Solving the problems gives upper and lower bounds for the numbers of vertices and edges, which can be used to improve the efficiency of computer-searching the graphs.A linear-time algorithm for computing the value of Hosoya index for trees is given. Wealso present the problem of given n integers m1,m2,...,mn, are there any trees T rooted atsomewhere such that the set {mv | v∈V(T)} is equal to the given set {mi |i = l,2,...,n} of integers? We show that the problem above is NP-complete.