blocks|key|1895722|text|如果您有N节点，则存在可从其引出的N+-+1定向边(每隔一个节点)。因此，最大边数为N+*+(N+-+1)。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1895723|entityMap^0|4|1|H|5|16|B|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]|$9|K|A|L|B|C]|$9|M|A|N|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|O|8|@]|D|@]|E|$]]]|G|$]]

If you have <code>N</code> nodes, there are <code>N - 1</code> directed edges than can lead from it (going to every other node). Therefore, the maximum number of edges is <code>N * (N - 1)</code>.

blocks|key|1895958|text|有向图：|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|1895959|+number+：n个顶点的有向图的最大边数是多少？|1895960|假设没有self-loops.|1895961|Assume，从给定的起始顶点到给定的结束顶点至多只有一条边。|unordered-list-item|1895962|1895963|1895964|1895965|1895966|每条边都由其起始顶点和结束顶点指定。对于起始顶点，有n种选择。由于没有自循环，因此有n-1个选择作为结束顶点。将这些相乘计算所有可能的选择。|blockquote|1895967|1895968|1895969|应答：n(n−1)|CODE|1895970|无向图|1895971|+number+：有n个顶点的无向图的最大边数是多少？|1895972|1895973|1895974|1895975|1895976|1895977|1895978|在无向图中，每条边由它的两个端点指定，顺序无关紧要。因此，边的数量是从顶点集中选择的大小为2的子集的数量。由于顶点集的大小为n，因此这样的子集的数量由二项式系数C(n,2)+(也称为"n选择2")给出。使用二项式系数的公式，C(n,2)+=+n(n-1)/2。|1895979|1895980|1895981|应答：(n*(n-1))/2|1895982|entityMap^0|0|4|0|0|8|0|0|0|0|0|0|0|0|0|0|0|2|3|6|0|0|3|0|0|8|0|0|0|0|0|0|0|0|0|0|0|2|3|B|0^^$0|@$1|2|3|4|5|6|7|1G|8|@$9|1H|A|1I|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|1J|8|@$9|1K|A|1L|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|1M|8|@]|D|@]|E|$]]|$1|J|3|K|5|L|7|1N|8|@]|D|@]|E|$]]|$1|M|3|-4|5|L|7|1O|8|@]|D|@]|E|$]]|$1|N|3|-4|5|6|7|1P|8|@]|D|@]|E|$]]|$1|O|3|-4|5|6|7|1Q|8|@]|D|@]|E|$]]|$1|P|3|-4|5|6|7|1R|8|@]|D|@]|E|$]]|$1|Q|3|R|5|S|7|1S|8|@]|D|@]|E|$]]|$1|T|3|-4|5|6|7|1T|8|@]|D|@]|E|$]]|$1|U|3|-4|5|6|7|1U|8|@]|D|@]|E|$]]|$1|V|3|W|5|6|7|1V|8|@$9|1W|A|1X|B|C]|$9|1Y|A|1Z|B|X]]|D|@]|E|$]]|$1|Y|3|Z|5|6|7|20|8|@$9|21|A|22|B|C]]|D|@]|E|$]]|$1|10|3|11|5|6|7|23|8|@$9|24|A|25|B|C]]|D|@]|E|$]]|$1|12|3|I|5|6|7|26|8|@]|D|@]|E|$]]|$1|13|3|K|5|L|7|27|8|@]|D|@]|E|$]]|$1|14|3|-4|5|L|7|28|8|@]|D|@]|E|$]]|$1|15|3|-4|5|6|7|29|8|@]|D|@]|E|$]]|$1|16|3|-4|5|6|7|2A|8|@]|D|@]|E|$]]|$1|17|3|-4|5|6|7|2B|8|@]|D|@]|E|$]]|$1|18|3|19|5|S|7|2C|8|@]|D|@]|E|$]]|$1|1A|3|-4|5|6|7|2D|8|@]|D|@]|E|$]]|$1|1B|3|-4|5|6|7|2E|8|@]|D|@]|E|$]]|$1|1C|3|1D|5|6|7|2F|8|@$9|2G|A|2H|B|C]|$9|2I|A|2J|B|X]]|D|@]|E|$]]|$1|1E|3|-4|5|6|7|2K|8|@]|D|@]|E|$]]]|1F|$]]

<h2>Directed graph:</h2>

Question: What's the maximum number of edges in a directed graph with n vertices?

<ul>
<li>Assume there are no self-loops.</li>
<li>Assume there there is at most one edge from a given start vertex to a given end vertex.</li>
</ul>

<blockquote>
 Each edge is specified by its start vertex and end vertex. There are n
 choices for the start vertex. Since there are no self-loops, there are
 n-1 choices for the end vertex. Multiplying these together counts all
 possible choices.
</blockquote>

Answer: <code>n(n−1)</code>

<h2>Undirected graph</h2>

