logo标签列表

一个有 n 个节点的有向图最多能有多少条边？

mathgraphmax
89
一个有n个节点的有向图中，最多能有多少条边？是否存在上限？
@LiorKogan 那“算法”部分怎么样？ - Loolooii
2
抱歉，我没有看到任何“算法”部分。只是一个组合问题。 - Lior Kogan
2
我投票关闭此问题，因为它与编程无关。 - Brian Tompsett - 汤莱恩
4
我正在投票关闭此问题，因为它并不是一个具体的编程问题。 - Nick stands with Ukraine
12个回答
-1

正确答案是 n*(n-1)/2。每条边被计算了两次，因此要除以2。完全图具有最大数量的边，即由 n 选 2 = n*(n-1)/2 给出。

1
只有在图中禁止有向环的情况下才是真的。 - István Zachar
13
这仅适用于无向图。 - Bandicoot
2
对于无向图，N*(N-1)/2是正确的，因为每个节点的边数逐渐减少，从(n-1),(n-2),(n-3),....,1（所有边数总和为n(n-1)/2）。然而，对于有向图，您应该考虑每个顶点的出边，因此是n(n-1)。 - Shailesh Pratapwar
-1

也可以被视为选择节点对的方式数，即 n 选 2 = n(n-1)/2。如果仅任何一对可以有一条边，则为真。否则乘以2

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接