设n阶无向简单图G有m条边,已知m>=1/2(n-1)(n-2)+1,证明G必连通

rhj1986 1年前 已收到2个回答 举报
赞

avril4ever 幼苗

共回答了24个问题采纳率：87.5% 举报

反之若不连通,设此图可以分成不连通的两部分,分别有a个和n-a个顶点,则这个图边数最多不会超过a(a-1)/2+(n-a)(n-a-1)/2条（也就是两部分都是完全图）.可以用不等式验证这个数小于等于1/2(n-1)(n-2),与已知m>=1/2(n-1)(n-2)+1矛盾.所以必连通

1年前 追问

2

rhj1986 举报

看不懂啊 能写明白一点吗 谢谢

举报 avril4ever

上面有个细节错了，应该是“可以用不等式验证这个数小于等于1/2(n-1)(n-2) “ 简单的说，思路就是如果一个图能分成两个不连通的部分的话，边数最多的情况是两个图都是完全图。而即使两部分都是完全图，边数也不会超过1/2(n-1)(n-2)+1，边最多的情况是1个单点和一个n-1阶完全图的时候

zzdqy 春芽

共回答了1个问题 举报

当n阶无向图简单图G为完全图时，G必连通，此时有m=\frac{1}{2}n(n-1)。此时图G的边连通度\lambda (G)=n-1，则当删除t < n-1，图G必连通，即m > \frac{1}{2}n(n-1) - (n-1)=\frac{1}{2}(n-1)(n-2)时图G必连通。即证当m \geq \frac{1}{2}(n-1)(n-2)时，图G必连通。

1年前

0
可能相似的问题

你能帮帮他们吗

精彩回答

Copyright © 2024 YULUCN.COM - 雨露学习互助 - 18 q. 0.022 s. - webmaster@yulucn.com