下载苹果平板电脑qq:最小广播图的研究
来源：百度文库 编辑：高校问答 时间：2024/04/30 15:05:15
给定一个拥有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的最小整数
现在要求每一个可以发布信息的点按照规则发布信息。不能发
布信息的点按规则传播信息。
信息通过点与点之间的电缆传送。
显然每个点都连接在一起的话肯定可以满足规则，但是那样却
需要电缆n*(n-1)/2根。
现在为了节约成本，我们需要求出满足要求的电缆的数目的最
小值。
规则：
1.每个信息发布点每间隔秒钟发布一次信息
2.每次发布或者传播信息的时候只能向一个与该点连接的并且
没有接受到信息的点传送信息
3.发送和传播的间隔时间为1秒
4.每个信息发布点的发布的信息不一样
5.发送时间最多不能超过Floor[ln( n )/ln( 2 )]
例：n=8时，最多不能超过3秒
n=12时，最多不能超过4秒
Floor[x]表示不小于x的最小整数