logo标签列表

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

mathgraphmax
89
一个有n个节点的有向图中，最多能有多少条边？是否存在上限？
@LiorKogan 那“算法”部分怎么样？ - Loolooii
2
抱歉，我没有看到任何“算法”部分。只是一个组合问题。 - Lior Kogan
2
我投票关闭此问题，因为它与编程无关。 - Brian Tompsett - 汤莱恩
4
我正在投票关闭此问题，因为它并不是一个具体的编程问题。 - Nick stands with Ukraine
12个回答
110
如果你有 N 个节点，那么可以从每个节点指向其他节点，共有 N - 1 条有向边。因此，最大的边数是 N * (N - 1)。
16
正确。如果允许边从一个节点指向自身，则最大值为 N^2。 - ypercubeᵀᴹ
3
如果你所讨论的是无向图，那么@M.A是正确的。但在有向图中，边(A,B)与边(B,A)是不同的。 - Bob9630
39
在有向图中，边的数量为N*(N-1)。在无向图中，边的数量为(N*(N-1))/2。 - Charles Chow
假设图是有向的前提下。 - moldovean
1
和 @ypercube 的想法一样，答案是正确的，但没有考虑有向图中的自环。 - algarecu
显示剩余3条评论
57

有向图：

问题：一个有向图，如果有n个顶点，最多能有多少条边？

  • 假设没有自环。
  • 假设每个起始顶点到结束顶点最多只有一条边。

每条边都由其起始顶点和结束顶点指定。对于起始顶点，有n种选择。因为没有自环，所以对于结束顶点，有n-1种选择。将它们相乘就是所有可能的选择数。

答案：n(n−1)

无向图：

问题：一个无向图，如果有n个顶点，最多能有多少条边？

  • 假设没有自环。
  • 假设每个起始顶点到结束顶点最多只有一条边。

在无向图中，每条边由其两个端点指定，且顺序不重要。因此，边的数量等于从顶点集合中选择大小为2的子集的数量。由于顶点集合的大小为n，因此这样的子集数量由二项式系数C(n,2)（也称为“n取2”）给出。使用二项式系数的公式，C(n,2) = n(n-1)/2。

答案：(n*(n-1))/2

28

在无向图中（不包括多重图），答案是n*(n-1)/2。在有向图中，两个节点之间可能存在双向边，那么答案就是n*(n-1)。

24

除了 Chris Smith 提供的直观解释外，我们可以从不同的角度考虑为什么这是这种情况：考虑无向图。

要看到为什么在有向图中答案是n*(n-1)，可以考虑一个无向图（这意味着如果两个节点（A和B）之间存在链接，则可以从A到B和从B到A都可以），无向图中边的最大数量是n(n-1)/2，很明显，在有向图中有两倍的数量。

好的，你可能会问，但是在无向 图中为什么最多只能有n(n-1)/2条边呢？ 为此，考虑 n 个点（节点）并问从第一个点可以做多少条边。显然，有n-1 条边。现在，如果已经连接了第一个点，那么从第二个点可以画多少条边呢？由于第一个点和第二个点已经连通，因此可以做n-2 条边。以此类推。所以所有边的总和为：

Sum = (n-1)+(n-2)+(n-3)+...+3+2+1

由于这个求和式中有(n-1)个数，而在这种序列中求和的平均值是((n-1)+0)/2 {(最后一个数 + 第一个数)/2}，所以Sum = n(n-1)/2

6

如果图不是多重图，则明显为n * (n - 1)，因为每个节点最多可以有向每个其他节点的边缘。如果这是一个多重图，则没有最大限制。

5
换句话说：
完全图是一种无向图，其中每对不同的顶点都有一条唯一的边连接它们。这在直觉上很容易理解，因为你基本上是从 n 个顶点的集合中选择 2 个顶点。
nC2 = n!/(n-2)!*2! = n(n-1)/2

这是无向图可能具有的最大边数。对于有向图，每条边变为两条有向边。因此，只需将先前的结果乘以二即可。这给出了结果：n(n-1)。
2
在一个有N个顶点的有向图中，每个顶点可以连接到图中的其他N-1个顶点（假设没有自环）。因此，边的总数可以是N(N-1)。
1
这个回答没有提供任何其他回答中已经存在的内容。此外，/2 是用于无向图的。 - Teepeemm
1
在带有自环的图中。
max edges= n*n

例如，我们有4个节点（顶点）。
4 nodes = 16 edges= 4*4
0

如果不允许多重边，那么在图中可能会有高达 n(n-1)/2 条边。

通过给顶点打上标签 1,2,...,n ，并且仅当 i>j 时从 i 到 j 存在一条边，我们就可以实现这个数量级。

请参见这里。

-1

无向图的边数为N^2。简单来说，每个节点有N条边的选择（包括自己），因此总共有N*N个节点。

N^2包括方向的重复，因此计算的边数比实际边数多。在无向图中，{1,2}与{2,1}相同。在一个无向图中，它是n(n-1)/2。 - BugShotGG
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接