跳到主要內容

臺灣博碩士論文加值系統

(18.97.14.81) 您好!臺灣時間:2025/02/19 02:47
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:鍾孟璇
研究生(外文):Meng-Hsuan Chung
論文名稱:關於圖的選擇辨識之研究
論文名稱(外文):A study of choice identifications of graphs
指導教授:董立大
指導教授(外文):Li-Da Tong
學位類別:碩士
校院名稱:國立中山大學
系所名稱:應用數學系研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2017
畢業學年度:106
語文別:英文
論文頁數:33
中文關鍵詞:選擇識別數識別集超立方體圖
外文關鍵詞:hypercube graphtreeidentifying setchoice identification number
相關次數:
  • 被引用被引用:0
  • 點閱點閱:255
  • 評分評分:
  • 下載下載:5
  • 收藏至我的研究室書目清單書目收藏:0
識別碼(identifying code)一開始由 Karpovsky 、 Chakrabarty 及 Levitin 三人介紹 。識別碼主要應用在處理多處理器系統的故障診斷。

對於一般圖不一定有識別碼,因此 Chang 及 Tong 提供了一個新的想法。如果我們對於圖 G 內的任意點 u 能利用點 u 的自身及其鄰居的子集提供唯一的識別方式,並且收集我們在圖 G 內所有用於識別的點所形成的集合,這個集合我們就稱為圖 G 的識別集(identifying set)。最小選擇識別數為最小識別集的元素個數。我們對於圖 G 的最小選擇識別數(choice identification number)i_c(G) 感到興趣,如果我們可以知道圖 G 的最小選擇識別數,則我們可以在檢查錯誤時,以最快時間找到在系統中的錯誤。

這篇論文中,一開始我們提供一些定義關於圖的定義及選擇識別碼在圖上的性質,接著我們利用兩層或三層的超立方體圖 Q_n(hypercube graph)子圖,找出 Q_n 的上界;最後,我們整理獲得的結果並敘述一些未解的問題。
The identifying codes were introduced by Karpovsky, Chakrabarty, and Levitin. They are applied to solve the diagnosis of faults in multiprocessor system.

Since not all of graphs have identifying codes, Chang and Tong gave a new idea. If we can uniquely identify all vertices u of a graph G by some vertices of neighbors of u and u, and collect all vertices of G which are selected by identifying vertices of G, then the set is called an identifying set of G.

The choice identification number i_c(G) of a graph G is the cardinality of a minimum identifying set of G. We interest the choice identification number i_c(G) of a graph G.

In the thesis, we give some introductions of graph and some properties of choice identifications in graphs, first. Next, we use two or three level of a hypercube graph Q_n to find upper bounds of Q_n. Finally, we give conclusions and open questions.
Contents
致謝 i
摘要 ii
Abstract iii
Contents iv
List of Figures v
1 Introduction 1
2 The main results 4
2.1 Properties of choice identi cations in a graph . . . . . . . . . . . . . 4
2.2 Induced subgraphs by two levels of a hypercube graph . . . . . . . . . 9
2.3 Induced subgraphs by three levels of a hypercube graph . . . . . . . . 14
2.4 Comparison choice identi cations on two and three levels of a hyper-
cube graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Algorithm for determining a minimum identifying set of a graph G 21
4 Conclusion 22
D. Auger, I. Charon, O. Hudry, A. Lobstein, Watching systems in graphs: an extension of identifying codes, Discrete Appl. Math. 161 (2013) 1674-1685.

I. Charon, O. Hudry, A. Lobstein, Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard, Theoret. Comput. Sci. 290 (3) (2003) 2109-2120.

T.-P. Chang, L.-D. Tong, Choice identification of a graph, Discrete Appl. Math. 167 (2014) 61-71.

S. Gravier, J. Moncel, Construction of codes identifying sets of vertices, Electron. J. Combin. 12 (2005) R13.

M.G. Karpovsky, K. Chakrabarty, L.B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory 44 (2) (1998) 599-611.

T. Laihonen, S. Ranto, Codes identifying sets of vertices, Lecture Notes in Comput. Sci. 2227 (2001) 82-91.

J. Moncel, On graphs on n vertices having an identifying code of cardinality $lceil log_{2}{(n + 1)}
ceil$, Discrete Appl. Math. 154 (14) (2006) 2032-2039.

A. Raspaud, L.-D. Tong, Minimum identifying code graphs, Discrete Appl. Math. 160 (9) (2012) 1385-1389.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top