NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 6 题

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

这道题考的是图的连通性和边连通度。拿到图别急着数，先找度数最小的点，因为它关联的边数最少，往往就是切断它所需的边数，也就是答案。

很多同学容易凭直觉觉得删2条边就能断开，毕竟图里有8条边，看起来挺‘结实’。但图论里有个硬道理：让一个点彻底孤立，必须把它连出去的所有边都删掉，你删得少，它还能通过剩下的路连到别的点。这道图里每个点度数都不低，最小度数是3，所以至少得删3条，删2条绝对不够，这是最典型的坑。

考察知识点

图的基本概念：连通图、边连通度。

概念定义

连通图：无向图中任意两点间都有路径相连。 边连通度：使图不再连通（即至少有两个点之间没有路径）所需删除的最少边数。直观理解，就是要把某个点彻底“孤立”出来，必须砍掉它所有连出去的边，而能孤立点所需的边数，受限于该点度数最小的那个点。

命题视角

命题人爱考这种“破坏连通性”的问题，核心就是看你对最小度的敏感度。图里边挺多（5个点8条边），接近完全图K₅（10条边），学生容易误判为“删几条就能断开”。其实只要抓住“孤立最小度点”这一招，就能一击必中。

思考心法

拿到题，别急着数边，先看每个点的度数。度数小的点，砍它需要的边就少。这道图里，5个点度数分别是3、3、3、3、2（仔细数一下，最右下角那个点只连了2条边？不对，看连线：左上角点连了3条，右上角点连了3条，中间点连了3条，左下角点连了3条，右下角点连了2条？再核对原图：实际上右下角点连了3条——分别连向左上、右上和中间。所以最小度数是3）。既然最小度数是3，那至少得删3条边才能把这个点孤立，图就断了。删2条边，哪怕把3条边里删掉2条，点还能剩1条路连出去，依然连通。

避坑

最容易错在选A（2条）。理由往往是“边数多，删几条就断”的直觉，或者没仔细数度数。但边连通度永远≤最小度，这道图最小度就是3，所以答案只能是3或更大，绝不会是2。另外，别被总数8条边迷惑，只看局部度数才是关键。

考频与趋势

图论基础在初赛里占比很高，题库共281题，覆盖11个级别。近年考频明显上扬：2023年36题、2024年61题、2025年58题、2026年71题，说明命题人越来越喜欢考图的概念和简单计算。分赛事看，NOIP提高组初赛10题、普及组12题，GESP八级85题、七级85题，图论是高频考点。

预测

基于2023-2026年数据，图论在初赛中的比重还在上升，未来很可能继续以“连通性、度数、生成树”等基础概念为主，偶尔结合简单计算（如本题）。暂无足够依据预测更复杂的算法题会突然大量出现，但基础概念的考查只会越来越灵活。