亲,欢迎光临多多书院!
错缺断章、加书:站内短信
后台有人,会尽快回复!
多多书院 > 都市言情 > 天才起跑线 > 第193章 反例替他守住边界
  • 主题模式:

  • 字体大小:

    -

    18

    +
  • 恢复默认

十点五十七。

还剩三十三分钟。

草稿上的三点图里,两条闭迹都经过`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的最后一页消失在牛皮纸袋里,手掌才开始发抖。

考场门打开。

走廊里先没有声音。

六十个人像同时忘了应该怎样呼吸。

然后第三考场有人狠狠干吼了一句:“封了!”

声音瞬间炸开。

“四场全封!”

“写完了!”

“别对答案,先喊!”

栏杆被拍响,鞋底在地面跺出一片闷雷。唐予宁把笔袋举过头顶,叶峥靠着墙笑到弯腰,沈砚从人群里挤过来,一把抓住林一肩膀。

“你最后撞桌干什么?”

“两条合成一条。”

沈砚眼睛一下亮了,又硬生生把追问咽回去。

“封了,不问。”

“不问。”

两个人狠狠干撞了一下拳。

这次没有当前第几,没有预测箭头,也没有谁替谁算线。

只有三只末场密封袋被监考抱过走廊,六十个人一路拍栏、跺脚、怒吼,把它们送进评分室。

正式结果还一个字都没出来。

可他们已经把能写的,全留在里面。