跳到主要內容

臺灣博碩士論文加值系統

(3.236.225.157) 您好!臺灣時間:2022/08/16 00:13
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林保廷
研究生(外文):Bou-Tin Lin
論文名稱:CmXPn和CmXCn的兩起始點傳播問題
論文名稱(外文):Broadcasting with twooriginator of CmXPn and CmXCn
指導教授:郭大衛郭大衛引用關係
指導教授(外文):D.Kuo
學位類別:碩士
校院名稱:國立東華大學
系所名稱:應用數學系
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:34
中文關鍵詞:傳播
外文關鍵詞:Broadcasting
相關次數:
  • 被引用被引用:0
  • 點閱點閱:99
  • 評分評分:
  • 下載下載:9
  • 收藏至我的研究室書目清單書目收藏:0
本論文所要研究的是圖形的傳播時間,我們先給定一個圖形 ,如果 是圖中的一個子點集,當它為這個圖的傳播集合時,我們定義 是此圖上經由傳播集合中的點傳遞至所有點時所需花的最小傳播時間,並定義 為圖上有 個起始點時的最小傳播時間。

當 和 為圖形 中之兩個子點集時,對於所有在圖形 上的點 而言,定義 為 兩點的最小距離,其中 是子點集 中的點;而 定義為 兩點的最小距離,但此時 為子點集 中的點。再者定義 表 到 距離中的最大值,因此若子點集 中的點有 個時,則 表為這些 中的最小值。對於圖中的任一點 到圖中一子集 的距離均為 的這些點所成的集合定義為 ;而 中的點的個數定義為 。

在本文中,我們研究了一些圖形 和圖形 的 和兩個起始點的傳播問題。
Given a graph G and a vertex subset S of V(G), the
broadcasting time with respect to} S, denoted by b(G,S), is the minimum broadcasting time when using S as the broadcasting set. And the k-broadcasting number, denoted by bk(G), is defined by bk(G)=min{b(G,S)|S subseteq V(G),
|S|=k}}

For a given graph G and two vertex subsets S, S of
V(G). For all v in V(G), define d(v,S)=minlimits{u in S}
d(v,u),d(S,S'})=min{d(u,v)|u in S,v in S', and
d(G,S)=maxlimits{v in V(G)}d(v,S). For all k, k leqslant
|V(G)|, the k-radius of G, denoted by rk(G), is defined
as rk(G)=min {d(G,S) | S subseteq V(G),|S|=k}. For a vertex
subset S of V(G), we also define the m-neighbor of S to be
the set Nm(S)={v in V(G)| d(v,S)=m}, and nm(S)=|Nm(S)|.}

In this thesis, we study the 2-radius and the
2-broadcasting number of the graphs CmXPn and the graphs CmXCn.
1.Introduction 1

2.Lower bound of the k-broadcasting number of
graphs 3

3.The 2-radius and 2- broadcasting number of
CmXPn 6

4.The 2-radius and 2- broadcasting number of
CmXCn 20

5.Conclusion 32
[1] A. Farley and S. Hedetniemi, ``Broadcasting in
grid graphs.' In Proc. Ninth SE Conf. on
Combinatorics, Graph Theory and Computing. Utilitas
Mathematica, Winnipeg, 1987.

[2] A. Farley and A. Proskurowski, ``Broadcasting in
trees with multiple originators.' SIAM J. Alg.
(1981) 381-386.

[3] M. Garey and D. Johnson, Computers and
Intractability: A Guide to the Theory of NP-
Completeness. Freeman, San Francisco, 1979.

[4] S. M. Hedetniemi and S. T. Hedetniemi,
``Broadcasting by decomposing trees into paths of
bounded length'. Technical Report CS-TR-79-16,
University of Oregon, 1979.

[5] S. M. Hedetniemi, S. T. Hedetniemi and A. L.
Liestman, ``A Survey of gossiping and broadcasting in
communication networks', Networks(1988), 319-349.

[6] P. J. Slater, E. Cockayne and S. T. Hedetniemi,
``Information dissemination in trees.' SIAM J. Comput.
(1981) 692-701.

[7] K. W. Tien, Broadcasting Problemin Communation
Networks, Master Thesis, Dept. Applied
Math., National Chiao
Tung Univ., 2000.

[8] Y. S. Tsay, Gossiping and Broadcasting in
Communation Networks, Phd. Thesis, Dept. Applied
Math.,National Chiao TungUniv., 1996.

[9] M. F. Tung, The Multiple Originator
Broadcasting Problem in Graphs, Master thesis, Dept.
Applied Math.,National Dong Hwa Univ., 2001.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top