题17

题17

题目

Q:【2010 统考真题】若无向图 中含有 7 个顶点,要保证图 在任何情况下都是连通的，则需要的边数最少是 ( ).
A. 6
B. 15
C. 16
D. 21

分析

A:无向完全图的边数是确定的，可以使用公式 n(n-1)/2 来计算；
而无向连通图的边数是不确定的，只要满足至少有 n-1 条边即可
和这个题目是一个思考方式：题10
保证无向连通图，每一个结点都连通，和最少边构成最小连通子图，这是两个两个问题，思考的角度不一样
前者要考虑，考虑如何避免出现孤立节点，也就是所有的结点都要用上，而后者要考虑的是构建一个子图

解