简单无向图的最大散度问题及其应用

Research and Applications of the Biggest Scatter of Simple Vndirecfed Grgph

提出了n阶简单无向图的散度的概念-图的顶点度数中的不同的度数的种数,并且先构造性地证明了无约束n阶简单无向图的最大散度为n-1,然后利用邻接矩阵的方法给出了在有不邻接约束条件下的n阶简单无向图的最大散度的算法。

This paper gives a definition of scatter, which means the number of different degrees of the vertexes of a simple undirected graph with n vertexes. This paper proves that an unconstrained simple undirected graph with n vertexes has a biggest scatter n - 1, and it also gives an algorithm to give the biggest scatter of a simple undirected graph with a non- adjacent constraint.