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

设n阶无向简单图G=，其中边数满足：│E│>(n－1)(n－2)/2，证明G是连通图。

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

证明：假设G不是连通图，不妨设G有两个连通分支G1和G2，且│V1│=n1，│V2│=n2，易见n1+n2=n，由于n1≥1，n2≥1，所以n1*n2-( n1+n2)+1≥0 （*）而│E1│≤n1(n1-1)/2, │E2│≤n2(n2-1)/2，从而│E│=│E1│+│E2│≤n1(n1-1)/2+ n2(n2-1)/2由式（*）可得，n1(n1-1)/2+ n2(n2-1)/2≤[(n1+n2)2-3(n1+n2)+2]/2=(n-1)(n-2)/2，即│E│≤(n－1)(n－2)/2这与题设条件│E│>(n－1)(n－2)/2矛盾，故G 是连通图。

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

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

分享给朋友：

返回列表

上一篇：劳动力市场竞争中最重要的自我制衡机制是（）

下一篇：_______年颁布的《全日制小学语文教学大纲》，明确提出思想教育要求，适当减少识字量，强调阅读教学的重要性。