簡易檢索 / 詳目顯示
| 研究生： |
王家駿 Chia-Chun Wang |
|---|---|
| 論文名稱： |
在西洋棋盤圖上之 Hub set 研究 Hub Set on the Rook’s, Bishop’s and Queen’s Graph |
| 指導教授： |
洪政煌
Cheng-Huang Hung |
| 口試委員: |
楊維寧
Wei-Ning Yang 王有禮 Yue-Li Wang |
| 學位類別： |
碩士 Master |
| 系所名稱： |
管理學院 - 資訊管理系 Department of Information Management |
| 論文出版年： | 2012 |
| 畢業學年度： | 100 |
| 語文別： | 中文 |
| 論文頁數： | 44 |
| 中文關鍵詞： | Hub set 、Hub number 、城堡圖 、主教圖 、皇后圖 |
| 外文關鍵詞： | Hub set, Hub number, Rook’s graph, Bishop’s graph, Queen’s graph |
| 相關次數： | 點閱：145 下載：3 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
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.
[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)
