政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/51308

政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/51308

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | 全文筆數/總筆數 : 114400/145431 (79%)
造訪人次 : 53074192 線上人數 : 498

RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.

搜尋範圍

查詢小技巧：

您可在西文檢索詞彙前後加上"雙引號"，以獲取較精準的檢索結果

若欲以作者姓名搜尋，建議至進階搜尋限定作者欄位，可獲得較完整資料

進階搜尋

主頁 ‧ 登入 ‧ 上傳 ‧ 說明 ‧ 關於政大典藏 ‧ 管理

到手機版

政大機構典藏 > 理學院 > 應用數學系 > 學位論文 > Item 140.119/51308

請使用永久網址來引用或連結此文件: https://nccur.lib.nccu.edu.tw/handle/140.119/51308

題名:	圖形的訊息傳遞問題 Message transmission problems of graphs
作者:	余銘芬 Yu, Ming Fen
貢獻者:	郭大衛李陽明余銘芬 Yu, Ming Fen
關鍵詞:	傳遞數傳遞集樹圖完全二部圖雙環網路 transmission number transmitting set tree complete bipartite graph double loop network.
日期:	2010
上傳時間:	2011-10-05 14:39:35 (UTC+8)
摘要:	給定一個圖形G，以及集合M，M為一描述圖形G中各點擁有訊息之情形的集合。圖形G相對於M的的傳遞數是指，於最短時間內，讓圖形中全部點皆獲得所有種類之訊息，並將符號記為t(G;M) 。傳遞過程中每個時間單位將受到下列限制: (1)圖形上的每個點只能與自己相鄰的點交換訊息。 (2)兩個相鄰的點在每個單位時間裡至多只能交換一個訊息。我們希望可以找到在最短的時間裡完成傳遞的方法，也就是讓圖形G中的每一個點都獲得所有種類之訊息，我們稱此類型問題為訊息傳遞問題。在本論文中，給定一個圖形G，且圖形G中每個點的訊息只有一個，G中任兩點的訊息都不會相同，符號t(G)代表完成傳遞所需最少的時間單位。我們給定圖形的傳遞數的上界與下界，並且定出一套公式計算樹圖、完全二部圖及雙環網路圖的傳遞數。 Given a graph G together with a set M , the transmission number of G corresponding to M , denoted by t(G;M), is the minimum number of time needed to complete the transmission , that is, to let all the vertices in G know all the messages in M , subject to the constraints that at each time unit, each vertex can interchange messages with all its neighbors, but the number of messages that two vertices can interchange at each time unit is at most one. We want to find the minimum number of time units required to complete the transmission, that is, to let all the vertices in G know all the messages. We call such a problem the message transmission problem. Given a graph G, the transmission number of G, denoted t(G), is the minimum number of time units required to complete the transmission, under the condition that \|m(v)\|=1 for all v in V(G). In this thesis, we give upper and lower bounds for the transmission number of G, and give formulas to compute the transmission numbers of trees, complete bipartite graphs and double loop networks.
參考文獻:	[1] C. W. Chang, D. Kuo and C. H. Li, Generalized broadcasting and gossiping problem of graphs. preprint. [2] M. L. Chia, D. Kuo and M. F. Tung, The multiple originator broadcasting problem in graphs, Disc. Appl. Math. 155 (2007) 1188-1199. [3] P. Chinn, S. Hedetniemi and S. Mitchell, Multiple-message broadcasting in complete graphs. In Proc.Tenth SE Conf. on Combinatorics, Graph Theory and Computing. Utilitas Mathe-matica, Winnipeg, 1979, pp. 251-260. [4] E. J. Cockayne and A. Thomason, Optimal multi-message broadcasting in complete graphs. In Proc. Eleventh SE Conf. on Combinatorics, Graph Theory and Computing. Utilitas Mathematica, Winnipeg, 1980, pp. 181-199. [5] A. Farley, Broadcast time in communication networks. SIAM J. Appl. Math. 39 (1980) 385-390. [6] A. Farley and S. Hedetniemi, Broadcasting in grid graphs. In Proc. Ninth SE Conf. on Combinatorics, Graph Theory and Computing. Utilitas Mathematica, Winnipeg, 1987. [7] A. Farley and A. Proskurowski, Broadcasting in trees with multiple originators. SIAM J. Alg. Disc. Methods. 2 (1981)381-386. [8] M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Fran- cisco, 1979. [9] S. M. Hedetniemi and S. T. Hedetniemi, Broadcasting by de-composing trees into paths of bounded length. Technical Re-port CS-TR-79-16, University of Oregon, 1979. [10] S. M. Hedetniemi, S. T. Hedetniemi and A. L. Liestman, A Survey of gossiping and broadcasting in communication net- works, Networks 18 (1988), 319-349. [11] P. J. Slater, E. Cockayne and S. T. Hedetniemi, Information dissemination in trees.SIAM J. Comput. 10 (1981) 692-701.
描述:	碩士國立政治大學應用數學系數學教學碩士在職專班 95972009 99
資料來源:	http://thesis.lib.nccu.edu.tw/record/#G0095972009
資料類型:	thesis
顯示於類別:	[應用數學系] 學位論文

文件中的檔案:

檔案	大小	格式	瀏覽次數
200901.pdf	557Kb	Adobe PDF2	805	檢視/開啟

在政大典藏中所有的資料項目都受到原著作權保護.

社群 sharing

著作權政策宣告 Copyright Announcement

1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.

DSpace Software Copyright © 2002-2004 MIT & Hewlett-Packard / Enhanced by NTU Library IR team Copyright © - 回饋