动机
一条恰好使用每条边一次的路线,与一条恰好经过每个顶点一次的路线,解决的是不同的问题。当需要枚举的对象是转移或相互重叠的词时,顶点重复是很自然的。欧拉(Euler)遍历把“每条边都要用到”这一要求转化为度数平衡与一个连通性条件。
对于词,图的顶点表示所记住的固定长度的前缀,每条边表示一个需要列出的完整块。每条边恰好遍历一次,就使每个块恰好出现一次。图的重叠规则把一条回路转化为一个紧凑的循环词,而不是一份互不相连的块列表。
定义
定义 5.2.1
(有向迹、度数与弱连通)
设有限有向多重图至少有一个顶点,其弧带有标号,允许有环与平行弧。迹不重复使用任何弧。闭欧拉迹从某个顶点出发并回到同一顶点,且每条弧恰好使用一次。端点为相异顶点 的开欧拉迹从 出发、到 结束,同样每条弧恰好使用一次。
一个环对入度和出度各贡献一。在非孤立顶点上的弱连通是指:当存在弧时,忽略方向并去掉孤立顶点之后,这些顶点构成一个连通图。无边图在任意选定的顶点处拥有空的闭迹。
定义 5.2.2
(万有词与词重叠图)
固定一个大小为 的字母表 和块长 。正长度 的循环词按周期方式读取;它的长度为 的块可以绕过末端回绕,若 甚至可以回绕多于一次。万有循环词包含 中的每个元素。我们要寻找每个元素恰好出现一次的循环词。
线性词不回绕。若其长度为 ,则长度为 的块有 个起始位置。词重叠图的顶点集为 ,对 中的每个词有一条带标号的弧,从它长度为 的前缀指向它长度为 的后缀。当 时,只有一个空词顶点以及 个带标号的环。
概念视角结构
顶点存储重叠记忆;边才是必须恰好出现一次的对象
顶点重复意味着重新访问了所记住的后缀,这是无害的。重复一条边则会重复它的整个块,而这在所求的万有词中是被禁止的。度数平衡定理控制着对边的枚举,而重叠关系把它压缩成一个循环序列。
定理/命题
定理 5.2.3
(平衡性与非孤立连通性刻画欧拉迹)
有限有向多重图存在闭欧拉迹,当且仅当所有顶点的入度等于出度,并且在存在弧时其非孤立的底图是连通的。
对于相异的 ,从 到 的开欧拉迹存在,当且仅当同样的连通性条件成立, 的出度比入度大一, 的入度比出度大一,且其余所有顶点都是平衡的。
定理 5.2.4
(万有词达到两个计数下界)
对每个 ,存在长度为 的循环词,其中每个长度为 的词恰好出现一次。没有更短的万有循环词。
另存在长度为 的线性词,恰好包含每个长度为 的词一次,并且不存在更短的万有线性词。循环的定义包括单符号字母表,即使所要求的块长超过整个循环的长度。
定理 5.2.5
(该构造关于其显式图是线性的)
给定带有持久未用弧指针的邻接表,欧拉圈拼接可以在 次图操作和 个存储条目内实现。对于重叠图,这些数量为 和 。
对于固定的字母表,带有显式词标号的直接实现使用 的符号运算量与存储空间,包括图的构造和初始线性词前缀。当 时,输出规模本身关于 是指数级的;这并不是关于块长度的多项式输出规模的论断。
证明思路或证明
证明
(度数计数、贪心闭片段与拼接)
闭准则的必要性来自对迹在每个顶点处到达与离开次数的计数。其使用过的弧在底图意义下也连通了每个非孤立顶点。开迹的度数差来自唯一的一次起始离开和最后一次到达;其余每一次到达都与一次离开配对。
对于闭情形的充分性,从一个有未用出弧的顶点出发,贪心地沿未用弧前进。若从 出发的迹停在不同的顶点 ,则在该处已用入弧数将比已用出弧数多一。由于没有未用出弧,这一差值也会使该处的已用入弧数超过原来的入度,与原图的平衡性矛盾。因此有限的贪心迹只能停在其起点,从而得到一条闭迹。
去掉闭迹所用的弧,剩余图仍保持平衡。若当前迹上有某个顶点还有未用出弧,则在该处重复此论证,构造另一条闭迹,并在该顶点处把它拼接进旧迹。弧的标号使得即使几条弧有相同端点,也不会被重复使用。
当不再有这样的顶点时,所有弧必然都已被使用。否则,取底图中一条路径第一次越过边界之处,弱连通性提供了一条未用弧,它连接一个已在迹上的顶点与一个迹外的顶点。已用的越界弧会使其两个端点都已在迹上。若这条未用越界弧指向外部,它直接提供了迹上的一条未用出弧。若它指向内部,则其端点处的剩余平衡性也在该处提供了一条未用出弧。两者都与停止条件矛盾。这样就证明了充分性,而无需把弱连通性替换为未经证明的更强假设。
对于开情形,添加一条特别的辅助弧 。它使两个端点平衡,并保持非孤立连通性。增广图中存在闭欧拉迹。将其弧列表旋转,使之从该辅助弧之后立即开始,然后删去该弧;剩下的列表就是从 到 的开欧拉迹。特别的标号使得即使已有另一条弧具有相同的方向和端点,这一论证依然有效。
证明透视
剩余平衡性阻止贪心片段停在错误的顶点
充分性的证明在两个不同的地方使用它的两个假设。平衡性在局部、在贪心行走停下的那一刻使用:从 出发而卡在 的行走,进入 的已用弧比离开 的多一条;既然再没有未用的出弧, 原来的出度便小于入度。后续每一轮都可以作同样的计数,因为闭片段在每个顶点用掉的入弧与出弧一样多,所以剩余图仍然平衡。
连通性只在拼接停止之后、在整体上使用一次:它给出一条连接路线顶点集与其余部分的越界弧,而越界弧在路线上那个端点处的剩余平衡性,把指向内部的越界弧转化为一条未用出弧。两个假设不能互相代替:两个分离顶点上各有一个环的图是平衡的,却无法连起来;只有一条弧 的图是连通的,却使行走滞留在 。开情形借助一条带标号的辅助弧化为闭情形,因此不需要第三个论证。
实现拼接而不必反复扫描整条路线
证明
(指针与工作表的计数)
保持出弧邻接指针和一个由路线出现位置组成的循环链表。每当使用一条弧,贪心片段便推进相应的出弧指针。为每个已访问的顶点存储一个已知的路线出现位置,这样新的闭片段就能通过常数次指针修改插入该处。
维护一个候选出现位置的工作表,这些位置的顶点可能仍有未用出弧。当新片段产生出现位置时,检查并安排它们;当旧候选从工作表中移除时,若其出弧列表已耗尽则跳过。若某个起始顶点仍有更多未用弧,则它也出现在新创建的片段中,因而可以通过这个新出现位置再次被安排。
每条弧只产生常数个存储的路线条目,并且被邻接指针处理一次。每个出现位置只在创建时被安排一次,每个被安排的候选只被移除一次。因此,初始的顶点扫描、邻接处理、工作表和拼接合计需要 次操作。每处理一个片段就重新扫描整条不断增长的路线的朴素实现不具有这一界;工作表的计数分析是该实现的一部分。
重叠图满足该准则
证明
(重叠图的度数与强连通性)
对任意长度为 的顶点,添加任一字母表符号在末尾得到一条出弧,在开头添加任一符号得到一条入弧。两种度数都是 ,当 时的空词顶点也不例外。
该图是强连通的,因而是弱连通的:从任意顶点出发,依次添加所需目标顶点的各个符号。经过 步之后,所记住的后缀恰好就是该目标。当 时无需任何步骤,因为只有一个顶点。因此,已证明的欧拉准则给出一条包含全部 条带标号块弧各一次的回路。
重叠把回路转化为一个词
证明
(把回路读成词、下界与符号代价)
读取线性表示的方法是:先写出初始顶点的词,然后按回路顺序写出每条弧的最后一个符号。用归纳法可知,在每个新写出的符号处结束的长度为 的块恰好是该弧的标号:先前的后缀是它的尾顶点,而添加操作给出整条边所对应的词。这样的块共有 个,两两相异且穷尽所有块。总长度为 。
对于循环表示,读取沿回路各条弧的最后一个符号。在每个弧位置结束的块都是它的标号,因为相继的弧标号在其后 个符号与前 个符号处重叠,包括由末到首的闭合。沿着之前的弧向后追溯,可对全部 个符号证明这一点,即使这意味着回绕多于一次。从块的结束位置转为块的起始位置只是对循环位置做一个置换,所以每个块仍然恰好出现一次。
任何长度为 的循环词只有 个块起始位置,因此要包含全部不同的块,必须有 。线性万有词首先长度至少为 ,然后还需 。这是两个下界,二者都被回路构造所达到。
对于固定字母表上带显式词标号的图的构造,把全部长度为 的顶点存储在一棵字典树中。每条弧及其移位后的头部可以用 次符号操作写出并定位;因此枚举所有弧用 。欧拉阶段采用所述的图条目模型。这一显式的符号界不把任意长的词标号当作一次免费的比较,也不在未计入代价的情况下假设存在常数时间的字符串字典。
例题详解
例题 5.2.6
(八个二进制三元块恰好填满长度为八的循环)
循环词 的连续回绕三元块为
这些恰好是长度为三的全部八个二进制词。在重叠图中,它们给出闭顶点路线 。四个两位顶点的入度与出度都是二,而且每条块弧恰好出现一次。
线性代表为 ,即把最初两个符号附在末尾,以给出最后的回绕块。它的十个符号恰好给出八个普通的三元块位置,因此同样达到线性下界。
例题 5.2.7
(把环片段拼接进更大的回路)
使用如下的弧: 处的一个环、一条弧 和一条弧 。两个顶点都是平衡的。单独的环就是在 处一个有效的初始闭片段。
其余两条弧构成闭片段 ,可以在 的该出现位置处拼接,得到 或相应的循环旋转。尽管 重复出现,每条弧仍恰好使用一次。环是一条独立的弧,贡献一个入关联和一个出关联,而不是因无关紧要而被丢弃。
例题 5.2.8
(单符号字母表需要重复回绕,而不是更长的循环)
对于字母表 和块长四,唯一的块是 。单符号循环 通过周期读取在其唯一的起始位置包含它,需要回绕数次。重叠图只有一个顶点 ,以及一个标号为 的环。
最短的线性词则是 ,长度为四,与公式 的预测一致。当块长为一、字母表为 时,该图是一个空词顶点加三个环,而循环 恰好包含每个单符号块一次。这两个边界情形使用相同的定义。
常见错误
反例模式
仅有平衡的度数无法连接不相连的片段
取两个顶点,各有自己的一个环,二者之间没有弧。每个顶点的入度都等于出度,但没有任何一条迹能同时使用两个环。非孤立的底图是不连通的。这就是为什么连通性是一个独立的假设,而不能从度数平衡推出。
常见错误
(欧拉迹可以重复顶点)
不要把欧拉迹与不得重复顶点的路径混淆。在二进制三元块的重叠图中,回路 把四个顶点各经过两次;只有弧才是恰好使用一次的。
常见错误
(回绕与不回绕的块计数)
循环块的计数包含回绕,而线性计数只包含后面还有足够符号的起始位置。长度为八的循环 包含全部二进制三元块,但若当作线性词读取,它只有六个三元块位置;线性代表 需要多两个符号。
常见错误
(对图线性不等于对块长多项式)
线性的图操作界并不会使一个相对于其较小的长度参数而言指数级长的万有词变成多项式长度。当 、 时,循环有 个符号,任何把它写出来的算法都至少需要这么多步。
总结
有向图的度数平衡与非孤立弱连通性给出欧拉迹的完整判别准则。剩余平衡性支持闭片段的拼接,持久指针加上被安排的出现位置给出线性的图运算量。词重叠图满足这些条件,从而产生最优的万有循环词与线性词,其中短循环与空前缀的边界情形均被明确处理。
练习
快速检查
(验证循环词 恰好一次地包含字母表 上的所有有序对。证明其长度是最小的。)
列出它的九个循环对的起始位置,包括由末到首的那一对。
解答 · 答案
这些对为 。九个可能的有序对各出现一次。任何包含它们全部的循环词至少有九个起始位置,因此长度至少为九。所给出的词达到这一下界,其最后一对由末两个符号接上起始的零构成。
快速检查
(为什么包含每个三位块的二进制线性词至少有十个符号?给出一个达到该界的词。)
数一数普通的起始位置,并与八个可能的块比较。
解答 · 答案
长度为 的线性词有 个三元块位置。要包含全部八个不同的块,需要 ,故 。词 达到十,它的块已在第一个例子中列出。长度为八的循环之所以足够,只是因为其回绕的块也被允许;去掉这一约定,计数就会改变。
快速检查
(对于由弧 、、 以及 处的一个环构成的图,求一条开欧拉迹。验证端点的度数,并解释辅助弧的构造。)
把环保留为四条带标号的弧之一。
解答
顶点 的出度为二、入度为一; 的入度为二、出度为一; 是平衡的。非孤立的底图是连通的。弧序列 使用了全部四条弧,并具有所要求的端点。
添加辅助弧 使每个顶点都平衡。相应的闭迹可以旋转,使该弧排在最后,删去它便得到所示的开迹。它的特别标号使之区别于可能同时存在的任何原有平行弧。