十点五十七。
还剩三十三分钟。
草稿上的三点图里,两条闭迹都经过`A`。
`A→b→A`。
`A→c→A`。
林一盯着`A`处的两组局部配对。
原来的配法是:从`b`回到`A`,再走向`b`;从`c`回到`A`,再走向`c`。
所以两条路各回各家。
若交换呢?
把入边`b→A`改配出边`A→c`,把入边`c→A`改配出边`A→b`。
追踪顺序立刻变成:
`A→b→A→c→A`。
四条边,一条闭合有向迹,一条也没重复。
林一的笔尖重重戳在`A`上。
不是删除周期。
是换掉共享顶点处的两个配对,把两只环焊在一起。
三点反例没有把局部配对法判死。它只替他守住了那句不能跳的边界:任意配对先得到的是若干周期;要得到一条总迹,还必须证明这些周期总能找到共享点,并且交换后确实合成而不拆坏别处。
空边情形平凡。以下设边集非空。
他在草稿上写:
`在所有局部入出边双射中,取置换周期数最少者。`
这样的配对存在。每个顶点入度等于出度,所以局部双射至少有一种;图的边数有限,所有局部双射的组合也有限,周期数因而能取到最小值。
若最小周期数已经是一,结论成立。
假设最小周期数`k>1`。
还缺两件事。
第一,不同周期为什么必有两条共享顶点?
第二,共享顶点处交换配对,为什么必把两条周期合成一条,而不是又拆成两条别的周期?
十点五十九,林一没有急着写“由强连通性显然”。
他把`k`条置换周期当成`k`个新顶点。若两条闭迹经过同一个原图顶点,就在对应的新顶点之间连一条无向边。
得到一张“周期交叠图”。
原图强连通,周期交叠图是否一定连通?
林一先写“是”,又划掉。
强连通说原图任意两点间有有向路,不直接说任意两条周期共点。中间可能要经过第三条、第四条周期。
但这恰好说明交叠图应当通过中间周期连起来。
他选任意两条周期`c?、c?`,各取一个原图顶点`u、v`。由强连通性,存在一条从`u`到`v`的有向路。路上的每一条边都属于某个置换周期;相邻两条路边在共同端点相接,所以它们所属的周期相同,或在交叠图中相邻。
沿这条有向路读下去,便得到从`c?`所在周期到`c?`所在周期的一条交叠图路径。
周期交叠图连通。
既然`k>1`,它至少有一条边,也就至少存在两条不同的置换周期共享某个原图顶点`w`。
第一座桥闭合。
林一在桌下攥拳,指节压得发白。
十一点零六。
还剩二十四分钟。
第二座桥。
设两条周期在`w`处分别使用入边`e?、e?`,原配对把它们接到出边`f?、f?`。把配对交叉改为`e?→f?、e?→f?`,其他所有顶点、所有其他入边的配对不变。
从`f?`开始沿第一条旧周期走,会走到`e?`进入`w`;新配对不再接回`f?`,而是转入`f?`。随后沿第二条旧周期完整走到`e?`,再由新配对接回`f?`。
两条旧周期因此首尾相接成一个新周期。
它包含两条旧周期的全部边,每条恰好一次;其他`k-2`条周期完全不受影响。
共享顶点可以在合并后的迹中出现多次,这不违反题意;题目禁止重复的是边,不是顶点。三点图里的`A`正好把这条边界提前暴露出来。
新配对的周期总数为`k-1`。
与`k`最小矛盾。
所以`k=1`。
一条覆盖全部边、每条边恰好一次的闭合有向迹存在。
十一点十一。
林一的胸口像被猛地撞开。
他没有压住那只拳。
拳头在桌下狠狠向上一顶,撞到桌板,发出“咚”的一声。
监考抬头。
林一立刻摊开手,示意没有掉落物,也没有说话。
前排有人被那声闷响惊得回头。N18方向,唐予宁的红笔停了一瞬,随即在纸上狠狠干拉下一道收束线。N32那边,沈砚没有回头,只把写满的第五张答题纸推到最上方,开始逐页反读结论。
林一开始誊写。
第一段定义局部双射与边置换。
第二段取周期数最少的配对,说明有限性保证最小值存在。
第三段构造周期交叠图,用原图任意两点间的有向路证明交叠图连通。
第四段在共享顶点交换两组配对,按`f?`、`e?`、`f?`、`e?`的顺序证明两周期合一。
第五段得到`k-1<k`的矛盾。
十一点十九,十四行写完。
他从最后一行倒查。
“所有局部双射组合有限”是否需要计数?不需要具体数量,只需每个有限入边集到等势出边集的双射有限,有限个顶点的有限乘积仍有限。
周期交叠图的连通证明中,有向路第一条边所属周期未必就是`c?`。因为起点`u`在`c?`上,却可能从另一条也经过`u`的周期离开。
这不是断桥。
第一条路边所属周期与`c?`共享`u`,所以在交叠图中相邻;终点同理。林一把这两句补到段首段尾。
十一点二十二。
交换配对后,局部双射是否仍为双射?
只交换`f?、f?`两个像,其他像不变,当然仍一一对应。但“当然”不能独占卷面。
他补写:`该操作仅作一个二换位,保持双射。`
十一点二十四。
还剩六分钟。
林一没有继续美化压轴。
他翻回第三题,检查有向长度负号;翻到第二题,检查零元先剔除;翻到第一题,检查循环替换的覆盖性。
十一点二十七,前三题无新增修改。
十一点二十八,他核对姓名、编号、页码。
叶峥在斜前方也正摸过每页右下角。唐予宁把隔开废路线的竖线再描了一次,却没有撕页。沈砚反读到第四页时,食指在一处停住,补了九个字。
周围没有人知道别人能拿多少分。
但所有人都知道,这是第一阶段最后两分钟。
监考报时。
“还剩一分钟。”
有人长长吐气。
有人把笔帽提前放在左手心,防止铃响后多写。
林一把四道题的最后一句各看一遍。
代数等号成立。
数论落单根成立。
几何公共弦成立。
组合合并桥成立。
铃声响起。
“停笔。”
林一的笔尖离开纸面。
没有多补一个句号。
三间考场的答题纸按编号收齐,页数复核,装袋,密封。林一看着N31的最后一页消失在牛皮纸袋里,手掌才开始发抖。
考场门打开。
走廊里先没有声音。
六十个人像同时忘了应该怎样呼吸。
然后第三考场有人狠狠干吼了一句:“封了!”
声音瞬间炸开。
“四场全封!”
“写完了!”
“别对答案,先喊!”
栏杆被拍响,鞋底在地面跺出一片闷雷。唐予宁把笔袋举过头顶,叶峥靠着墙笑到弯腰,沈砚从人群里挤过来,一把抓住林一肩膀。
“你最后撞桌干什么?”
“两条合成一条。”
沈砚眼睛一下亮了,又硬生生把追问咽回去。
“封了,不问。”
“不问。”
两个人狠狠干撞了一下拳。
这次没有当前第几,没有预测箭头,也没有谁替谁算线。
只有三只末场密封袋被监考抱过走廊,六十个人一路拍栏、跺脚、怒吼,把它们送进评分室。
正式结果还一个字都没出来。
可他们已经把能写的,全留在里面。