信息传播的最优结构  

The optimal structure of information dissemination

作　　者：陈智斌[1] 李建平[1] 

机构地区：[1]云南大学数学系,云南昆明650091

出　　处：《云南大学学报（自然科学版）》2004年第5期378-381,共4页Journal of Yunnan University(Natural Sciences Edition)

基　　金：国家自然科学基金资助项目 ( 10 2 7110 3 ) ;云南省自然科学基金资助项目 ( 2 0 0 3F0 0 15M ) .

摘　　要：研究连通网络中的信息传播问题 ,即有信息的节点vi在每个单位时间里能同时向它的至多ki(ki ≥1)个邻点发送信息 ,要求传播的最短时间 ,使得网络中所有顶点均有此种信息 .鉴于在任意网络中该问题是NP-完备的 ,特研究一种特殊的网络 ,即m维立方体网络 .通过应用递推技巧 ,揭示了在m维立方体网络上信息传播的诸多好的特性及有趣的现象 。The problem of information dissemination on network is studied,where any vertex v_i that has information can transmits its information to at most k_i(k_i≥1) neighbors simultaneously per a unit time.The objective of this problem is to minimize the broadcasting time such that all vertices in the network can received this information.Since this problem is NP-complete in an arbitrary network,the special network called a hypercube of m-dimensions is studied.By using the technique of induction,many good features as well as some interesting characteristics in this hypercube are given,which shows that hypercube is the optimal structure to information dissemination.

关 键 词：信息传播 最优结构 k1-传播模型 m维立方体网络 NP-完备 最优结构 连通图 

分 类 号：G206[文化科学—传播学] O157.5[理学—数学]