只有一个节点的图的直径是多少？

Question

我正在尝试寻找分布式算法课程中问题的答案，为此我希望澄清一些事情。

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

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

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

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

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

Answer 1

有两件事：

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

   换句话说，图的直径是从一个顶点到另一个顶点当排除回溯、绕行或循环的路径时必须遍历的最大顶点数。

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) => 您的解决方案仍然有效！
   因此，即使您也考虑了带有循环的路径，我仍然认为您的解决方案是错误的。

Answer 2

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

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

再次强调，这对你构建无限家庭的练习没有任何帮助。一个只有一个节点且有很多边缘返回自身的族是无法解决问题的。想一想如何向大直径的图形（例如 n 循环或路径）添加许多边，而不将直径减小那么多。