图的增广支配数

增广ｐ一中心是在原有的服务设施基础上增加ｐ个设施为网络中的顶点提供紧急服务，因此增广ｐ一中心问题比经典的ｐ一中心问题更具有实际意义。本文提出了图的增广支配集、增广支配数的概念，这些概念与增广ｐ一中心问题密切相关，给出了求任意图全部极小增广支配集的布尔方法，提出了一个线性时间的算法求树的增广支配数。

Augmented Domination Number of a Graph

Augmented p-center is a class of problems that decides the positions of p new facilities that serve the all venices in a network along with the original facilities. It is obvious that the concept of augmented p-center is more meaningful than that of p -center. This paper presents the concepts of augmented dominating set and augmented domination number of a graph,which are closely related to the augment p-center. A Boolean method is given to find all minimal augmented dominationg sets of a graph. A linear time algorithmeis designed to determine the minimum augmented dominationg set of a tree. Computing examples are also given to demonstrate these algorithms.'