对于哪些n值，下面的图是二分图kncnwnqn
答案:1 悬赏:0 手机版
解决时间 2021-01-17 09:45
- 提问者网友：黑米和小志
- 2021-01-16 14:31
对于哪些n值，下面的图是二分图kncnwnqn
最佳答案
- 五星知识达人网友：未来江山和你
- 2021-01-16 15:42
最多 (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条边。
=====================
纯手打，自算，有用就吧~
这个可以自己算出来啊，很好算的！我给你推导一下二分图的最大边数吧！
设总共有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条边。
=====================
纯手打，自算，有用就吧~
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