| dc.contributor.advisor | 郭大衛<br>李陽明 | zh_TW |
| dc.contributor.author (Authors) | 余銘芬 | zh_TW |
| dc.contributor.author (Authors) | Yu, Ming Fen | en_US |
| dc.creator (作者) | 余銘芬 | zh_TW |
| dc.creator (作者) | Yu, Ming Fen | en_US |
| dc.date (日期) | 2010 | en_US |
| dc.date.accessioned | 5-Oct-2011 14:39:35 (UTC+8) | - |
| dc.date.available | 5-Oct-2011 14:39:35 (UTC+8) | - |
| dc.date.issued (上傳時間) | 5-Oct-2011 14:39:35 (UTC+8) | - |
| dc.identifier (Other Identifiers) | G0095972009 | en_US |
| dc.identifier.uri (URI) | http://nccur.lib.nccu.edu.tw/handle/140.119/51308 | - |
| dc.description (描述) | 碩士 | zh_TW |
| dc.description (描述) | 國立政治大學 | zh_TW |
| dc.description (描述) | 應用數學系數學教學碩士在職專班 | zh_TW |
| dc.description (描述) | 95972009 | zh_TW |
| dc.description (描述) | 99 | zh_TW |
| dc.description.abstract (摘要) | 給定一個圖形G，以及集合M，M為一描述圖形G中各點擁有訊息之情形的集合。圖形G相對於M的的傳遞數是指，於最短時間內，讓圖形中全部點皆獲得所有種類之訊息，並將符號記為t(G;M) 。傳遞過程中每個時間單位將受到下列限制:(1)圖形上的每個點只能與自己相鄰的點交換訊息。(2)兩個相鄰的點在每個單位時間裡至多只能交換一個訊息。我們希望可以找到在最短的時間裡完成傳遞的方法，也就是讓圖形G中的每一個點都獲得所有種類之訊息，我們稱此類型問題為訊息傳遞問題。在本論文中，給定一個圖形G，且圖形G中每個點的訊息只有一個，G中任兩點的訊息都不會相同，符號t(G)代表完成傳遞所需最少的時間單位。我們給定圖形的傳遞數的上界與下界，並且定出一套公式計算樹圖、完全二部圖及雙環網路圖的傳遞數。 | zh_TW |
| dc.description.abstract (摘要) | 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. | en_US |
| dc.description.tableofcontents | 謝辭...................II中文摘要................III英文摘要................IV1.Introduction.........12.Preliminary..........33.Trees................64.Complete bipartite graphs....125.Double loop networks.........136.References...................16 | zh_TW |
| dc.language.iso | en_US | - |
| dc.source.uri (資料來源) | http://thesis.lib.nccu.edu.tw/record/#G0095972009 | en_US |
| dc.subject (關鍵詞) | 傳遞數 | zh_TW |
| dc.subject (關鍵詞) | 傳遞集 | zh_TW |
| dc.subject (關鍵詞) | 樹圖 | zh_TW |
| dc.subject (關鍵詞) | 完全二部圖 | zh_TW |
| dc.subject (關鍵詞) | 雙環網路 | zh_TW |
| dc.subject (關鍵詞) | transmission number | en_US |
| dc.subject (關鍵詞) | transmitting set | en_US |
| dc.subject (關鍵詞) | tree | en_US |
| dc.subject (關鍵詞) | complete bipartite graph | en_US |
| dc.subject (關鍵詞) | double loop network. | en_US |
| dc.title (題名) | 圖形的訊息傳遞問題 | zh_TW |
| dc.title (題名) | Message transmission problems of graphs | en_US |
| dc.type (資料類型) | thesis | en |
| dc.relation.reference (參考文獻) | [1] C. W. Chang, D. Kuo and C. H. Li, Generalized broadcasting and gossiping problem of graphs. preprint. | zh_TW |
| dc.relation.reference (參考文獻) | [2] M. L. Chia, D. Kuo and M. F. Tung, The multiple originator broadcasting problem in graphs, Disc. Appl. Math. 155 (2007) 1188-1199. | zh_TW |
| dc.relation.reference (參考文獻) | [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. | zh_TW |
| dc.relation.reference (參考文獻) | [4] E. J. Cockayne and A. Thomason, Optimal multi-message | zh_TW |
| dc.relation.reference (參考文獻) | broadcasting in complete graphs. In Proc. Eleventh SE Conf. | zh_TW |
| dc.relation.reference (參考文獻) | on Combinatorics, Graph Theory and Computing. Utilitas | zh_TW |
| dc.relation.reference (參考文獻) | Mathematica, Winnipeg, 1980, pp. 181-199. | zh_TW |
| dc.relation.reference (參考文獻) | [5] A. Farley, Broadcast time in communication networks. SIAM J. Appl. Math. 39 (1980) 385-390. | zh_TW |
| dc.relation.reference (參考文獻) | [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. | zh_TW |
| dc.relation.reference (參考文獻) | [7] A. Farley and A. Proskurowski, Broadcasting in trees with multiple originators. SIAM J. Alg. Disc. Methods. 2 (1981)381-386. | zh_TW |
| dc.relation.reference (參考文獻) | [8] M. Garey and D. Johnson, Computers and Intractability: A | zh_TW |
| dc.relation.reference (參考文獻) | Guide to the Theory of NP-Completeness. Freeman, San Fran- | zh_TW |
| dc.relation.reference (參考文獻) | cisco, 1979. | zh_TW |
| dc.relation.reference (參考文獻) | [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. | zh_TW |
| dc.relation.reference (參考文獻) | [10] S. M. Hedetniemi, S. T. Hedetniemi and A. L. Liestman, A Survey of gossiping and broadcasting in communication net- | zh_TW |
| dc.relation.reference (參考文獻) | works, Networks 18 (1988), 319-349. | zh_TW |
| dc.relation.reference (參考文獻) | [11] P. J. Slater, E. Cockayne and S. T. Hedetniemi, Information dissemination in trees.SIAM J. Comput. 10 (1981) 692-701. | zh_TW |
