一个单位图可以有几个边缘？

Question

单膜图是一个有向图，因此，从任何一个顶点到任何其他顶点，最多都有一个简单的路径。

单位图可以具有周期。例如，双重链接列表（不是圆形列表！）是一个单位图。如果列表具有$ n $元素，则该图的长度为2 $ n-1 $循环，总计$ 2（N-1）$。

带有$ n $顶点的单层图中的最大边数是多少？渐近约束将做（例如$ o（n）$或$ theta（n^2）$）。

_{受到启发 在称重的单位图中找到最短的路径;在 我的证明, ，我最初想声称边缘的数量为$ O（n）$，但随后意识到界限循环数已经足够了。}

Answer 1

单膜图可以具有$ theta（n^2）$边缘。有一种众所周知的图形，具有$ n^2/4 $的边缘。

考虑一个完整的双方图，带有方向的边缘$ forall（i，j） in [1，m]^2，a_i rightarrow b_j $。该图是单一的，没有周期：其所有路径的长度$ 1 $。它具有$ 200万美元的顶点和$ m^2 $边缘。

_{（后续问题：这个比率最大吗？可能不是，但我没有另一个示例。此示例是最大的，因为您在现有节点之间添加的任何一个边缘都会破坏单一属性的属性。）}

Answer 2

我不知道是否有超过$ frac {n^2} {4} $ edges上的单一图形，但这是一个参数，显示不超过$ frac {n^2} {2} {2} {2}+3 $边缘是可能的：

假设$ g =（v，e）$是一个单位图，以至于$ | e | e | geq frac {n^2} {2} {2}+3 $。

根据PigeOnhole原理，存在V $中存在$ V ，因此$$ d _ { text {in}}}（v） geq frac {n} {2} {2}+1 $$

表示$ u = {u in V mid（u，v） in E } $

请注意，如果v setMinus {v } $中有一个顶点$ x ，则$ neq u_2 in u：（x，u_1），（x，u_2） in E $$

然后，该图不会是单一的（因为$（x to u_1 to v）$和$（x to u_2 to v）$都是有效的路径）。

这意味着（从$ {v } times u $添加边缘）：$$ | e cap（v times u）| leq2 | u | $$

因此，$ u $的顶点的平均水平最多是2，因此：$$ | e | = | e cap（v times u）|+| e cap（v times（v setminus） u））| $$ $ $ leq 2 | u |+n | v setMinus u | leq 2（ frac {n} {2} {2} +1）+n（ frac {n} {2} {2} -1 ）< frac {n^2} {2}+3 $$

$ square $