Question: What's the maximum number of edges in an undirected graph with n vertices?

<ul>
<li>Assume there are no self-loops.</li>
<li>Assume there there is at most one edge from a given start vertex to a given end vertex.</li>
</ul>

<blockquote>
 In an undirected graph, each edge is specified by its two endpoints
 and order doesn't matter. The number of edges is therefore the number
 of subsets of size 2 chosen from the set of vertices. Since the set of
 vertices has size n, the number of such subsets is given by the
 binomial coefficient C(n,2) (also known as "n choose 2"). Using the
 formula for binomial coefficients, C(n,2) = n(n-1)/2.
</blockquote>

Answer: <code>(n*(n-1))/2</code>

blocks|key|1092688|text|在无向图(不包括多重图)中，答案是n*(n-1)/2，在有向图中，边可以出现在两个节点之间的两个方向上，则答案是n*(n-1)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1092689|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

In an undirected graph (excluding multigraphs), the answer is n*(n-1)/2. In a directed graph an edge may occur in both directions between two nodes, then the answer is n*(n-1).

blocks|key|4759425|text|除了Chris+Smith提供的直观解释之外，我们还可以从不同的角度考虑为什么会出现这种情况:考虑无向图。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4759426|要了解为什么在有向图中答案是n*(n-1)，请考虑一个无向图(这只意味着如果两个节点(A和B)之间存在链接，则可以双向进行:从A到B和从B到A)。无向图中的最大边数是n(n-1)/2，显然在有向图中有两倍于的。|offset|length|style|BOLD|CODE|4759427|很好，你可能会问，但是为什么在无向图__中有最大的n(n-1)/2边？为此，考虑n个点(节点)，并询问从第一个点可以生成多少条边。显然，n-1边缘。现在，假设您连接了第一个点，那么一个点可以从第二个点绘制多少条边？由于第一个点和第二个点已经是连接的，所以可以使用n-2边。诸若此类。所以所有边的总和是：|4759428|Sum+=+(n-1)%2B(n-2)%2B(n-3)%2B...%2B3%2B2%2B1+|code-block|syntax|javascript|4759429|由于Sum中有最后一个项，并且这样的级数中Sum的平均是((n-1)%2B0)/2+{(最后一个%2B第一个)/2}，Sum+=+n(n-1)/2|4759430|entityMap^0|0|7|2|2V|1|E|7|2B|8|0|F|3|3D|U|P|8|1W|3|3N|3|0|0|0|1X|S|B|1J|E|0^^$0|@$1|2|3|4|5|6|7|T|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|U|8|@$D|V|E|W|F|G]|$D|X|E|Y|F|G]|$D|Z|E|10|F|H]|$D|11|E|12|F|H]]|9|@]|A|$]]|$1|I|3|J|5|6|7|13|8|@$D|14|E|15|F|G]|$D|16|E|17|F|G]|$D|18|E|19|F|H]|$D|1A|E|1B|F|H]|$D|1C|E|1D|F|H]]|9|@]|A|$]]|$1|K|3|L|5|M|7|1E|8|@]|9|@]|A|$N|O]]|$1|P|3|Q|5|6|7|1F|8|@$D|1G|E|1H|F|G]|$D|1I|E|1J|F|H]|$D|1K|E|1L|F|H]]|9|@]|A|$]]|$1|R|3|-4|5|6|7|1M|8|@]|9|@]|A|$]]]|S|$]]

In addition to the intuitive explanation Chris Smith has provided, we can consider why this is the case from a different perspective: considering undirected graphs.
To see why in a DIRECTED graph the answer is <code>n*(n-1)</code>, consider an undirected graph (which simply means that if there is a link between two nodes (A and B) then you can go in both ways: from A to B and from B to A). The maximum number of edges in an undirected graph is <code>n(n-1)/2</code> and obviously in a directed graph there are twice as many.
Good, you might ask, but why are there a maximum of <code>n(n-1)/2</code> edges in an undirected graph?
For that, Consider n points (nodes) and ask how many edges can one make from the first point. Obviously, <code>n-1</code> edges. Now how many edges can one draw from the second point, given that you connected the first point? Since the first and the second point are already connected, there are <code>n-2</code> edges that can be done. And so on. So the sum of all edges is:
<pre><code>Sum = (n-1)+(n-2)+(n-3)+...+3+2+1 
</code></pre>
Since there are <code>(n-1)</code> terms in the Sum, and the average of Sum in such a series is <code>((n-1)+0)/2</code> {(last + first)/2}, <code>Sum = n(n-1)/2</code>

blocks|key|3158939|text|如果图不是多图，那么它显然是n*+(n+-+1)，因为每个节点至多可以有到每个其他节点的边。如果这是一个多重图，则没有最大限制。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3158940|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

