Question

一道数据结构的填空题题,若非连通无向图G含有21条边,则G的顶点个数至少为多少?PS：但没思路.别单纯只给答案,思路,这

Answer 1

如果一个图允许有多重边,则21个自环就可以解决问题,所以连通图只需要一个顶点,非连通图2个顶点.

当然一般是说不允许两个顶点间有多条边的,则非连通图至少分成两个连通子图,每一子图若干顶点.任何一个连通部分若有n个顶点,则最多有n*(n-1)/2条边,可以通过不太复杂的分析得到,平分边或者多于两个子图会增加顶点数,这样结论就是：

8个顶点,7个顶点之间点点连接,外加一个孤立顶点.