Division Of Small-diameter Diagram And Coverage Issues,

A network topology structure can be indicated by a graph.We can study structures of networks by studying properties of graphs.The theory of studying properties of graphs is graph theory.Graph theory has wide applications in many fields of computer sicence, such as switch theory and logic design,data structure,form language,operation system, principles of compiling,information organization and retrieval etc.Matching theory is one of the important parts of graph theory.As an important branches of matching theory,induced matching theory also has very important applications in the field of computer science.For instance,consider a bipartite graph G=(U,V,E),where edges represent communication capabilities between broadcaster nodes in U and receivers nodes in V.We select k edges e_i(i=1,2,...,k)such that messages on channel i will be passed from broadcaster U(e_i)to receiver V(e_i).If the k edges just form an induced matching of graph G,then the messages on the k channels cannot be revealed or disturbed each other during the course of transmission.The thesis mainly investgates the computational complexity of induced matching partition problems and induced matching cover problems of induced matchings.We also do some work on the computational complexity of induced forest cover problems.Cameron and Faudree did some research on the basic properties and existence conditions of induced matchings in 1989.Induce matching k-partition problem was first studied as a combinatorial optimization problem.Yuan,Wang and Yang did some work on this problem and got some valuable results.Induced matching k-cover problem was presented by Dong and Yuan in 2006.There are no many results on the above problems at present.Some results on induced matching k-partition problem have been obtained by investigators.While there are few results on induced matching forest problem.In the thesis,we prove that induced mathing 2-partition problem and induced matching 2-cover problem of graphs with diameter 5,induced mathing 3-partition problem and induced matching 3-cover problem of graphs with diameter 3 and 4 and induced forest 2-cover problem of graphs with diameter 2 are all NP-complete.The thesis is divided into five chapters.In chapter 1,we give the basic terminology, the history and the advances of the matching theory,the work we do and the structure of the thesis.In chapter 2,we discuss the complexity of induced matching partition problem of grahs with small diameter,and prove that induced matching 2-partition problem of graphs with diameter 5,induced matching 3-partition problem of graphs with diameter 4 and induced matching 3-partition problem of graphs with diameter 3 are all NP-complete. In chapter 3,we discuss the complexity of induced matching cover problem of grahs with small diameter,and show that induced matching 2-cover problem of graphs with diameter 5, induced matching 3-cover problem of graphs with diameter 4 and induced matching 3-cover problem of graphs with diameter 3 are all NP-complete.In chapter 4,the complexity of induced forest cover problem of grahs with diameter 2 is discussed.We prove that induced forest 2-cover problem of graphs with diameter 2 is NP-complete.In chapter 5,we propose some prolbems to be considered in the future.