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

A numbering scheme of non-isomorph graph

作　　者：张兴元[1] 蔡淮[2] 

机构地区：[1]西南交通大学峨眉校区基础课部,四川峨眉614202 [2]西南交通大学计算机与通信工程学院,四川成都610054

出　　处：《成都信息工程学院学报》2005年第3期332-335,共4页Journal of Chengdu University of Information Technology

摘　　要：首先在正整数的所有无序划分构成的集合上定义了一个全序关系,由此将所有无序划分的全体分成一些互不相交的子集,从而得到生成所有无序划分的方法,也就得到了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.

关 键 词：无序划分 全序关系 简单图 置换格式 

分 类 号：O157[理学—数学]