论文部分内容阅读
广播问题,从P.J. Slater等人在1977年引入定义以来,至今已经有了非常丰富的内容和巨大进展。广播是信息在网络中传输的一种模式。通过相邻结点间的通讯把初始结点所拥有的信息传输到网络中的每一个结点。广播技术和理论深刻影响通讯、信息论、计算机网络等领域的发展,它本身也越来越成为网络和图论领域的一个重要分支。
广播是一个在通讯网络(作为图的模型)信息传播的过程,而这个信息传输过程是指在满足每一次通信需要一个时间单位和网络中每一个顶点在一个时间单位内至多和它的一个邻点通信这两个条件下把任一个顶点的信息传遍网络中所有顶点。在1998年,Shastri等人研究了广播时间略多于最优时间[log2n]的最稀疏可能的广播图,尤其是他们构造了对于小顶点数n(≤14)的最稀疏可能的广播图和对于较大顶点数n(≤65)的非常稀疏可能的广播图。Shastri猜想对于所有的n,存在一棵广播时间不超过「3/2(log2n+1)」+1的树。在本文中,我们得到较Shastri猜想更强的结果,即对于所有的n,存在一棵广播时间不超过「3/2(log2n+1)」-1的树。进一步的,我们利用了树的中心这一概念研究了对于固定广播时间的树的最大可能结构,得到了固定广播时间的最优广播树,从而给出了具有最优广播时间的任意阶树的的结构。