【正确答案】：证明:G=
非连通图仅当连通分量为2,且顶点集分别含n-1个顶点及1个顶点时,图中所能容纳的边数达到最大。此时边数emax=(n-1)(n-2)/2,与已知矛盾。故G必是连通图。 证毕
简单图G有n个顶点,e条边,若e> (n-1)(n-2)/2,证明G是连通图。
- 2024-08-04 00:07:48
- 离散数学(02324)
简单图G有n个顶点,e条边,若e> (n-1)(n-2)/2,证明G是连通图。
【正确答案】：证明:G= ,l Ⅴ l=n,若G不是连通图,则W(G)≥2。
非连通图仅当连通分量为2,且顶点集分别含n-1个顶点及1个顶点时,图中所能容纳的边数达到最大。此时边数emax=(n-1)(n-2)/2,与已知矛盾。故G必是连通图。 证毕
【正确答案】：证明:G=
非连通图仅当连通分量为2,且顶点集分别含n-1个顶点及1个顶点时,图中所能容纳的边数达到最大。此时边数emax=(n-1)(n-2)/2,与已知矛盾。故G必是连通图。 证毕