只有一个节点的图的直径是多少？
What is the diameter of a graph with just one noed?
我正在尝试为我的分布式算法课程中的问题找到答案，为此我想弄清楚一些事情。
- 一个节点有一条边的图的直径是多少？是 1 还是 0？
如果您有兴趣，我试图找到答案的问题是：
In terms of n (# nodes), the number of messages (= diam * |E|) used in
the FloodMax algorithm is easily seen to be O(n^3). Produce a class of
digraphs in which the product (diam * |E|) really is Omega(n^3).
我想出的有向图是一个只有一个节点的图，它有一条到自己的有向边。那样|E|将是 1，即 n^2，并且 如果直径为 1，它也满足第二个条件，即直径 = 1 = n。所以它给了我 class 个有向图，消息复杂度为 Omega(n^3)。
那么我的想法是否正确，在这样的图形中直径是 1？
两件事：
根据this好像是0，说的是：
In other words, a graph's diameter is the largest number of vertices which must be traversed in order to travel from one vertex to another when paths which backtrack, detour, or loop are excluded from consideration.
你对给定问题的解决方案应该描述如何构建一个图（或者更确切地说是什么类型的已知图具有 属性，因为它说 "produce a class"） 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) => 您的解决方案仍然有效！
因此，即使您也考虑了带有循环的路径，我仍然认为您的解决方案不正确。
O(n^3) 和 Omega(n^3) 并不意味着 cn^3，并且在 n 的有限多个非零值处为 0 的函数在 O(n^3) 中没有问题) 和欧米茄 (n^3)。例如，n^3-100 在两者中，n^3-100n^2 也是。出于渐近学的目的，单个示例的直径是多少并不重要。你被要求找到一个直径足够大的无限图族，并且图的单个示例不影响无限族的渐近性。
也就是说，可以通过几种方式定义图（或强连通有向图）的直径。一种可能性是从 v 到 w 并返回所有对 v 和 w 的往返长度的最小值的一半的最大值，并且当 v 和 w 重合时为 0。所以，一个顶点的图的直径为0.
同样，这对您构建无限大家庭的练习毫无帮助。一个只有一个节点且有很多边返回自身的族不会削减它。想一想如何在不减小直径的情况下向具有大直径的图形（例如 n 循环或路径）添加许多边。
我正在尝试为我的分布式算法课程中的问题找到答案，为此我想弄清楚一些事情。
- 一个节点有一条边的图的直径是多少？是 1 还是 0？
如果您有兴趣，我试图找到答案的问题是：
In terms of n (# nodes), the number of messages (= diam * |E|) used in the FloodMax algorithm is easily seen to be O(n^3). Produce a class of digraphs in which the product (diam * |E|) really is Omega(n^3).
我想出的有向图是一个只有一个节点的图，它有一条到自己的有向边。那样|E|将是 1，即 n^2，并且 如果直径为 1，它也满足第二个条件，即直径 = 1 = n。所以它给了我 class 个有向图，消息复杂度为 Omega(n^3)。
那么我的想法是否正确，在这样的图形中直径是 1？
两件事：
根据this好像是0，说的是：
In other words, a graph's diameter is the largest number of vertices which must be traversed in order to travel from one vertex to another when paths which backtrack, detour, or loop are excluded from consideration.
你对给定问题的解决方案应该描述如何构建一个图（或者更确切地说是什么类型的已知图具有 属性，因为它说 "produce a class"）
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) => 您的解决方案仍然有效！
因此，即使您也考虑了带有循环的路径，我仍然认为您的解决方案不正确。
O(n^3) 和 Omega(n^3) 并不意味着 cn^3，并且在 n 的有限多个非零值处为 0 的函数在 O(n^3) 中没有问题) 和欧米茄 (n^3)。例如，n^3-100 在两者中，n^3-100n^2 也是。出于渐近学的目的，单个示例的直径是多少并不重要。你被要求找到一个直径足够大的无限图族，并且图的单个示例不影响无限族的渐近性。
也就是说，可以通过几种方式定义图（或强连通有向图）的直径。一种可能性是从 v 到 w 并返回所有对 v 和 w 的往返长度的最小值的一半的最大值，并且当 v 和 w 重合时为 0。所以，一个顶点的图的直径为0.
同样，这对您构建无限大家庭的练习毫无帮助。一个只有一个节点且有很多边返回自身的族不会削减它。想一想如何在不减小直径的情况下向具有大直径的图形（例如 n 循环或路径）添加许多边。