试题出自试卷《暨南大学2020年830数据结构B真题解析》

9

本题考查非连通无向图的性质。
若想最少的顶点连接最多的边，则每一个顶点应当和除了本身之外的每个顶点相连。又因为是一个无向图，所以第1个顶点和n-1个顶点相连，共n-1条边；第2个顶点和n-2个顶点相连，共n-2个边，依次类推，第n-1个顶点和1个顶点相连，共一个边。因此边数e=1+2+……+（n-1）=1/2*n*（n-1），带入e=28，求解得出n=8。但此时图是连通的状态，题干要求非连通图，所以顶点的个数应当加1个，即共有9个顶点。