非同构简单无向图的计数方法

A numbering scheme of non-isomorph graph

首先在正整数的所有无序划分构成的集合上定义了一个全序关系,由此将所有无序划分的全体分成一些互不相交的子集,从而得到生成所有无序划分的方法,也就得到了n顶点的全体置换格式,然后给出了由简单无向图的顶点的置换格式确定简单无向图边的置换格式的方法,最后给出了n顶点非同构简单无向图的生成多项式并给出了部分计算结果。

A total order '≤' is defined in a set S(n), which is the collection of all non-order partitions of the natural numbers N. According to this order a partition of S(n) and an algorithm of the recursion are obtained. All permutation formats of N-vertices of the simple undirected graph are gained. The relation between the permutation formats of vertices and those of edges is given. The formula used to compute the total number and the particular distribution of the non-isomorph graph of the simple undirected graph is also given. The generation polynomial of the non-isomorph graph and some computation results are presented.