发表日期: 2026年06月 发表单位: University of Maribor; Institute of Mathematics, Physics and Mechanics, Ljubljana; University of Ljubljana; University of Novi Sad 原文链接: https://arxiv.org/pdf/2606.27120v1.pdf
先把规则摆平，不然后面会越看越像“谁先眨眼谁输”。论文里把图 G 当作棋盘。跑者一开始先走一条边，之后轮流行动：跑者每次必须沿着当前所在顶点的一条未走过的边继续前进；阻挠者则每回合删除一条边。跑者的目标很朴素：尽量访问更多顶点。阻挠者则反过来，要让她尽量少走几个点。如果双方都很聪明，最后跑者能访问多少顶点就不再是“运气值”，而是图的一个不变量。论文把它叫做破坏数，记作 sab(G)。这里的“破坏”不是指图被炸了，而是指阻挠者通过删边把跑者的路线“拆短了”。为了方便后面讨论，论文还引入了一个很关键的概念：下破坏数，记作 sab-(G)。它的定义是：在图 G 的所有生成树里，取破坏数最大的那个。这条公式的意思很直白：先把图里所有“骨架树”都拿出来，再看哪棵树最能让跑者吃瘪。因为树没有环，路径更容易分析，所以这个定义相当于先给复杂图找一条“最难走的简化版”。论文的一个基本观察也很重要：如果 H 是 G 的连通子图，那么 sab(H) ≤ sab(G)。直觉上很好懂：图越大，跑者能绕的路通常越多，阻挠者想把她困住就越难。这个单调性，后面会一直被拿来当“递推垫脚石”。
2. 核心发现：破坏数的计算公式
这篇论文最值钱的地方，不是把某个特殊图算出来，而是先把树的破坏数彻底算明白了。因为树像图论里的“素颜照”，没有环来搅局，很多策略都能看得非常清楚。作者给出的结论是：树的破坏数由一棵完美二叉子树决定。更准确地说，要在树中找一棵以某个点为根的完整二叉子树，看它的高度，再加上一个和根的度数有关的修正项。这个修正项很有意思：如果根的度数大于 2，说明根除了二叉子树之外还有“外援边”，跑者能多蹭一步，所以结果要再加 1。换句话说，树里的破坏数不是看“最长路有多长”，而是看阻挠者能不能持续把跑者赶进一棵二叉迷宫。只要这棵迷宫足够深，跑者就能一路往下钻；一旦某层某个分支被删掉，她就只能换另一边。这个过程像在走一个不断缩水的选择树。这条公式对应的是证明里的关键上界：如果某个位置能保证跑者至少再走 k 步，那么图里就必须藏着一棵高度至少为 k 的完整二叉子树。这里的 h(B) 是子树高度，degT(v2) 是顶点度数，方括号里的项表示“条件成立时加 1，不成立时加 0”。这其实给了一个很漂亮的图论直觉：跑得远不远，取决于分叉够不够多。如果图老是单线条，阻挠者一删边就结束；如果图有稳定的左右分叉，跑者就能像“躲猫猫高手”一样不断换路。作者进一步证明：对于树 T，这个公式不仅是上界，还是精确值。也就是说，树的破坏数可以被完整刻画。这一步非常关键，因为后面的单环图、子三次图，都是借着树的结果往外扩。
[1] Marko Jakovac, Sandi Klavžar, Mirjana Mikalacki, Andrej Taranenko. Maker-Breaker Sabotage Game. arXiv:2606.27120v1, 2026.[2] van Benthem 等关于 sabotage games 的早期工作，以及 Maker-Breaker positional games 的经典文献，见原文参考文献列表。
