具有n个节点的有向图中的最大边数是多少？

Question

具有n个节点的有向图中的最大边数是多少？有上限吗？

Answer 1

如果你有N节点,那么有N - 1定向边缘可以从它导出(到达每个其他节点).因此,最大边数是N * (N - 1).

Answer 2

在无向图(不包括多图)中,答案是n*(n-1)/ 2.在有向图中,边缘可以在两个节点之间的两个方向上发生,然后答案是n*(n-1).

Answer 3

有向图:

问题:有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

Answer 4

除了Chris Smith提供的直观解释之外,我们可以从不同的角度考虑为什么会出现这种情况:考虑无向图.

为了解答为什么在DIRECTED图中答案是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)Sum 中有条件,因此这一系列中的Sum的平均值为((n-1)+1)/2{(last + first)/ 2},Sum = n(n-1)/2

Answer 5

如果图形不是多图形,那么它显然是n*(n-1),因为每个节点最多可以具有到每个其他节点的边缘.如果这是一个多图,那么没有最大限制.

Answer 6

换句话说：

完整图是无向图，其中每对不同的顶点都有唯一的边连接它们。这是直观的，因为您基本上是从 n 个顶点的集合中选择 2 个顶点。

nC2 = n!/(n-2)!*2! = n(n-1)/2

这是无向图可以拥有的最大边数。现在，对于有向图，每条边都转换为两条有向边。因此只需将之前的结果乘以 2 即可。这给出了结果：n(n-1)