(3.230.173.249) 您好!臺灣時間:2021/04/21 05:01
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:王家駿
研究生(外文):Chia-Chun Wang
論文名稱:在西洋棋盤圖上之 Hub set 研究
論文名稱(外文):Hub Set on the Rook’s, Bishop’s and Queen’s Graph
指導教授:洪政煌洪政煌引用關係
指導教授(外文):Cheng-Huang Hung
口試委員:洪政煌
口試日期:2012-07-09
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:資訊管理系
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:44
中文關鍵詞:Hub setHub number城堡圖主教圖皇后圖
外文關鍵詞:Hub setHub numberRook’s graphBishop’s graphQueen’s graph
相關次數:
  • 被引用被引用:0
  • 點閱點閱:134
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:25
  • 收藏至我的研究室書目清單書目收藏:0
G = ( V, E )是一個簡單的無向圖,令H為G的點的子集合,表示為H V(G),使得在H外的任意兩點u和v,除了u和v兩點為鄰居外,存在一條路徑P,點u和v為此路徑P的兩端點且端點以外的內部節點皆在H裡面,我們稱H為G的hub set。

如果我們用最少的點的個數達成hub set,我們稱之為hub number,符號定義為h(G)。如果集合H為連通(connected)集,我們稱之為connected hub set。當我們用最少的點形成connected hub set,我們稱之為connected hub number,符號定義為hc(G)。

Rook、Bishop 和 Queen 是西洋棋中的城堡、主教、和皇后。在圖論中,西洋棋盤圖(chessboard graph)中的點(node)表棋子可以站立的位置,即棋盤上的方格(黑格或白格),圖中的邊(edge)表棋子合法的移動路徑。

本研究中,我們將hub set和hub number相關議題運用在城堡圖、主教圖與皇后圖上。在城堡圖與主教圖中,我們證明出其hub number與connected hub number,並提供一個找到最小hub set與connected hub set的方法。在皇后圖中,因為圖中有特殊情形,故我們只找到hub set與connected hub set的上限值,並給予一個建構出hub set與connected hub set上限的演算法。
Let G is a simple and undirected graph.Ahub set Hof G is a vertex subset such that for any two vertices u, v outside of H, either u and v are directly connected or there exists a path P between u and v with all internal vertices in H.
The hub number of G is the minimum cardinality of the hub set in G, denotedbyh(G). A connected hub setis a hub set which the induced subgraphin G is connected. The connected hub number of G is the minimum cardinality of the connected hub set in G, denoted by hc(G).
A chessboard graph is a graph that represents all legal moves of the chess pieces on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move.
In this study, we focuson the related issues of the hub set and the hub number in the Rook's graph, Bishop's graph and Queen's graph. In theRook's graph and Bishop's graph, we provethat the hub number and the connected hub number is exist, and provide a method of finding the minimum hub set and the connected hub set in these two graphs. In the Queen’s graph, we only find out the upper bound of the hub set the connected hub set because of the special conditions in the Queen's graph. Moreover, we construct upper bound hub set and connected hub set in the Queen's graph.
論文摘要 I
Abstract II
誌謝 III
目錄 IV
圖目錄 V
第一章 緒論 1
1.1 研究動機 1
1.2 研究範圍 1
1.3 論文架構 1
第二章 理論與相關名詞解釋 3
2.1 名詞解釋 3
2.2 西洋棋盤圖-城堡圖(Rook’s graph) 4
2.3 西洋棋盤圖-主教圖(Bishop’s graph) 5
2.4 西洋棋盤圖-皇后圖(Queen’s graph) 5
第三章 將 hub set 運用於西洋棋盤圖 7
3.1 城堡圖(Rook’s graph) 7
3.2 主教圖(Bishop’s graph) 15
3.3 皇后圖(Queen’s graph) 26
第四章 結論 33
參考文獻 34
[1]M. Walsh, The hub number of a graph, Int. J. Math. Comput. Sci. 1, 117-124 (2006)

[2]T. Grauman, S.G. Hartkeb, A. Jobson, B. Kinnersley, D.B. West, L. Wiglesworth, P. Worah, H. Wu, The hub number of a graph, Information Processing Letters 108 226-228 (2008)

[3]“Rook’s graph,” http://en.wikipedia.org/wiki/Rook's_graph

[4]E.J Cockayne, B Gamble, B Shepherd, Domination parameters for the bishop’s graph, Discrete Mathematics, Volume 58, Issue 3, Pages 221–227 (1986)

[5]‧Lowell W. Beineke, Izak Broere, Michael A. Henning, Queen’s graph, Discrete Mathematics, Volume 206, Issue 1-3, Pages 63–75 (1999)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