第一章引言
对现实生活中许多表示关系的事例，用图形建立数学模型，往往会非常方便，这种图形是由一个点集，以及这个点集中某些点对的连线构成的.比如用点表示人，而连线表示两个人认识，对这类事例的数学抽象产生了图论.1736年是图论的元年，当时L. Euler解决了一个困惑人们的著名问题——Konigsberg七桥问题，从而成为图论和拓扑学的创始人.随着计算机的兴起，图论研宄得到了长足发展，并己成为离散数学和计算机科学中理论完备的一个重要组成部分，包括图论算法、极值图论、随机图论、代数图论、拓扑图论等分支.本文主要介绍关于电力控制集在算法方面以及相关研究方向的成果，并介绍本人在电力控制集问题中所得到的结果.
1.1基础知识
1.1.1 基本概念定义
1.1 (图）无向图G，简称图（graph),是（V；五，t/；)的三元组.
(1) V称为图的节点集（vertex set),其中的元素称为节点（vertex),节点数|1^|称为图的阶（order),记为xj或n;
(2) E称为图的边集（edge set),其中的元素称为边（edge),边数|E|称为图的规模（size),记为e或m;
(3) 称为图的关联函数（incidence function),设 e e E, tb{e) = {u, u} C V, {u和V不必相异)，则称u/t)为边e的两个端点（endpoint)，互称u，和e是关联的（incident),并互称u和为邻居（neighbor),或邻接的（adjacent),记为UV.
定义1.2 (简单图）端点相同的边称为环（loop).连接同一对节点的边称为平行边（parallel edges).既没有环又没有平行边的图称为简单图（simple graph).对于简单图，每条边由它的两个端点唯一确定，因此省略边的标记.设岭⑷={a, (；},则简记e = lit)或 e = vu.
1.2电力控制集
1.2.1 问题由来
电力控制集问题中被首次引入，用于对电力系统的监控问题进行数学建模.电力公司需要不断地通过定义的一组状态变量（例如，负载的电压大小、发电机的机相角）来监控他们系统的状态.监控这些变量的一种方法就是在系统的指定位置安放相位测量仪（phase measurement unit, PMU).由于PMU的昂贵费用，因此有必要在维持监控整个系统的前提下，最小化它们的数量.如果系统的所有状态变量都能被一组测量值（如，电压、电流）按照如下法则决定，则称该系统为被监控的.
(1)为PMU所在节点的所有分路赋电流相位测量值，同时为PMU所在节点赋电压测量值)；
(2)根据欧姆定律（Ohm’s law),若已知分路的电流和一端的电压，则为另一端赋电压测量值2;
(3)根据欧姆定律，若已知分路两端的电压，则为分路赋电流相位测量值；
(4)根据基尔霍夫电流定律（KirchhofTs current law),若某个分支的电流可被推断出来，则为该分支赋电流相位测量值3.
第二章完美图上的电力控制集问题
2.1 一般性理论
本节描述电力控制集问题的一般理论，进入冠图的概念，刻画MPDS中节点的性质，并给出电力控制数的上界.对于控制集问题，只有控制法则0R1;而对于电力控制集问题，却另有一个附加的控制法则0R2.因此每个控制集也是电力控制集，于是有下面的命题.
命题 2.1 (Haynes)对于任何图 G，都有 1 < 7P(G0 (G).接下来看看上面不等式取等号的条件.由控制法则0112知，电力控制集的控制机制具有非局部性：当一定的条件满足时，一个节点可以控制在任意距离远的节点.显然，对所有的路Pn,都有、、Pn) = 1，并且中的任何节点都构成一个最小电力控制集.除Pn以外，还有一些满足p(G0 = 1的图，它们一起构成下面的命题.
命题 2.2 (Haynes)对于图 G G {P, C? 有、{G) = 1.两个图G和丑的冠图（corona),记为G。它是由一份G和份H构成的，其中G的第Z个节点与第I份的H的每个节点都关联.冠图G = Pfc。：满足7p(G) = 7(G) = A;;而冠图 了 = 。K,满足 = l<k + l= 7(r).换句话说，一个图的控制数和电力控制数可以相等，也可以相差很大，那么满足7p(G0 = 7(G)的图具有什么样的性质，它的子图有什么特征吗，能否从子图的角度来刻画这样的图呢？下面的命题回答了这个问题.
第二章 完美图上的电力控制集....................................... 19-41
2.1 一般性理论....................................... 19-22
2.2 树上的算法....................................... 22-30
2.2.1 预备知识 .......................................22-24
2.2.2 标号算法....................................... 24-27
2.2.3 动态规划算法 .......................................27-30
2.3 块图上的算法....................................... 30-34
2.3.1 预备知识....................................... 30-31
2.3.2 标号算法....................................... 31-34
2.4 区间图上的算法....................................... 34-41
2.4.1 预备知识 .......................................35-37
2.4.2 标号算法 37-41
第三章 电力控制集问题的分析 .......................................41-43
3.1 一般性理论 .......................................41-42
3.2 NP-完全性....................................... 42-43
第四章 特殊图上的电力控制集问题....................................... 43-47
4.1 网格图上的算法....................................... 43-45
4.2 一般的Petersen图....................................... 45-47
第五章 后记 .......................................47-48
结论
在第1.1.2小节，给出了弦图的概念，而在第3.2小节，证明了电力控制集问题在弦图上是NP-完全的，强弦图是弦图的一个重要的子图类，希望能最终解决强弦图的电力控制集问题，下面给出一些基本的概念和结论.
强弦图是由多名学者在研究控制集时引入的[32.3气它包括树、块图、区间图、有向路径图等.到目前为止己经有很多研宄成果来鉴别强弦图.在中，作者给出了一个复杂度为0(|1^|3)的多项式时间算法来测试给定的图G= (V，五）是不是强弦图.此后，有人将复杂度改进到0(L(logL)2)，其中|/| + |￡|.后来又有人给出了复杂度为C)(L(logL))l36j和0(1V|2)[371的多项式时间算法.同时这些算法也能给出一个强消去序，如果给定的图是强弦图.