企源知识库

一个n阶(n>2)简单非连通图的边的最大个数是_________。
【正确答案】：(n-1)(n-2)/2
【题目解析】：可以借助完全图来进行解决。完全图是简单无向图，每对不同的顶点之间都恰连有一条边相连，那么n阶完全图的边数为n(n-1)/2，要改造成为非连通图，则只需要至少制造出一个孤立结点即可，即去掉n-1条边，于是可得n(n-1)/2-(n-1)=(n-1)(n-2)/2，故一个n阶(n>2)简单非连通图的边的最大个数是(n-1)(n-2)/2。