(3.230.173.249) 您好！臺灣時間：2021/04/21 05:01

### 詳目顯示:::

:

• 被引用: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.
 論文摘要 IAbstract II誌謝 III目錄 IV圖目錄 V第一章 緒論 11.1 研究動機 11.2 研究範圍 11.3 論文架構 1第二章 理論與相關名詞解釋 32.1 名詞解釋 32.2 西洋棋盤圖-城堡圖(Rook’s graph) 42.3 西洋棋盤圖-主教圖(Bishop’s graph) 52.4 西洋棋盤圖-皇后圖(Queen’s graph) 5第三章 將 hub set 運用於西洋棋盤圖 73.1 城堡圖(Rook’s graph) 73.2 主教圖(Bishop’s graph) 153.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)
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 CMMI ML4流程程序制定之研究 2 在區塊－仙人掌圖上探討混合支配問題 3 在梯形圖上探討中繼數 4 以社交網路為基礎之知識社群系統建置研究 - 以知識銀行系統為例 5 資管系學生關鍵知識盤點系統建置之研究 6 職涯探索輔導系統建置之研究 7 以知識本體論建構職涯建議系統之研究 8 基於樹增強型單純貝氏網路之文件分類方法 9 根基於共通脆弱性評估系統(CVSS)之脆弱性管理績效指標研究 10 無線隨意網路中考量資料項存取與異動分類的快取策略 11 一個可防複製的智慧型手機與平板軟體認證機制 12 網路環境中網頁與手機應用程式間即時互動的訊息傳遞 13 畫像真人化 14 車載隨意網路中以移動模式為基礎的權重叢集演算法 15 結合技術指標與加權模糊時間序列預測股票買賣點

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室