通訊網路上的傳播問題

Abstract

本論文所研究的（一個起點）的傳播問題是從一連通圖中某個知道某一訊息的點開始，經由一系列傳遞的過程，使圖中的其他點都得知此訊息。在傳遞給其他點的過程中，必須滿足下列三項規定：(1)每傳遞一次算一個單位時間；(2)每個點在傳遞訊息時，只能傳遞訊息給與其有邊相鄰的點；(3)在每次單位時間內，每點只能傳遞訊息給與之相鄰的一點。在這個問題上我們討論下列三個問題：(1)計算某點u的傳播時間，也就是從此點傳遞訊息給其他所有點所花的最短時間，記為b(u)；(2)在圖中選取一點使其傳遞時間不大於圖中其他點的傳遞時間，將其所花的時間定義為此圖的傳播時間，記為b(G)；(3)找出傳播時間與圖的傳播時間相等的所有點的集合，稱為圖的傳播中心，記為BC(G)。在本文中，我們用labeling algorithm簡化了Slater、 Cockayne和 Hedetniemi尋找樹的傳播中心的演算法。我們也在路徑、圈、滿m-元樹、完全圖和完全二分圖中研究了多重起始點的傳播問題。

Broadcasting from an originator is the process of passing one unit of information from that source to every other vertex in a connected graph G=(V, E). This is accomplished by a series of calls over the edges of G, subject to the following constraints：(1) each call requires one unit of times；(2) a vertex can only call an adjacent vertex；and (3) a vertex can participate in only one call per unit of time. We mainly discuss the following three problems：(1) finding the broadcast number b(u) of a vertex u which is the minimum number if calls needed to broadcast the information to all other vertices；(2) computing the broadcast number of G, denoted by b(G), which is the minimum broadcast number of a vertex in G；(3) determining the broadcast center of G, denoted by BC(G), which is the set of all vertices having minimum broadcast number. In this thesis, we simplify Slater, Cockayne and Hedetniemi's algorithm for finding the broadcast center BC(T) of a tree T by using a labeling algorithm. We also study the problem of broadcasting messages with multiple originators for paths, cycles, full m-ary trees, complete graphs, and complete bipartite graphs.