0

我试图在我的分布式算法课程中找到问题的答案，为此我想澄清一些事情。

  1. 具有一个节点且自身有一条边的图的直径是多少？是 1 还是 0？

如果您有兴趣，我试图找到答案的问题是：

就 n（# 个节点）而言，FloodMax 算法中使用的消息数（= diam * |E|）很容易看出是 O(n^3)。产生一类有向图，其中乘积 (diam * |E|) 确实是 Omega(n^3)。

我想出的有向图是一个只有一个节点的图，它本身有一条有向边。那样|E| 将是 1 ，即 n^2，如果 diam 是 1，它也满足第二个条件，即 diam = 1 = n 。所以它给了我一类消息复杂度为 Omega(n^3) 的有向图。

那么我的想法是否正确，在这样的图中，直径是 1？

4

2 回答 2

0

两件事情：

  1. 它似乎是 0 根据this，它说：

    换句话说，图的直径是当不考虑回溯、绕道或循环的路径时，为了从一个顶点行进到另一个顶点而必须遍历的最大顶点数。

  2. 您对给定问题的解决方案应该描述如何构建一个带有节点的图（或者更确切地说是什么类型的已知图具有该属性，因为它说“产生一个类”）n，而不是一个您手动计算出的具有多少节点的图解决方案。我可以对 2 个节点执行相同的操作：

    1 -- 2

|E| = 1 = (1/4)*2^2 = (1/4)*n^2 = O(n^2)
diam = 1 = 2 - 1 = n - 1 = O(n)
tada!

    或者，即使直径为 0，我们也可以让您的解决方案发挥作用：0 = 1 - 1 = n - 1 = O(n) => 您的解决方案仍然有效！

    因此，即使您也考虑了带有循环的路径，我仍然认为您的解决方案不正确。

于 2015-03-08T22:08:50.903 回答
0

O(n^3) 和 Omega(n^3) 并不意味着 cn^3，并且在 n 的有限多个非零值处为 0 的函数在 O(n^3) 和 Omega(n ^3)。例如，n^3-100 在两者中，n^3-100n^2 也是。出于渐近的目的，单个示例的直径是多少并不重要。您被要求找到一个具有足够大直径的无限图族，并且图的单个示例不会影响无限族的渐近线。

也就是说，可以通过几种方式定义图（或强连通图）的直径。一种可能性是在所有对 v 和 w 上从 v 到 w 并返回的往返长度的最小值的一半的最大值，并且当 v 和 w 重合时为 0。因此，具有一个顶点的图的直径为 0。

同样，这对您构建无限家庭的练习没有任何帮助。一个拥有一个节点和许多边返回自身的家庭不会削减它。想一想如何将许多边添加到具有大直径的图中，例如 n 循环或路径，而不会减少那么多的直径。

于 2015-03-09T13:51:39.053 回答