允许 95% 的节点对在有向图中交换的广播数
Number of broadcasts to allow 95% of node pairs to exchange in directed graph
我有一个有向未加权图，有 N 个节点和 E 个边。节点的平均度数为 2E/N。
在第一轮中，每个节点都将自己的信息广播给所有的邻居。在随后的轮次中，节点将上一轮从其邻居接收到的信息广播给所有其他邻居，依此类推。
不保证图是无环的。
我的问题是：要使 95% 的节点对相互联系，平均需要连续多少轮广播？ 是否可以计算一个近似值图基于图的平均度数？
平均而言，我假设您指的是所有可能的 (N,E) 有向图的平均值，没有多条边。
定理1
如果 E <= (N-1)^2，将至少有一个图不会传播信息。
证明
一个有 N 个节点的有向图最多有 N(N-1) 条边。考虑一个完整的图，select 一个节点，并删除它的所有出边（或者，我们可以删除它的所有入边）。来自该节点的信息无法传播，我们剩下 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% ordered-node-pairs 可以在 1 轮内通信，但其他 ordered-node-pairs 交流2轮。
如果您考虑一个包含 6 个节点的完整有向图，其中只删除了一条边，那么这是微不足道的。 (6*5-1) / (6*5) = 96.66% 的 ordered-node-pairs 可以在一轮中通信。
为什么要专门问95%？精确计算出这个数字是否重要？让我们知道。我不认为你可以推导出一个简单准确的通用公式，尤其是当 N 和 E 很小的时候。也许我们可以渐进地制定一些东西（对于非常大的 N）。
我有一个有向未加权图，有 N 个节点和 E 个边。节点的平均度数为 2E/N。
在第一轮中，每个节点都将自己的信息广播给所有的邻居。在随后的轮次中，节点将上一轮从其邻居接收到的信息广播给所有其他邻居，依此类推。
不保证图是无环的。
我的问题是：要使 95% 的节点对相互联系，平均需要连续多少轮广播？ 是否可以计算一个近似值图基于图的平均度数？
平均而言，我假设您指的是所有可能的 (N,E) 有向图的平均值，没有多条边。
定理1
如果 E <= (N-1)^2，将至少有一个图不会传播信息。
证明
一个有 N 个节点的有向图最多有 N(N-1) 条边。考虑一个完整的图，select 一个节点，并删除它的所有出边（或者，我们可以删除它的所有入边）。来自该节点的信息无法传播，我们剩下 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% ordered-node-pairs 可以在 1 轮内通信，但其他 ordered-node-pairs 交流2轮。
如果您考虑一个包含 6 个节点的完整有向图，其中只删除了一条边，那么这是微不足道的。 (6*5-1) / (6*5) = 96.66% 的 ordered-node-pairs 可以在一轮中通信。
为什么要专门问95%？精确计算出这个数字是否重要？让我们知道。我不认为你可以推导出一个简单准确的通用公式，尤其是当 N 和 E 很小的时候。也许我们可以渐进地制定一些东西（对于非常大的 N）。