具有n个顶点的二分图有多少条边

具有n个顶点的二分图有多少条边

最多 (n^2)/4 条边吧！
这个可以自己算出来啊，很好算的！我给你推导一下二分图的最大边数吧！
设总共有n个顶点 ->
首先，对于完全图来说总共有边数：( n(n-1) )/2 条 ->
将完全图的顶点平分时二分图边数最多，即二分为各有n/2个顶点的集合 ->
一个集合中的每个点之间都没有边相连接，相比完全图要减掉每个集合的不存在边 ->
两个集合中的顶点数都是n/2 ->
两个集合中都会少：( (n/2) ( (n/2) - 1 ) )/2 条边 ->
两个集合一共减少了：(n/2) ( (n/2) - 1 ) 条边 ->
二分图的边数为完全图边数减去少了的边 ->
( n(n-1) )/2 - (n/2) ( (n/2) - 1 ) ，化简得到 ->
(n^2)/4
即顶点数为n的二分图最多(n^2)/4条边。

=====================
纯手打，自算，有用就采纳吧~

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息