当前位置：首页 >
离散数学(02324) > 正文内容
简单图G有n个顶点,e条边,若e> (n-1)(n-2)/2,证明G是连通图。
简单图G有n个顶点,e条边,若e> (n-1)(n-2)/2,证明G是连通图。
证明:G=
非连通图仅当连通分量为2,且顶点集分别含n-1个顶点及1个顶点时,图中所能容纳的边数达到最大。此时边数emax=(n-1)(n-2)/2,与已知矛盾。故G必是连通图。 证毕
扫描二维码免费使用微信小程序搜题/刷题/查看解析。
版权声明：本文由翰林刷题小程序授权发布，如需转载请注明出处。