对一个与并行结构和通信网络设计密切相关的图论公开性问题进行了研究。讨论了图的结点数为n，连通度至少为k，k-直径至多为d的条件下的最小图问题，给出了一般条件下最小图边数条数的上、下界，在此基础上，得到了两种条件下最小图边数的计算公式，结合已有的图论结果，对文中所提到的最小图进行了构造。关 键 词 图; 公开性问题; 连通度; k-直径; 直径在并行结构和通信网络的设计中，往往希望构造一个满足一定条件的最小网络，即满足条件链路最少的网络，以减少网络材料开销。若把网络结点看着图的顶点，链路看着图的边，一个网络可以模型于一个图。本文将对图的顶点数为n，连通度至少为k，k-直径至多为d的条件下的最小图的边数问题进行分析研究。1 有关定义在文献[1]中介绍了有关图的容器(Container)理论和它的发展现状。容器是对单路径的扩充，在此基础上，扩充了图的连通度和直径的概念，提出了图的宽距离和宽直径的概念。设G表示一无向简单图(图中无自环、无平行边)，u、v表示图G中的顶点(也称为结点)，V(G)表示图G中的顶点集，概念定义如下[1]。定义 1 图G的两顶点间的一个容器C(u,v)是u、v间所有顶点不重合的路集合；容器C(u,v)的宽度是指该集合的势，记为w(C(u,v))；容器C(u,v)的长度是指这个路集合中最长路的长度，记为l(C(u,v))。定义 2 图G中的两顶点u、v之间的w-宽距离是指u、v之间所有宽为w的容器长度的最小值，记为dw(u,v)，即：dw(u,v)=min{l(Cw(u,v)), u≠v}，其中Cw(u,v)表示u、v之间宽度为w的容器。