标题: | 半电力控制集的研究 A Study of Semi-power Dominating Set |
作者: | 吴政轩 傅恒霖 应用数学系所 |
关键字: | 电力控制集;半电力控制集;回馈点集合;power dominating set;semi-power dominating set;feedback vertex set |
公开日期: | 2009 |
摘要: | 用图的模型来研究一个半电力控制集问题是在图G上一些点放着测试器,依据我们订下的规则,若能让图G的所有边都被观察到,则我们称这些点所成的集合为图G的半电力控制集合。在这篇论文中,我们先说明了电力控制集问题与半电力控制集问题的关联性。接着,我们证明了一些特殊图的半电力控制集的最少点数,也证明当图G为连通图,且G中每个点所连到的边数至少为两边时,半电力控制集的最少点数与回馈点集的最少点数相等。我们也提出一递回方法,来建构PnXPn、CnXCn的半电力控制集;于是,提供了一个半电力控制集最少点数的上界。最后我们证出PnXPn的半电力控制集最少点数为Fn或Fn+1,其中Fn=[n^2-2n+2]+1,这结果改善了原来文献中的最佳结论。 In a semi-power domination set (SPDS) system, we place measurement units on some vertices of a graph G, and according to the rule we defined, if all the edges of G can be observed, then we say that the vertex set is a semi-power domination set. In this thesis, we first find the relationship between PDS and SPDS, and then we prove that the minimum size of SPDS of a graph G, denoted by γsp(G) is equal to the minimum size of the feedback vertex set of G provided G is connected and δ(G)≥2. In addition, we bring up a recursive idea to produce the SPDS of a graph G. Finally, with the recursive idea, we prove that γsp(PnXPn) is equal to either Fn or Fn+1 where Fn=[n^2-2n+2]+1. This improves known results. |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#GT079522531 http://hdl.handle.net/11536/41202 |
显示于类别: | Thesis |
文件中的档案:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.