The Application Of Tree Theory In Group Testing Problem

So far, group testing problem has been 60 years. It started as an idea to do large scale blood testing in World War II. Group testing has associated with many problems of computer science, such as complexity theory, learning models, etc. It is also used in multi-access communication, coding and so on. Recently it's also used in the cloning library screening.Graph theory is a new branch of mathematics, which has strong applications in different areas. Recently, the graph theory has been developing rapidly, and its application range becomes wide, which has now penetrated into logic, computer science and other branches of mathematics. The proof of group testing problem using the tree in graph theory can be simplified a lot. The main work of this paper is as follows.First, we will introduced the origin of the group testing and contents of group testing problem, including how to set up a testing model based on a practical problem, the classification of group testing problem and some related definitions and restrictions. Our purpose is that we can understand more of group testing problem, in order to achieve some the further study of group testing problems.Second, we will introduce the relationship among graph, tree and group testing, including the group testing on graph, the defective vertex, and group testing on tree graph. Especially, we will introduce the relation between the theory of the tree and group testing, and how to apply the tree theory to solve the problemof group testing. Also the relation between the number of tree leaf nodes and the lower bound of group testing theory.Third, we introduce the application of tree theory in a sequence algorithm for group testing, and the details of another special problem - counterfeit coins problem, and some conclusions of this problem.Fourth, respectively, we will use the tree theory to solve two types of group testing problem. The first is named four counterfeit coins problem, in this part we will decide the arrangement of the test by the number of the tree's leaf notes, and show the specific process of testing on the graph. The second category is based on S-stage algorithm and the counterfeit coins problem, in this part, we propose a new class of counterfeit coins problem, and draw some relevant conclusions and some constructive ideas.Above all, the tree theory has played an important role in solving the problem of group testing, which not only helps to determine the test methods, but also facilitates to prove group testing conjecture or theorem.