The Origin And Development Of Theory Of Graphical Enumeration

In recent years, Graph Theory as a new subject is developing rapidly and it has been applied in many fields. Subsequently determining the number of some kind of graphs hasgrown into an independent research field of Graph Theory-----the theory of graphicalenumeration, in which the core is Polya's Enumeration Theory. This theory combined the generating functions and groups effectively (the former is an ordinary tool in combinatorial enumeration and the latter is the most vital algebraic structure in mathematics), applied permutation groups to enumerate various graphs skillfully, and laid the foundation of the theory of graphical enumeration. Polya's Enumeration Theory has become a powerful technique in the theory of graphical enumeration, even in Combinatorial Mathematics.According to the chronological order and centering on the Polya's Enumeration Theory,the present paper begins with an early enumeration problem------the enumeration of trees,explores gradually the formative process of Polya's Enumeration Theory and the generalization of the enumeration theory by Harary, tries to analyze comprehensively and study systematically the origin and development of the theory of graph enumeration through the literature analysis and comparison. The main results are as follows:1. This dissertation reviews the background of the appearance and early development of the enumeration of trees, analyzes the relation among the enumeration of trees, mathematics and chemistry, reveals that graphical enumeration is significant in reality, and illustrates the initiating achievement made by A. Cayley and C. Jordan in the enumeration of trees.2. This dissertation analyzes the formative process of Polya's Enumeration Theory and its applications to graphical enumeration. Through giving a detailed discuss of the research before Polya's Enumeration Theory and investigating the profound idea contained in Polya's classical paper, the dissertation shows that Polya's Theorem is a perfect production gained by the penetration and intersection between Algebra and Graph Theory, and reveals that systematic theories and unified methods are the key to solving problems.3. This dissertation exhibits the great contributions and influences made by John Howard Redfield—who was forgotten for a long time—to graphical enumeration. Redfield's paper was unnoticed for a long time. Fortunately, Harary found its great value after several decades the paper was published. This dissertation tried to discuss Redfield's life and legacy in detail.4. This dissertation investigates the further developments of graphical enumeration after Polya's Enumeration Theory, examines the work of several main mathematicians in this field, analyzes the relations among their idea, and expounds de Bruijn's Theorem, Read's Superposition Theorem, Harary and Palmer's Power Group Enumeration Theorem, Robinson's Composition Theorem and their applications.5. On the basis of investigating Graphical Enumeration thoroughly, this dissertation summarizes generally and comments impersonally on this book, shows several traits of the book and its impacts on the theory of graphical enumeration. In addition, this dissertation gives a brief biography of Harary who is one of the authors. Graphical Enumeration summed up completely all of the scattered results and methods in the filed of graphical enumeration for the first time. And it is the first authoritative and comprehensive book on the theory of graphical enumeration.