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

Research and Applications of the Biggest Scatter of Simple Vndirecfed Grgph

作　　者：张乃岳[1] 潘劲[1] 

机构地区：[1]北京大学软件与微电子学院北京大学ACOM金融信息化研究中心,北京100871

出　　处：《计算机与数字工程》2008年第10期157-161,共5页Computer & Digital Engineering

摘　　要：提出了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.

关 键 词：图论 无向简单图 散度 不邻接划分 

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