题目

设有向图 G=(V, E)，顶点集大小 n=|V|，每条边标记一个字符。定义字符串集 S 为所有路径上边标记拼接成的字符串的集合。以下说法错误的是（）。

错因

A

把"S 是有限集"当成错的，可能是受到"路径数可能很多"的直觉影响。事实是：无环 → 任何路径都不能重复顶点（否则就构成环了），路径长度上界为 n-1 条边，S 中字符串长度有限、个数也有限。A 是对的。

C

把"有环"和"路径只能走一遍"绑在一起，没意识到路径可以绕环任意多次。每多绕一圈就在字符串末尾追加一段固定子串，长度可以无限增长，自然存在远超 n 的字符串。C 是对的。

D

被"有环 → 字符串很长"的印象误导，以为 S 里全是绕环来的长串。其实 S 同样包含短路径——只要图里有任何一条边（有环时图肯定非空），那条单边自身就构成一个长度为 1 的串，1 < 2n。D 是对的。

总解析

先把"路径"读清楚：本题中 S 包含所有路径对应的边标记字符串，路径可以重复顶点（这是允许讨论"绕环长度"的前提）。

两种情形分别分析：

Case 1：G 无环

• 任何路径都不能重复顶点（重复就成环了）→ 这就是简单路径；
• 简单路径最多覆盖 n 个不同顶点 → 最多 n−1 条边；
• 字符串长度上限 n−1，不存在长度恰为 n 的字符串；
• 简单路径数上界 ≤ n!，S 有限。
• 故 A ✓，B ✗（B 是错误说法）。

Case 2：G 有环

• 可沿环绕任意多圈，每圈把字符串延长一段固定子串 → 字符串长度可任意大，必然存在长度 > n 的字符串。C ✓。
• 有环 → 至少有边 → 单条边即为长度 1 的字符串，1 < 2n。D ✓。

结论：错误的说法只有 B。

最终答案是 B。