圖上電力支配問題的研究

Abstract

電力公司為了監控他們的電力系統，必須在系統中選定的位置上放置位相測量單位以監控電力系統的狀態。由於它的成本較高，因此電力公司必須儘可能地放置最少的位相測量單位，並使得整個系統仍然能夠被監控到以節省成本。這個問題可以視為圖論中支配問題的一種變化形，我們稱之為電力支配問題。 我們以圖論的方式來看電力支配問題：對於一個給定的圖G，如果一個頂點集的子集S，依循下列電力支配的方法可以監測到圖G的所有頂點和邊，則我們稱S是一個圖G的電力支配集：(1)S和S的鄰居可以被監測到；(2)如果有一個已經被S監測到的頂點，只剩下一個鄰居尚未被監測到，則此未被監測到的頂點可以自動地被監測到。而我們的目的是希望找到頂點數最少的電力支配集，這個最小的數目稱為圖G的電力支配數。 對於電力支配問題的研究方面，陸續已經有不少的結果被發表。而在這篇文章中，我們一開始先証明在兩個圈的卡氏積上電力支配問題的結果；接下來以演算法的觀點，分別在P_4-免除圖和樹狀圖上各給出一個演算法來找出其最小的電力支配集。

Electric power companies monitor the state of their electric power system by placing phase measurement units (PMUs) at selected locations in the system. They want to place as few measurement devices as possible such that these devices still monitor the whole system. This problem can be considered as a variation of the domination problem in graph theory, which we call the power domination problem. Power domination problem is defined as follows: given a graph G, a subset S is called a power dominating set if every vertex of G can be observed by S by repeatedly applying the following rules: (i) vertices in S and their neighbors are observed; (ii) if at some stage an observed vertex has exactly one unobserved neighbor, then this neighbor is observed. The purpose of the problem is to find a minimum power dominating set S of G. The minimum cardinality of a power dominating set of G is called the power domination number $gamma_p(G)$. In this thesis, we first determine the power domination numbers of the Cartesian product of two cycles. We then investigate the properties of co-graphs and give an algorithm for the power domination problem on co-graphs. Finally, we present a labeling algorithm for the power domination problem on trees.