圖論上的電力支配問題

Power Domination on Graphs

簡毓延(Yu-Yen Chien)

指導教授 ： 張鎮華

國立臺灣大學/理學院/數學研究所/碩士(2004年)

https://doi.org/10.6342/NTU.2004.00532

摘要

電力公司在其電力系統當中放置位相量測單元以監測系統的狀態。
為了節省成本，電力公司必須儘可能以少量的位相量測單元來監測整個系統。這個問題可以視為圖論中支配問題的推廣。對圖Ｇ來說，若點集合的子集Ｓ能夠根據電力系統監測的法則監測到Ｇ所有的點和邊，我們稱Ｓ為Ｇ的電力支配集，而Ｇ的最小電力支配集的元素個數稱為Ｇ的電力支配數。在本論文中，我們探討電力支配問題和支配問題之間的關聯性，並以支配問題的性質來證明電力支配問題在弦二部圖和最大度數為4的平面圖上是NP完備。我們也引進了將一個圖分割成電力支配數為1的導來子圖的概念，並以此給了電力支配數一個上界。最後我們給了另一個線性演算法來求樹狀圖的最小電力支配集。

關鍵字

支配 ； 電力監測 ； 電力支配

並列摘要

Electric power companies monitor the state of their electric power system by placing phasor measurement units in the system. For economical considerations, companies have to place as few phasor measurement units as possible and still maintain the ability of monitoring the entire system. This problem can be theoretically represented as a variation of the well-known domination problem in graph theory as follows. A set S is a power dominating set of a graph G if every vertex and every edge of G can be monitored by S following a set of rules for power system monitoring. The minimum cardinality of a power dominating
set of a graph G is the power domination number of G. In this thesis, we investigate the relation between power domination and domination, and use the NP-completeness of the domination problem to show that the power domination problem is NP-complete for chordal bipartite graphs and planar graphs with maximum degree 4. We also introduce the concept of partitioning a graph into induced subgraphs of power domination number 1 and give an upper bound of power domination number. In the last section, we give an alternative linear-time algorithm for the power domination problem on trees.

並列關鍵字

domination ； electric power monitoring ； power domination

參考文獻

T. L. Baldwin, L. Mili, M. B. Boisen, Jr., and R. Adapa, Power system observability with minimal phasor measurement placement, IEEE Trans. Power Syst., Vol. 8, No. 2, May 1993, 707-715.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, San Francisco, 1979.

T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi, and M. A. Henning, Domination in graphs applied to electric power network, SIAM J. Discrete Math. Vol. 15, No. 4, 2002, 519-529.

D. T. Lee and C. Liao, Power domination problem in interval graphs, manuscript, 2004.

M. B. Boisen, Jr., T. L. Baldwin, and L. Mili, Simulated annealing and graph theory applied to electrical power networks, manuscript, 2000.