NOIP 提高 2017 第一轮 第 5 题：设G是有n个结点、m 条边（n≤m）的连通图，必须删去G的（）条边,

题目

设 $G$ 是有 $n$ 个结点、$m$ 条边 $(n \leq m)$ 的连通图，必须删去 $G$ 的（   ）条边， 才能使得 $G$ 变成一棵树。

选项

• A. $m - n + 1$
• B. $m - n$
• C. $m + n + 1$
• D. $n - m + 1$

答案

A

题解

考点定位

本题考「生成树」,对应大纲 3.3.1（难度【1】）。

解题过程

删 m−(n−1) = m−n+1 条。

选 A。

易错提醒

① 与普及组同题；② 冗余边 = 环数（基本圈秩）。