通訊網路上訊息傳送問題

Abstract

本論文主要是討論通訊網路上的訊息傳送問題。在通訊網路上，最初只有一個人知道唯一的消息，這個人稱為廣播中心；然後透過所給的通訊網路，藉由打電話的方式將廣播中心的訊息傳給其它人；最後每個人都要知道這個訊息。在這篇論文中，我們利用圖G＝(V,E) 作為通訊網路的模型，求得一些通訊網路上訊息傳送的最少時間。我們證明：如果Ｇ是一佣連通圖，則Ｇ中的最少傳送訊息時間大於或等於Ｇ的半徑。我們並且證明：如果Ｇ是連通圖，而且距離Ｇ的任一中心最遠的點至少有兩個，則Ｇ中的最少傳送訊息時間大於Ｇ的半徑。更一般來說，我們證明：如果Ｇ是連通圖，藉由某一最佳傳送方式，經過第一個單位時間，Ｇ中有兩點知遣消息（稱為Ｓ集合），而且在Ｇ中有兩點與Ｓ中的其中一點距離為Ｓ的離心率，且與Ｓ中的另一點距離大於Ｓ的離心率，則Ｇ中的最少傳送訊息時間大於Ｓ的離心率加１。我們利用上述的結果，求得：對於路徑與圈作笛卡兒乘積及正乘積所得網路中最少的傳送訊息時間。

In the broadcasting problem, exact one member of the network, called the broadcast originator (center), has a unique message which is to be disseminated to all other members as quickly as possible over the communication network. In this thesis, we model a communication network by a graph G = (V. E) and determine the minimum broadcast time in G. We prove that if G is a connected graph, then the minimum broadcast time in G is at least the radius of G, and if G is a connected graph in which there are two or more vertices that are farest to a center of the graph, then the minimum broadcast time is greater than the radius of G. Suppose G is a connected graph in which, after one unit of time, S = {u,v} know the message by an optimal call scheme. We also prove that if there are two vertices in G whose distances from u are eG (S) and distances from v are greater than eG (S), then the minimum broadcast time is greater than eG (S)+1. We use above results to obtain the broadcast times for Cartesian product and direct product of paths and cycles.