NOIP 普及 2017 第一轮 第 10 题：连通图删边变成树需要删除的边数

题目

设 $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（难度【2】）。

解题过程

连通图 m 条边 → 树需 n−1 条：删 m−(n−1) = m−n+1 条。

选 A。

易错提醒

① 生成树 n−1 条边；② 删除的 = 环上的冗余边（余树）。