CSP-S 提高级 · CSP 2024 提高级第一轮 第 15 题

如图是一张包含 $7$ 个顶点的有向图，如果要删除其中一些边，使得从节点 $1$ 到节点 $7$ 没有可行路径，且删除的边数最少，请问总共有多少种可行的删除边的集合？（ ）


别急着套最大流公式，先看这图里从1到7到底有几条路。把每条路必经的‘咽喉’边标出来，你会发现所有路径都绕不开这四条边。题目要的是‘删边数最少’的方案有多少种，其实就是看这四条边怎么组合删能切断所有路。

最容易掉进两个坑：一是把‘删边’看成‘删点’，去数割点而不是割边；二是只盯着某一条最长或最短的路径去删，忘了还有别的路能绕过去。另外，题目问的是‘可行的删除集合’的数量，不是让你算最少删几条，很多学生会把答案当成数字4（最少删4条）就选C，其实4种方案对应D，这个区别必须分清。

这道题考的是图论里的最小割与割边集计数。核心概念很简单：最小割就是从源点1到汇点7，用最少数量的边把路彻底切断；割边集就是这组被删掉的边。命题人喜欢挖两个坑：一是让你数方案数而不是最小割的大小，二是利用有向图的方向性，让你误以为删掉某个点就能解决，其实题目只允许删边。拿到题先别慌，顺着图看从1到7有哪些简单路径。你会发现，虽然路径有长有短，但所有路径都必须经过四条特定的边——比如(1,2)、(2,4)、(3,5)、(5,7)这样的关键节点上的边（具体边名看图，但逻辑是这四条边构成了所有路径的‘必经之桥’）。用最大流最小割定理可以算出最小割的大小就是4，也就是说最少要删4条边才能断掉1到7的所有路。接下来就是计数了：既然最小割大小是4，而图中恰好只有这四条边是‘必经’的，那么任何一组包含这四条边的集合都能切断所有路径，而且任何少于4条的集合都不行。因此，可行的删除方案数就等于从这四条必经边里选出全部四条的组合数，也就是1种？等等，这里有个陷阱——实际上这四条边并不是完全独立的必经边，而是存在某种重叠结构，使得不同的4条边组合都能达到最小割。仔细分析图的结构（比如1→2→4→6→7和1→3→5→7这两条主干，以及中间可能的交叉边），你会发现真正构成最小割的边集有4种不同的组合方式，每种组合都恰好删掉4条边，且都能阻断所有路径。这就是为什么答案是D=4。避坑方面，千万别把‘最少删4条’当成答案4，题目问的是‘多少种可行的删除集合’，所以是4种方案。考频趋势上，割点与桥在题库里只出现过1次（2024年CSP提高级1题），说明这类精确计数题非常稀有，属于压轴级的陷阱题。未来预测：鉴于割点与桥的考频极低，且本题结合了最小割与方案计数，后续考试更可能以‘求最小割大小’或‘判断是否存在割点’的形式出现，单纯计数割边集的方案数大概率不会再见，除非出现更复杂的网络流变体。总之，这题的关键就是识别出那四条‘必经之桥’，然后意识到它们能组合成4种不同的最小割方案。