algorithm - 证明无向图由该算法转化为有向图的最大出度的上界O(log n)

Question

首先是一些定义:“累积图”是后来添加边的图。主题是方向问题(使无向图有向)，我们的目标是使最大出度尽可能低。

现在，他们给出了这样的算法:“当添加边 (u,v) 时，我们将从出度较低的顶点指向较高的顶点。如果相等，则随机选择。”

例如，如果 outdegree(u) = 3 且 outdegree(v) = 4，并且我们刚刚添加 (u,v)，则算法将从 u-->v 引导它。如果出度相等，则u,v和v,u都是可能的。

问题是为可能的最大出度证明 O(log n) 的上限。第二个问题是形成一个图，其中该算法将导致 Omega(log n) 最大出度。

到目前为止，我只能指出这个问题是错误的。

首先，我的 friend 建议他们实际上是指 O(log m) [m = # of edges]，因为对于无向图中的 n 个顶点，我们最多有 n(n-1)/2 条边，最终为 O(n^2)。如果我们假设在一个完整的图中，每个节点的出度是 log(n)，我们得到总计 n*log(n) 出度，这明显小于 n^2(并且没有意义，因为所有出度应该相加到边数。)。

我想出了这个算法，它证明了因为我们在两者相等的情况下随机选择，所以最大可能的出度是 O(n):将 n-1 个顶点指向最后一个顶点(可能在所有方向都在同一方向的最坏情况下)。我们现在有 n-1 个顶点出度为 1，1 个顶点出度为 0。然后递归重复以完成 n+(n-1)+(n-2)+...+1+0 出度。

我可能对问题的理解有误，但这就是我目前的理解。

编辑:讲师编辑了问题并说这个问题中的图形是森林(这意味着您最多可以有 V-1 条边)。我相信我设法证明了第一个问题:

想象一下:由于出度为 2 的唯一方法(最坏情况)是连接两个出度为 1 的节点，我们必须有 4 个节点，其中 A 连接到 B，C 连接到 D为了从 A 到 C 添加一条边，并使其中一个的出度为 2。因为这是可能创建出度为 2 的最小树，所以创建出度为 3 的唯一方法是构建两棵相同的树并再次将它们连接在一起。如果我们重复这个过程直到我们到达 n 个顶点，我们会注意到我们最终得到 1+2+4+8+...+log n 作为我们的出度。

目前我一直在思考第二个问题。

Answer 1

首先，因为 m = O(n^2)，所以我们有 O(log m) = O(log n^2) = O(2 * log(n)) = O(log n)。换句话说，这个问题与你 friend 提出的推理并不矛盾。

但是您是对的，问题(如您所述)是不正确的——使用您描述的过程，最坏情况下的出度是 O(n)。 (但是最高出度是n-1，不是你写的n。)

也许问题实际上要求您限制最大预期出度？