「图的基本概念」在信息学竞赛真题中出现 47 次，覆盖 NOIP 提高组 初赛、NOIP 普及组 初赛、CSP 提高级、CSP 入门级。下面按考试级别列出每一道题的题号、答案与一句话解题思路，可以按考点横向刷，也可以顺着套卷纵向练。
怎么用这一页：先看下面的「命中题目速查」，挑 2~3 道做；做完对照每题的「常见错误」检查自己是不是踩了同一个坑；同一个考点连续错两次，就去知识点精讲把规则补齐再回来刷。
-
第 18 题
答案：A
· 选择题 · NOIP 2008 普及组初赛试题
这题考树的基本性质。拿到题先想：树是啥？连通且无环，边数一定是顶点数减一。直接对比选项，A说边数等于顶点数，明显违背定义，选它。
看完整解析 →
-
第 18 题
答案：A
· 选择题 · NOIP 2009 普及组初赛试题
这题考强连通图定义与最少边数，直接构造一个 n 个顶点的大环即可，每个点出度入度都为 1，且互相可达，边数恰好 n。
看完整解析 →
-
第 18 题
答案：D
· 选择题 · NOIP 2010 普及组初赛试题
这题考拓扑排序的核心性质。拿到题先想：拓扑排序只存在于有向无环图（DAG），且每一步必须选入度为0的点。因此第一个点必然是入度为0的点，而环、唯一性、前后顺序都是常见陷阱，直接排除干扰项。
看完整解析 →
-
第 5 题
答案：B
· 选择题 · NOIP 2011 普及组初赛试题
拿到题先想组合数：7个顶点里任选2个连一条边，C(7,2)=21。
看完整解析 →
-
第 19 题
答案：A
· 选择题 · NOIP 2011 普及组初赛试题
这题考强连通图的判定，拿到图先别急着删边，而是心里把每条边的‘替代路径’找出来，删掉后还能绕回来才是真强连通。
看完整解析 →
-
第 10 题
答案：C
· 选择题 · NOIP 2013 普及组初赛试题
这题考图论里的连通性与边删减。拿到图先数顶点数和边数，判断是不是完全图，再想：让图不连通，最少要让一个顶点‘孤立’，它连出去几条边就要删几条，这就是切入点。
看完整解析 →
-
第 12 题
答案：A
· 选择题 · NOIP 2013 普及组初赛试题
这题考图论里的深度优先搜索（DFS），拿到图先画访问标记，记住DFS是‘一条路走到底，撞墙才回头’，然后逐个选项模拟，看哪个顺序会卡在中间跳不过去。
看完整解析 →
-
第 17 题
答案：C
· 选择题 · NOIP 2014 普及组初赛试题
拿到题先别急着套公式，想清楚有向图和无向图的根本区别：边有方向，所以得从‘进’和‘出’两个方向数边，把两部分加起来才是顶点的度。
看完整解析 →
-
第 12 题
答案：B
· 选择题 · NOIP 2015 普及组初赛试题
这题考的是最小生成树的基本性质：n个顶点的树必有n−1条边。拿到题先别想算法，直接想树的结构——连通无环，所以边数一定是顶点数减一，代入6算就是5。
看完整解析 →
-
第 15 题
答案：D
· 选择题 · NOIP 2016 普及组初赛试题
这题就是考握手定理：总度数=2×边数。拿到题先设顶点数为n，把“每个点度数都是2”翻译成等式n×2=2×16，直接解出n=16，别绕弯子。
看完整解析 →
-
第 10 题
答案：A
· 选择题 · NOIP 2017 普及组初赛试题
这题考树的基本性质。拿到题先想：树必须连通且无环，n个结点的树边数固定是n 1。题目给的图有m条边，只要把多余的删掉就行，直接算m (n 1)就能选出答案。
看完整解析 →
-
第 11 题
答案：A
· 选择题 · NOIP 2018 普及组初赛试题
四个无标号点要连成连通简单图，先想‘最少几条边能连通？’树最少3条，再多就是4、5、6条。按边数一层层画，边数相同就比形状是否同构，同构的只算一种，这样就能把总数数清楚。
看完整解析 →
-
第 8 题
答案：B
· 选择题 · CSP 2019 提高级第一轮
这题核心就是抓“非连通”四个字。既然要顶点最少，那有边的部分必须尽可能稠密，直接凑成完全图；剩下的顶点只能孤立。算出能装下28条边的完全图顶点数，再加一个孤立点，答案就出来了。
看完整解析 →
-
第 12 题
答案：D
· 选择题 · CSP 2019 提高级第一轮
这题其实是在考你对数据结构的‘适用范围’有没有数清楚。拿到题先想：图是多对多关系，那谁能存多对多？栈、队列、二叉树都只能存线性或一对一/一对多，只有邻接矩阵是专门给图设计的，直接锁定D。
看完整解析 →
-
第 7 题
答案：C
· 选择题 · CSP 2021 提高级第一轮
这题核心就是利用非连通图至少有两个连通分量，把边塞进一个完全图，剩下的点只要凑够分量数就行。
看完整解析 →
-
第 15 题
答案：B
· 选择题 · CSP 2021 提高级第一轮
这题本质是手算 Dijkstra。别盯着 A 出发的边，先标出 A 到各点当前最短距离，每次把距离最小的那个点圈起来，再用它的出边去松弛邻居，直到圈到 J 为止。
看完整解析 →
-
第 8 题
答案：B
· 选择题 · CSP 2022 提高级第一轮
这题考的是强连通图与完全图的概念辨析。拿到题先别急着看选项，脑子里要把‘强连通’的定义刻清楚：有向图里任意两点间必须双向都有路径。然后逐项去套这个定义，看哪个选项描述的不是强连通而是别的概念，那个就是答案。
看完整解析 →
-
第 9 题
答案：D
· 选择题 · CSP 2022 提高级第一轮
这题本质是圆排列计数。2 正规图必由若干环组成，欧拉回路条件强制图连通，即只有一个大环。把 n 个点围成环，先除以旋转同构 n 得 (n 1)!，再考虑环可翻转（镜像对称）同构，最终除以 2，答案即 (n 1)!/2。
看完整解析 →
-
第 4 题
答案：C
· 选择题 · CSP 2023 提高级第一轮
这是 2023 年 CSP 提高组的一道经典题。规则：n 根柱子，依次放置编号 1,2,3... 的圆环，要求任何两个相邻（上下相邻）圆环的编号之和为完全平方数。问 4 根柱子时最多能放多少个。 构建图论模型：将每个编号…
看完整解析 →
-
第 6 题
答案：A
· 选择题 · CSP 2023 提高级第一轮
这题其实就在考二分图的定义。看到'不超过两种颜色'，脑子里立刻要跳出'无奇环'这几个字。然后逐个选项想：哪些图天生就没有奇环？树肯定没有环，那它一定没有奇环；平面图、边双连通、欧拉图虽然性质很好，但都可能藏着三角形这种奇…
看完整解析 →
-
第 13 题
答案：C
· 选择题 · CSP 2023 提高级第一轮
这题考拓扑排序与环的判定。图有拓扑序等价于无环（DAG）。题目说原图无拓扑序，说明有环；删一条边后要有拓扑序，就是要删掉能打断所有环的边。拿到图先找环，再找环的公共边，答案就是公共边的数量。
看完整解析 →
-
第 19 题
答案：BADC
· 完善程序 · CSP 2023 提高级第一轮
这题核心是 DAG 上第 k 小路径。先拓扑排序逆序 DP 算出每个点出发的路径数（含自身），再按字典序贪心：若 k 小于等于当前点的路径数，就选它；否则 k 减去该路径数继续往后找。
看完整解析 →
-
第 7 题
答案：D
· 选择题 · CSP 2024 提高级第一轮
这题考的是欧拉图的定义和性质。拿到题先想：欧拉图必须满足哪两个硬性条件？再看选项，前三个直接对应定义，只有D在讲边数奇偶性，这跟欧拉图本身没关系，图论里度数之和是边数的两倍，偶数加偶数还是偶数，所以边数必然是偶数，D肯定…
看完整解析 →
-
第 15 题
答案：D
· 选择题 · CSP 2024 提高级第一轮
别急着套最大流公式，先看这图里从1到7到底有几条路。把每条路必经的‘咽喉’边标出来，你会发现所有路径都绕不开这四条边。题目要的是‘删边数最少’的方案有多少种，其实就是看这四条边怎么组合删能切断所有路。
看完整解析 →
-
第 5 题
答案：D
· 选择题 · CSP 2025 提高级第一轮
这题考拓扑排序的数量性质。拿到题先想：拓扑排序是把 DAG 线性化，只要存在‘自由点’（入度为 0 的点），顺序就能换，数量就会爆炸。别被 n m 这种线性关系忽悠，孤立点都能排 n! 种，直接选 D。
看完整解析 →
-
第 8 题
答案：B
· 选择题 · CSP 2026 提高级第一轮
顶点 4 与谁都不相邻，位置完全自由；剩下 3 个顶点只需满足"1 在 2、3 之前"。用排列计数：总排列 4! = 24，而 {1,2,3} 中 1 排最前的概率是 1/3，故为 8。
看完整解析 →
-
第 11 题
答案：C
· 选择题 · CSP 2026 提高级第一轮
缩点后是 DAG，要把整张图变成强连通，最少添加的边数 = max(入度为 0 的数目, 出度为 0 的数目)，本题即 max(3, 4) = 4（前提是 SCC 个数 ≥ 2）。
看完整解析 →
-
第 19 题
答案：CDBA
· 完善程序 · CSP 2026 提高级第一轮
BFS 求无权图最短路，同时用 c[] 做二分图染色。① 把 '+'/' ' 变成权值 ±1；② 队列用 hh/tt 双指针，循环条件是 hh < tt；③ 距离由父结点加一；④ 相邻点同色说明出现奇环（非二分图）；⑤ …
看完整解析 →
粤公网安备44200102446416号 ·
意见反馈 ·
zsweiluo@163.com