圖的覆蓋問題之研究

Abstract

圖的覆蓋問題是一種最佳化問題, 考慮在給定條件下如何來覆蓋圖的點集或邊集, 或者說選某些點或邊的子集使得每個點或每條邊屬於至少一個子集。圖的覆蓋問題除了理論的挑戰亦有許多實務的應用, 它被廣泛用於各種領域之中, 例如生物化學中的基因體學, 電機工程的通訊網絡與編碼理論, 電腦科學的演算法與計算方法, 或運籌學的排程調度等等。 本論文討論以下六種圖的覆蓋問題。 「強邊著色」是將邊著色使得任何兩條距離小於等於二之內的邊需著不同顏色; 「邊羅馬控制」為邊版本的羅馬控制, 將邊給上0,1,2的標記使得一條標0的邊必與一條標2的邊相鄰; 更廣義來說, 「k權羅馬控制」考慮將點給0,1,...,k的標記使得從一個標0的點算i步之內必有一個標i (<k+1)的點; 「距離邊覆蓋」是廣義的邊覆蓋, 將邊標記使得每個點都有一個標記j的邊在它的j步之內; 「模定向」為一個邊的定向, 使得每個點的內向度數等同於其外向度數; 「鬆弛過程」考慮點標號, 及把標負數的點更改標號為其絕對值, 並將其差值由此點的鄰居們共同分擔的過程。 這篇論文的目的為用演算法, 代數與機率觀點探討上述覆蓋問題。 對於某些相關的參數, 我們給出精確值或上下界, 並發展新技巧來解決問題, 證明或反證已知的猜想。

Covering problems in graphs are optimization problems about covering the vertex set V(G) or the edge set E(G) of a graph G under some additional restrictions. In other words, a emph{graph covering} of G is a collection of vertex/edge subsets of G such that each vertex/edge of G is belonged to at least one subset in this collection. Graph covering enjoys many practical applications as well as theoretical challenges. It is heavily used in various fields such as biochemistry (genomics), electrical engineering (communication networks and coding theory), computer science (algorithms and computation) and operations research (scheduling) etc. In this thesis, we consider six covering problems in graphs, which study the optimality of the following related functions. A it strong edge-coloring is a function that assigns to each edge a color such that any two edges within distance two apart receive different colors. An edge Roman dominating function is the edge version of a Roman dominating function, that is, a function f: E(G)->{0,1,2} such that every edge e with f(e)=0 is adjacent to some edge e' with f(e')=2. More generally, for a fixed positive integer k, a k-power Roman dominating function is a function f:V(G)->{0,1,...,k} such that every vertex u with f(u)=0 is adjacent to some vertex v with f(v)=i<k+1 within distance i. A distance edge cover is a generalization of an edge cover, that assigns each edge a label such that every vertex is within distance j from some edge with label j. A modular orientation is an orientation of edges such that the in-degree equals to the out-degree of each vertex. A relaxation procedure is a series of relabeling by changing the sign of a negative vertex and sharing the difference equally to its neighbors. The purpose of this thesis is to study the above mentioned graph covering problems from algorithmic, algebraic and probabilistic point of view. In particular, we give exact values and/or upper/lower bounds for related parameters of these problems. New technics are developed to establish interesting results, including the proofs/dis-proofs of some known conjectures.