If the graph is not a multi graph then it is clearly n * (n - 1), as each node can at most have edges to every other node. If this is a multigraph, then there is no max limit.

blocks|key|4759513|text|换一种说法：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4759514|一个完整的图是一个无向图，其中每对不同的顶点都有一条唯一的边连接它们。这是直观的，您基本上是从n个顶点的集合中选择2个顶点。|4759515|nC2+=+n!/(n-2)!*2!+=+n(n-1)/2|code-block|syntax|javascript|4759516|这是无向图可以拥有的最大边数。现在，对于有向图，每条边都转换为两条有向边。所以只要把之前的结果乘以2即可。结果是：n(n-1)|offset|length|style|BOLD|4759517|entityMap^0|0|0|0|1L|6|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|S|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|T|8|@$K|U|L|V|M|N]]|9|@]|A|$]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

Putting it another way: 

A complete graph is an undirected graph where each distinct pair of vertices has an unique edge connecting them. This is intuitive in the sense that, you are basically choosing 2 vertices from a collection of n vertices. 

<pre><code>nC2 = n!/(n-2)!*2! = n(n-1)/2
</code></pre>

This is the maximum number of edges an undirected graph can have. Now, for directed graph, each edge converts into two directed edges. So just multiply the previous result with two. That gives you the result: n(n-1)

blocks|key|4759478|text|在一个有N个顶点的有向图中，每个顶点可以连接到图中的N-1个其他顶点(假设没有自环)。因此，边的总数可以是N(N-1)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4759479|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

In a directed graph having N vertices, each vertex can connect to N-1 other vertices in the graph(Assuming, no self loop). Hence, the total number of edges can be are N(N-1).

blocks|key|1899724|text|在具有自循环的图中|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1899725|max+edges=+n*n|code-block|syntax|javascript|1899726|比如我们有4个节点(顶点)|1899727|4+nodes+=+16+edges=+4*4|1899728|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

In the graph with self loop 

<pre><code>max edges= n*n
</code></pre>

such as we have 4 nodes(vertex)

<pre><code>4 nodes = 16 edges= 4*4
</code></pre>

blocks|key|1092638|text|如果不允许多边，则图形中可以有与n(n-1)/2边一样多的边。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1092639|这是可以实现的，如果我们将顶点标记为1,2,...,n，并且存在从i到j的边当且仅当i>j。|1092640|参见here。|1092641|entityMap|0|LINK|mutability|MUTABLE|url|http://www.csun.edu/~jnoga/comp610/h1a.pdf^0|G|8|0|I|9|X|1|Z|1|16|3|0|2|4|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@$9|S|A|T|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|U|8|@$9|V|A|W|B|C]|$9|X|A|Y|B|C]|$9|Z|A|10|B|C]|$9|11|A|12|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|13|8|@]|D|@$9|14|A|15|1|16]]|E|$]]|$1|J|3|-4|5|6|7|17|8|@]|D|@]|E|$]]]|K|$L|$5|M|N|O|E|$P|Q]]]]

There can be as many as <code>n(n-1)/2</code> edges in the graph if not multi-edge is allowed.

And this is achievable if we label the vertices <code>1,2,...,n</code> and there's an edge from <code>i</code> to <code>j</code> iff <code>i&gt;j</code>.

See <a href="http://www.csun.edu/~jnoga/comp610/h1a.pdf" rel="nofollow">here</a>.

blocks|key|3158982|text|正确的答案是n*(n-1)/2。每条边都被计算了两次，因此除以2。一个完整的图具有最大的边数，它由n选择2=+n*(n-1)/2给出。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3158983|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

The correct answer is n*(n-1)/2. Each edge has been counted twice, hence the division by 2. A complete graph has the maximum number of edges, which is given by n choose 2 = n*(n-1)/2.

blocks|key|1895776|text|也可以看作是选择结点对的方式数n+choose+2=+n(n-1)/2。如果任何结点对只能有一条边，则为True。乘以2，否则|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1895777|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Can also be thought of as the number of ways of choosing pairs of nodes n choose 2 = n(n-1)/2. True if only any pair can have only one edge. Multiply by 2 otherwise

blocks|key|4759365|text|无向是N%5E2。简单-每个节点有N个边选项(包括他自己)，总共有N个节点，因此是N*N|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4759366|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Undirected is N^2. Simple - every node has N options of edges (himself included), total of N nodes thus N*N

What is the maximum number of edges in a directed graph with n nodes? Is there any upper bound?

What is the maximum number of edges in a directed graph with n nodes?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋 

腾讯云代码助手

CODING DevOps

Cloud Studio

SDK中心

API中心

命令行工具

N个节点的有向图的最大边数是多少？有没有上限？

问N个节点的有向图的最大边数是多少？
EN

回答 12

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问N个节点的有向图的最大边数是多少？EN

回答 12

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问N个节点的有向图的最大边数是多少？
EN