408考研逐题详解：2010年第7题——连通图的边
2010年第7题
若无向图 G=(V，E) 中含有 7 个顶点，要保证图 G 在任何情况下都是连通的，则需要的边数最少是（ ）
A. 6 \qquad B. 15 \qquad C. 16 \qquad D. 21
解析
本题主要考查图的有关知识：
-
连通图：一个无向图是连通的，当且仅当图中任意两个顶点之间都存在一条路径。连通性是图的基本性质，确保图没有孤立的部分。
-
不连通图的最大边数：当图不连通时，它可以被划分为两个或更多连通分量。为了最大化边数，每个连通分量应尽可能“稠密”，即内部边数最大化。最坏情况是图被分成两个完全图，大小分别为 k k k 和 n − k n-k n−k（其中 n n n 为顶点数， 1 ≤ k ≤ n − 1 1 \leq k \leq n-1 1≤k≤n−1）。此时，边数为 ( k 2 ) + ( n − k 2 ) \binom{k}{2} + \binom{n-k}{2} (2k)+(2n−k)，其中 ( k 2 ) = k ( k − 1 ) 2 \binom{k}{2} = \frac{k(k-1)}{2} (2k)=2k(k−1) 表示大小为 k k k 的完全图的边数。
- 最大值出现在 k = 1 k=1 k=1 或 k = n − 1 k=n-1 k=n−1 时（即一个孤立点和一个完全图），此时边数为 ( n − 1 2 ) = ( n − 1 ) ( n − 2 ) 2 \binom{n-1}{2} = \frac{(n-1)(n-2)}{2} (2n−1)=2(n−1)(n−2)。
-
保证连通性的最小边数：要保证任何具有 n n n 个顶点和 m m m 条边的图都连通， m m m 必须大于不连通图的最大可能边数。即：
m > max 1 ≤ k ≤ n − 1 ( ( k 2 ) + ( n − k 2 ) ) m > \max_{1 \leq k \leq n-1} \left( \binom{k}{2} + \binom{n-k}{2} \right) m>1≤k≤n−1max((2k)+(2n−k))
由于最大值在 k = 1 k=1 k=1 或 k = n − 1 k=n-1 k=n−1 时取得，且为 ( n − 1 2 ) \binom{n-1}{2} (2n−1)，因此最小 m m m 为：
m = ( n − 1 2 ) + 1 = ( n − 1 ) ( n − 2 ) 2 + 1 m = \binom{n-1}{2} + 1 = \frac{(n-1)(n-2)}{2} + 1 m=(2n−1)+1=2(n−1)(n−2)+1
如果边数 m m m 满足此条件，则图不可能不连通（因为边数已超过不连通图的最大边数），必须连通。 -
组合计算（二项式系数）：需要计算组合数 ( n 2 ) = n ( n − 1 ) 2 \binom{n}{2} = \frac{n(n-1)}{2} (2n)=2n(n−1)，表示 n n n 个顶点中无序对的数量（即完全图的边数）。
本题要求“在任何情况下都连通”，即无论边的分布如何，只要边数达到最小值，图就必须连通。这对应于最坏情况分析：考虑边被最大化地用于连通分量内部，但分量之间没有边（导致不连通）。
已知顶点数量 n = 7 n = 7 n=7 ：
- 不连通图的最大边数为 ( 6 2 ) = 15 \binom{6}{2} = 15 (26)=15（例如，一个 K 6 K_6 K6 有 15 条边和一个孤立顶点）。
- 保证连通的最小边数为 15 + 1 = 16 15 + 1 = 16 15+1=16。
对于本题，注意区分“可能连通”和“保证连通”：
- 边数 m = n − 1 = 6 m = n-1 = 6 m=n−1=6 时，图可能连通（如树），但不保证（如多个连通分量）。
- 边数 m = ( n − 1 2 ) + 1 = 16 m = \binom{n-1}{2} + 1 = 16 m=(2n−1)+1=16 时，强制图连通，体现组合优化思想。
即区分易混淆概念：最小连通边数（ n − 1 n-1 n−1） vs. 保证连通最小边数（ ( n − 1 2 ) + 1 \binom{n-1}{2} + 1 (2n−1)+1）。
本题答案：C