首先是一些定义：“累积图”是一个图，它的边随后被添加到其中。主题是方向问题（使无向图引导），当我们的目标是使最大出度尽可能低。
现在，他们给出了这个算法：“当边（u，v）被添加时，我们将把它从向外度较低的顶点指向较高的顶点。如果相等，则随机选择。“
例如，如果outdegree（u）=3和outdegree（v）=4，并且我们刚刚添加（u，v），算法将从u-->v引导它。如果它们的outdegree相等，则u、v和v、u都是可能的。
问题是证明O（log n）的上限为可能的最大出度。第二个问题是形成一个图，该算法将导致Omega（log n）最大出度。
到目前为止，我只能指出这个问题是错误的。
首先，我的朋友建议它们实际上是指o（log m）[m=边]，因为对于无向图中的n个顶点，我们最多有n（n-1）/2条边，这最终是o（n^2）。如果我们假设在一个完整的图中，每个节点的outdegree s都是log（n），那么我们得到了n*log（n）outdegrees的总数，它明显小于n^2（并且没有意义，因为所有outdegrees都应该和边的相加）。
我提出了一个算法，它证明了由于我们在两种情况都相等的情况下随机选择，所以最大可能的超出度是o（n）：
将n-1个顶点指向最后一个顶点（在所有方向都在同一方向的最坏情况下可能）。我们现在有n-1个顶点的外度为1，1的外度为0。然后重复上述步骤，完成n+（n-1+（n-2+…+1+0度）。
我可能理解错了，但这就是我到目前为止得到的。
编辑：老师编辑了问题，并说这个问题中的图形是一个森林（这意味着最多可以有v-1边）。
我相信我成功地证明了第一个问题：
想象一下：由于outdegree为2的唯一方法（最坏情况下）是连接outdegree为1的两个节点，因此我们必须有4个节点，其中a连接到b，c连接到d，以便添加a到c的边，并使其中一个节点的outdegree为2。因为这是创建outdegree为2的最小树，所以创建outdegree为3的唯一方法是构建两个相同的树并将它们再次连接在一起。如果我们重复这个过程直到达到n个顶点，我们会注意到我们最终得到1+2+4+8+…+logn作为我们的outdegree。
现在我一直在想第二个问题。
最佳答案
首先，因为m=O（n^2），我们有O（logm）=O（logn^2）=O（2*logn））=O（logn）换句话说，这个问题与你朋友提出的理由并不矛盾。
但您是对的，问题（如您所述）是不正确的——使用您所描述的过程，最坏的情况是o（n）。（但最高的优势是n-1，而不是你所写的n。）
也许问题实际上是要求你约束最大期望的出度？
关于algorithm - 通过该算法证明了无向图的最大出度上的O(log n)的上限变成有向图，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50728655/