当前位置：首页 > 离散数学(02324) > 正文内容

简单图G有n个顶点,e条边,若e> (n-1)(n-2)/2,证明G是连通图。

高老师2年前 (2024-03-26)离散数学(02324)11

简单图G有n个顶点,e条边,若e> (n-1)(n-2)/2,证明G是连通图。

证明:G= ,l Ⅴ l=n,若G不是连通图,则W(G)≥2。
非连通图仅当连通分量为2,且顶点集分别含n-1个顶点及1个顶点时,图中所能容纳的边数达到最大。此时边数e_max=(n-1)(n-2)/2,与已知矛盾。故G必是连通图。证毕

扫描二维码免费使用微信小程序搜题/刷题/查看解析。

版权声明：本文由翰林刷题小程序授权发布，如需转载请注明出处。

本文链接：https://doc.20230611.cn/post/429818.html

分享给朋友：

返回列表

上一篇：美国公民迈克在美国诉我国公民张三，美国法院依法作出判决，迈克申请我国法院执行该判决，下列选项正确的是（　）。

下一篇：单音节词一般都是单纯词。单纯词也有双音节或多音节的，包括______、联绵词、象声词和译音词几种情况。