组合计数的群论与计算机方法

Group Theory and Computer Methods for Combinatorial Enumerations

本文综述组合数学和图论中解决计数问题的群论与计算机方法及其最新发展．传统的计数方法得到有限的计数公式或递推公式等，然而许多复杂的问题很难得到有限的表达式，即使能得到，公式也往往非常复杂．由于计算机技术的发展不仅使复杂的计数公式有了实际意义，而且可以设计恰当的计算方法进行数值计算，使计数问题有更为广阔的发展领域．另一方面，为了计算不同构的图或组合结构，最有效的方法是群论方法，因此把群论方法与计算机方法结合起来就成了解决计数问题的有效途径．本文着重介绍由作者和Ｒ．Ｃ．Ｒｅａｄ教授提出的压缩图法，采用群论与计算机方法解决计数问题所取得的一些成果。

This paper survey the group theory and computer methods for the enumeration problems in Combinatorics and Graph Theory and its recent developments. Traditional methods for enumerations aim to obtain some finite formulas or recurrent formulas. But it is difficult or even impossible to find simple formulas for many problems. We can design computer methods for enumeration problems because computers are powerful. On the other hand, people are usually concerned about the numbers of nonisomorphic graphs or combinatorical structures. Group Theory provides the most efficient methods for enumerating nonisomorphic ones.Therefore combination of group theory and computer is a good path to the aim. Author and Canadian Graph Theory specialist Professor R. C. Read proposed a new method which called ”compressing graph method” in 1987. We will introduce this method and present some results by this method.