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) 最大出度。

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

首先，我的朋友建议他们实际上是指 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 作为我们的出度。

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

标签： algorithmgraphorientationassignundirected-graph

Answer 1

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

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

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