通訊網路上的傳播問題

Abstract

通訊網路上的傳播問題包含訊息交換和訊息廣播兩問題。上述兩問題是描 述一群人在給定的通訊網路中傳送訊息的問題。在訊息交換問題□，每個 人最初只知道一個其他人不曉得的訊息，然後，透過所給的通訊網路，藉 由打電話交換彼此於打電話時所知道的所有訊息；最後，每個人都要知道 其他所有人的訊息。在訊息廣播問題□，最初只有一個人知道唯一的訊息 ，這個人稱為廣播中心；然後，透過所給的通訊網路，藉由打電話將廣播 中心的訊息傳給其他人；最後，每個人都要知道這個訊息。第二章主要是 ，在所給的網路上研究部份訊息交換問題，這個問題要求透過最少通電話 數，使每個人知道至少k 個不同訊息。第三章主要是，在所給的網路上研 究精確訊息交換問題，這個問題要求透過最少通的電話數目，使每個人恰 好知道k 個不同訊息。第四章主要是，研究訊息廣播所需時間問題，針對 三種不同的網路分別提出它們完成廣播所需最少時間。第五章主要是，給 一樹狀結構的通訊網路及給一特定時間 t，決定最少的廣播中心，使每個 人都能在t 時間內接收到訊息。我們提出一個線性演算法則解決這個問題 ，它的運算時間和給定時間t 無關。 Gossiping and broadcasting are the problems of information dissemination described for a group of members connected by a communication network. In the gossiping problem, every member originates a unique piece of message and must transmit it to every other member by a telephone call sequence in a given network. In each telephone call made between a pair of members, the two members involved exchange all messages they know at that time. Everybody knows all messages at the end of the sequence of calls. In broadcasting problem, exact one member of the network, called the broadcast originator, has a message which is to be disseminated to all other members by a call sequence over the network. In Chapter 2, we study the partial k- gossiping problem, which is to determine the minimum number of calls necessary for each member finally knowing at least k distinct messages on communication network G. In Chapter 3, we study the exact k-gossiping problem, which is to determine the minimum number of calls necessary for each member finally knowing exact k distinct messages on communication network G. In Chapter 4, We study the broadcast time problem and determine the minimum broadcast time for complete n-partite graphs, n- wheels, and wrap-around grids. In Chapter 5, we determine the minimum number of originators necessary to complete broadcasting in an arbitrary tree T in at most t time units of time, where t is a given positive integer. We present an O(|V( T)|)-time algorithm for the problem.