40000字硕士毕业论文图的功率控制集问题
论文类型：硕士毕业论文
论文字数：40000字
论点：控制,电力,节点
论文概述：
电力控制集问题就是确定给定图的电力控制数，最初由T.W. Haynes提出，并证明了这个问题对于一般图而言是完全的.本文在总结了前人的理论成果的基础之上，系统地论述了图的电力控制集问题
论文正文：
第一章导言
为许多现实生活中代表关系的例子建立带有图形的数学模型通常非常方便。这样的图由一组点和这组点中一些对的连接线组成。例如，点代表人，而连接线代表两个人的理解。这些例子的数学抽象产生了图论。1736年是图论的第一年。当时，欧拉解决了一个困扰人们的著名问题——柯尼斯堡七桥问题，从而成为图论和拓扑学的创始人。随着计算机的兴起，图论的研究取得了很大进展，已经成为离散数学和计算机科学的重要组成部分，包括图论算法、极限图论、随机图论、代数图论和拓扑学。本文主要介绍了功率控制集在算法和相关研究方向上的成果，并介绍了我在功率控制集问题上取得的成果。
1.1基本知识
1.1.1基本概念定义
1.1(图形)无向图G，缩写为图形，是(V；五、t/；
(1) v称为图的顶点集，其中元素称为顶点，节点数| 1 |称为图的顺序，表示为xj或n；
(2) e称为图的边集，其中元素称为边，边的个数|E|称为图的大小，表示为E或m；
(3)被称为图的关联函数，如果e e，tb{e) = {u，u} C V，{u和V不需要不同)，那么u/t)被称为边E的两个端点，u和E是关联的，u和E是相邻的。或者相邻(邻近)，表示为紫外线。
定义1.2(简单图)具有相同端点的边称为循环。连接同一对节点的边称为平行边。没有循环和平行边的图叫做简单图。对于简单的图，每条边由其两个端点唯一确定，因此省略了边的标记。设置脊(4) = {a，(；E =亮)或e = vu。
1.2电源控制装置
1.2.1该问题源于
功率控制集问题，首次引入该问题是为了对电力系统的监控问题进行数学建模。电力公司需要连续传递一组定义的状态变量(例如，负载的电压大小和发电机的机器相位角)来监控其系统的状态。监控这些变量的一种方法是在系统的指定位置放置相位测量单元。由于PMU成本高，有必要在保持对整个系统监控的同时，尽量减少PMU的数量。如果系统的所有状态变量可以通过一组值(例如，电压和电流)来测量，这些值是根据以下规则确定的，那么系统被称为被监控的。
(1)所有分流相位测量值都分配给PMU所在的节点，电压测量值同时分配给PMU所在的节点)；
(2)根据欧姆定律(s law)，如果一端的分流电流和电压已知，则在另一端施加电压测量值2；
(3)根据欧姆定律，如果分流器两端的电压已知，则分流器被给予电流相位测量值；
(4)根据基尔霍夫电流定律，如果可以推断出支路的电流，则支路的电流相位测量值为3。
第二章完美图上的功率控制集问题
2.1一般理论
本节描述了功率控制集问题的一般理论，引入了凸图的概念，刻画了MPDS节点的性质，并给出了功率控制数的上限。对于控制集问题，只有控制律0R1可用；对于功率控制设置的问题，还有另一个附加的控制规则0R2。因此，每个控制集也是一个功率控制集，所以有以下命题。
命题2.1(海恩斯)对于任何图形G都有1 < 7P(G0 (G))，接下来，看看上面的不等式等于符号的条件。从控制规则0112可知。功率控制集的控制机制是非本地的:当满足某些条件时，节点可以控制任意距离的节点。显然，对于所有路径Pn，存在、、Pn) = 1，并且集合中的任何节点形成最小功率控制集合。除了Pn之外，还有一些满足p(G0 = 1)的图，它们共同构成了以下命题。图G {P，C }的
命题2.2(海恩斯)？有，{G) = 1。两个图和一个丑陋的日冕图，用G表示。它由一部分G和一部分H组成，其中G的第Z节点与第I部分中的每个H节点相关联。冠状图G = Pfc:满足7p(G)= 7(G)= A；；皇冠数字=。第二章功率控制装置.............................................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标记算法.............................................34-41
on.............................................31-34
2.4区间图2.4.1初步知识.............................................35-37
2.4.2标签算法37-41
第三章功率控制集问题分析.............................................41-43
3.1一般理论.............................................41-42
3.2 NP-完成.............................................42-43
第4章特殊图形上的功率控制集问题.............................................43-47
4.1网格图上的算法.............................................43-45
4.2彼得森通用图表.............................................45-47
第五章附言.............................................47-48
结论
在1.1.2小节中，给出了弦图的概念。在3.2小节中，证明了弦图上的功率控制集问题是NP-完全的。强弦图是弦图的一个重要子图类。希望强弦图的功率控制集问题最终得到解决。以下是一些基本概念和结论。许多学者在研究[32.3气体控制集时引入了
强弦图，包括树、块图、区间图、有向路径图等。迄今为止，已有许多研究来识别强弦图。在中，作者给出了一个复杂度为0 (| 1 | 3)的多项式时间算法来检验给定的图G= (V，V)是否是强弦图。此后，一些人将复杂度提高到0(1(LogL)2)，其中|/|+| |。后来，一些人给出了复杂度为C(1(log1))l36j和0(1V|2)[371的多项式时间算法。同时，如果给定的图是强弦图，这些算法也可以给出强消去顺序。