证明无向图由该算法转化为有向图的最大出度的上界O(log n)
Prove upper bound of O(log n) on the maximum outdegree of an undirected graph turned into a directed one by this algorithm
首先是一些定义："accumulated graph" 是一个图，其中边后来被添加到它。题目是方向问题（使无向图有向），当我们的目标是使最大出度尽可能低。
现在，他们给出了这个算法："When the edge (u,v) is added, we will direct it from the vertex with the lower outdegree to the higher one. if equal, choose randomly."
例如，如果 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 作为我们的出度。
现在我一直在想第二个问题
首先，因为m = O(n^2)，我们有O(log m) = O(log n^2) = O(2 * log(n)) = O(log n) .换句话说，这个问题与你朋友提出的推理不矛盾。
但是你是对的，问题（正如你所说的）是不正确的——最坏情况的出度是 O(n)，使用你描述的过程。 （但是最高出度是n-1，不是你写的n。）
也许问题实际上是要求您限制最大预期 出度？
我强烈怀疑预期的问题是限制此在线算法与离线最优算法之间的竞争比（例如，如果离线最优算法的最大输出度为 1，则在线解决方案的最大输出度为 O(log n); 若离线最优解的最大出度为√n，则在线解的最大出度为O((√n) log n))。下界很容易（参见 union-by-rank union-find 的下界以获得灵感），我猜想上界也是可以达到的。
首先是一些定义："accumulated graph" 是一个图，其中边后来被添加到它。题目是方向问题（使无向图有向），当我们的目标是使最大出度尽可能低。
现在，他们给出了这个算法："When the edge (u,v) is added, we will direct it from the vertex with the lower outdegree to the higher one. if equal, choose randomly."
例如，如果 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 作为我们的出度。
现在我一直在想第二个问题
首先，因为m = O(n^2)，我们有O(log m) = O(log n^2) = O(2 * log(n)) = O(log n) .换句话说，这个问题与你朋友提出的推理不矛盾。
但是你是对的，问题（正如你所说的）是不正确的——最坏情况的出度是 O(n)，使用你描述的过程。 （但是最高出度是n-1，不是你写的n。）
也许问题实际上是要求您限制最大预期 出度？
我强烈怀疑预期的问题是限制此在线算法与离线最优算法之间的竞争比（例如，如果离线最优算法的最大输出度为 1，则在线解决方案的最大输出度为 O(log n); 若离线最优解的最大出度为√n，则在线解的最大出度为O((√n) log n))。下界很容易（参见 union-by-rank union-find 的下界以获得灵感），我猜想上界也是可以达到的。