正文

最小广播图的研究2005-09-04 12:43:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/hawkjxr/4430.html

分享到:

给定一个拥有n个点网络,其中有k个点可以发布信息。 现在要求每一个可以发布信息的点按照规则发布信息。不能发 布信息的点按规则传播信息。 信息通过点与点之间的电缆传送。 显然每个点都连接在一起的话肯定可以满足规则,但是那样却 需要电缆n*(n-1)/2根。 现在为了节约成本,我们需要求出满足要求的电缆的数目的最 小值。 规则: 1.每个信息发布点每间隔秒钟发布一次信息 2.每次发布或者传播信息的时候只能向一个与该点连接的并且 没有接受到信息的点传送信息 3.发送和传播的间隔时间为1秒 4.每个信息发布点的发布的信息不一样 5.发送时间最多不能超过Floor[ln( n )/ln( 2 )]     例:n=8时,最多不能超过3秒         n=12时,最多不能超过4秒         Floor[x]表示不小于x的最小整数

阅读(2510) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册