赵　敏,陈　琴

(中国计量大学 理学院,浙江 杭州 310018)

1　简　介

近三十多年来,图的控制数理论已成为图论的一个重要研究领域,在相关学科领域具有广泛的应用.根据不同的应用背景,人们定义并研究了多种控制参数[1-9].关于图的控制理论的全面研究进展可参看文献[8,9].2002年,Haynes等在文[10]中首先研究了电力网的监控问题.电力公司为了实现对整个电力网运行的监控,需要在电力网中选择一些电力节点来放置监控设备(PMU).由于PMU成本的昂贵性,我们希望在保证整个电力网被完全监控的前提下,选择尽可能少的节点放置PMU.如果电力网中所有的电力节点和电力传输线都能被放置在电力网中的PMU所监控,那么就称整个电力网被这些PMU监控.Haynes等把这类电力网的监控问题转化到图论上,发现它与图论中经典的点覆盖及控制集问题有着密切的关系.

用G=(V,E)代表整个电力网,G的顶点代表电力节点,边代表连接两个电力节点的传输线.一个PMU监控它所在的电力节点及与此节点关联的边和这些边的另一个端点(这些节点和边称为被监控).其它被监控的规则如下:

1)如果一条边被监控,则与它关联的点也被监控;

2)如果两个相邻的点被监控,则连接这两点的边也被监控;

3)如果一个点与k条边关联(k>1),并且这k条边中有k-1条被监控,则这k条边都被监控.我们称电力控制集具有“传递性”.

设S⊆V(G),若N[S]=V(G),则称S为图G的控制集.最小控制集的基数称为控制数,记为γ(G).基数恰为γ(G)的控制集称为G的γ(G)-集.若S为G……