無線網路中單位圓盤圖的不完美比例

Abstract

無線網路上的干擾問題是重要且困難的，該問題對應到單位圓盤圖的著色問題。在文獻[9]中，Mani和Petr對隨機網路的單位圓盤圖做了大量的模擬，並且觀察到單位圓盤圖的完全子圖數ω(G)和著色數χ(G)是非常接近的。為了估計ω(G)與χ(G)的接近程度，Mani和Petr採用了「不完美比例」imp(G)=sup_R(χ(G')/ω(G'))。這裡的G'是由G轉換過來的圖，而這個sup是考慮所有權重向量R之後計算所得。已 有學者證明出imp(G)的理論上界是2.155，imp(G)=1若且唯若G 是完美圖。基於模擬所得之結果，Mani和Petr認為，對單位圓盤圖而言，一個切合實際的上界是imp(G)=1.2079，這個上界值遠小於猜測中的上界值1.5，也遠小於理論上界值2.155。本論文之目的在於證明確實存在單位圓盤圖其imp(G)>1.2079，且猜測中的上界值imp(G)=1.5是可達到的。特別地，我們證明了：若G是長度≥5的奇圈或者是Harary圖H_(2m,3m+2)（其中 m 是奇數），則imp(G)=1.5；若G 是輪圖W_6 ，則imp(G)=4/3。

The interference problem between nodes in a wireless network is important and difficult and it corresponds to the coloring problem in Unit Disc Graphs (UDGs). In [9], Mani and Petr performed extensive simulations with UDGs of random networks and observed that in a UDG G, the clique number ω(G) and the chromatic number χ(G) were typically very close to one another. To evaluate the closeness of χ(G) and ω(G), Mani and Petr used the measure “imperfection ratio” imp(G) = sup_R(χ(G')/ω(G')).Here G' is a graph transformed from G and the supremum is computed over all possible weight vectors R. It has been proven that the theoretical bound of imp(G) is 2.155 and imp(G) = 1 if and only if G is perfect. Based on the simulation results, Mani and Petr concluded that a practical bound for UDGs is imp(G) ≤ 1.2079, which is far less than the conjectured upper bound of 1.5 or the theoretic upper bound of 2.155. The purpose of this thesis is to show that there exist UDGs such that imp(G) > 1.2079 and the conjectured upper bound imp(G) = 1.5 is achievable. In particular, we show that: if G is an odd cycle of length ≥ 5 or is the Harary graph H_(2m,3m+2) where m is odd, then imp(G) = 1.5, and if G is the wheel W_6, then imp(G) = 4/3.