NOIP 提高 2013 第一轮 第 6 题：在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。右图是一个有 5

题目

在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。右图是一个有 $5$ 个顶点、$8$ 条边的连通图。若要使它不再是连通图，至少要删去其中的（   ）条边。

选项

• A. 2
• B. 3
• C. 4
• D. 5

答案

B

题解

考点定位

本题考「边连通度」,对应大纲 3.3.1 连通图（难度【3】）。

解题过程

5 点 8 边连通图（原卷图）：要使其不连通的最少删边数 = 图的边连通度。按原图找最小割：割断某点需删其关联边——原图中最小度数点的度 = 3 ⇒ 至少删 3 条。

选 B。

易错提醒

① 最少删边数 = 最小边割集大小 ≤ 最小点度；② 找「孤立一个点」或「分成两坨」的最省删法。