我有一个带有 N 个节点和 E 个边的有向未加权图。节点的平均度为 2E/N。
在第一轮中，每个节点都将其信息广播给所有邻居。在随后的轮次中，节点将上一轮期间从邻居收到的信息广播给所有其他邻居，依此类推。
不保证该图是非循环的。
我的问题是:平均需要多少次连续广播才能使 95% 的节点对相互到达？是否可以根据平均值计算出一个近似数字图的度数？
最佳答案
平均而言，我假设您的意思是所有可能的没有多重边的 (N,E) 有向图的平均值。
定理1
如果 E <= (N-1)^2，则至少有一个图的信息不会传播。
证明
具有 N 个节点的有向图最多具有 N(N-1) 条边。考虑一个完整的图，选择一个节点，然后删除它的所有出边(或者，我们可以删除它的所有入边)。来自该节点的信息无法传播，我们只剩下 N(N-1)-(N-1) = (N-1)^2 条边。
推论1
当E <= (N-1)^2时，至少有一张图信息无法传播，因此平均轮数为无穷大。
定理2a
如果 E > (N-1)^2，则最大轮数为 2。
证明
具有 N 个节点和 E > (N-1)^2 条边的有向图是最多删除 (N-2) 条边的完全图。
如果我们想从完整图中删除边，使得轮数为 3(例如从节点 A 到节点 B)，我们需要确保不存在节点 B 和边 A->B且 B->C。这意味着我们需要为 (N-2) 个可能的“B”节点中的每一个删除至少一条边(A->B 或 B->C)。我们还需要删除直接的 A->C 边。我们总共需要删除 (N-3) 条边。
定理2b
如果 E > (N-1)^2，则最小轮数为 2。
证明
微不足道。该图是不完整的，因此至少存在一条长度为 2 的路径。
推论2
如果 (N-1)^2 < E < N(N-1)，则轮数为 2。
定理3
如果E = N(N-1)，则轮数为1
证明
微不足道。完整图表。
现在，您询问的是超过 95% 的节点对。
当然，我们可以构建一些 (N-1)^2 < E < N(N-1) 图，其中 >= 95% 的有序节点对可以在 1 轮中通信，但其他有序节点对- 两人进行 2 轮交流。
如果您考虑一个包含 6 个节点的完整有向图，其中仅删除一条边，那么这是微不足道的。 (6*5-1)/(6*5) = 96.66% 的有序节点对可以在一轮中进行通信。
为什么要具体询问 95%？精确计算这个数字重要吗？让我们知道。我不认为你可以推导出一个简单准确的通用公式，特别是当 N 和 E 很小时。也许我们可以渐近地制定一些东西(对于非常大的 N)。
关于graph - 允许 95% 的节点对在有向图中交换的广播数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34424719/