配送路线可能需要经过每条街道,但允许重复经过路口。这是关于边的问题,不同于寻找经过每个顶点的哈密顿(Hamilton)圈。这里讨论有限简单无向图。
定义 2.1.1
(迹与欧拉回路)
迹是不重复边的游走;欧拉(Euler)回路是恰好经过每条边一次的闭迹。
对没有边而至少有一个顶点的图,约定长度为零的游走是回路;排除空顶点集。
定理/命题
定理 2.1.2
(欧拉回路的偶度判据)
至少有一条边的有限图存在欧拉回路,当且仅当所有正度顶点属于同一连通分支,且每个顶点的度数都是偶数。孤立顶点不影响路线。
证明
(配对进入边与离开边)
回路连接所有边的端点。每次经过顶点都使用一条进入边和一条不同的离开边;起点的最后进入边与最初离开边配对。因此每个顶点的关联边被分成若干对,度数为偶数。
证明
(闭合并拼接未用边的迹)
从正度顶点出发,沿未使用的边前进,直到无边可用。此迹必定回到起点:在其他顶点,已用的关联边由此前访问的一对对边及最后一条进入边组成;偶数度保证还存在未用的离开边。若所有边已用完则结束。否则,由正度顶点连通,可找到当前闭迹上的顶点与未用边相接:从闭迹沿路径走向某条未用边,取路径上的第一条未用边。删去闭迹的边后,每个顶点减少的度数都是偶数,故剩余图仍为偶数度。从该顶点沿未用边走出另一个闭迹,拼入原迹。每次拼接至少用掉一条新边,边数有限,最终覆盖全部边。
常见错误
(只需正度顶点之间连通)
要求整个图连通过强:三角形加一个孤立顶点仍有经过全部边的回路。反之,两个不相交三角形的度数全为偶数,却没有一条迹能覆盖两个分支。两个条件各有作用。
例题详解
例题 2.1.3
(共享一个顶点的两个三角形)
两个三角形 和 只共享顶点 。各点度数依次为 ,欧拉回路为 。允许重复顶点 ,没有边重复;它不是哈密顿圈,因为闭合前 出现两次。
练习
快速检查
(连通图能否恰有一个奇数度顶点?)
解答 · 答案
不能。每条边有两个端点,所以度数之和为 。一个整数和为偶数,当且仅当奇数项的数目为偶数。
快速检查
(证明:恰有两个奇数度顶点 的连通图有一条从 到 、恰好经过每条边一次的迹。)
解答 · 答案
添加新顶点 及边 。扩充图所有顶点均为偶数度,正度顶点连通,故有欧拉回路。把回路旋转成从 开始,再删除首尾两条边,即 的仅有两条关联边,剩余迹恰好经过每条原边一次,端点为 ;必要时反向。使用新顶点无须假设 原本不是边。
开迹与奇数度条件
定理 2.1.4
(开放迹的两奇度顶点判据)
回路定理也给出开放欧拉迹的完整判别法。设图至少有一条边,所有正度顶点在同一分支。存在恰好经过每条边一次且两个端点不同的迹,当且仅当恰有两个奇数度顶点;这两个顶点就是迹的端点。
证明
(两端未配对的边)
必要性来自配对:在每次内部访问时,把进入边与离开边配对。起点有一条未配对的离开边,终点有一条未配对的进入边,其余边均配对,所以恰有这两个奇数度顶点。迹在结束前重复经过端点也不影响论证,因为中间的访问仍贡献成对的边。充分性已在关于两个奇点之间欧拉迹的练习中用添加辅助顶点并删除其两条关联边证明。使用新顶点可以避免在原本已有 时加入重边。
没有奇数度顶点时,从正度顶点出发并覆盖每条边的迹必须回到起点。有四个奇数度顶点的图不可能由一条迹覆盖全部边,但可能由多条迹共同覆盖。正度顶点之间的连通性也不能省略:两条互不相连的边有四个奇数度顶点,两个互不相连的三角形没有奇数度顶点,两者都没有覆盖全部边的一条迹。
例题 2.1.5
(悬挂边产生两个奇数度顶点)
在共享 的两个三角形 上添加悬挂边 。 的度数变为 5 和 1,其余顶点的度数仍为 2。一条开放欧拉迹是 。它以两个奇数度顶点为端点。不能从 开始走完全部边,因为端点必须是 。
由证明得到算法
拼接闭迹证明了存在性,但若每次都在整条路线中重新寻找插入位置,就可能浪费许多时间。栈记录尚未处理完的顶点出现位置,隐式完成插入:先处理完一段沿未用边走出的路线,再返回较早的位置。同一顶点的不同次出现是不同的栈项。
先假设图至少有一条边,所有正度顶点在同一分支,且每个顶点度数均为偶数。选正度顶点 为起点。给 条边各分配一个不同的编号;在边的两个端点的邻接表中,都记录另一端及同一个边编号。每条边只有一个布尔(Boolean)标记 used[e],两个端点共享它,而不是分别标记。每个顶点各有一个邻接表游标,初始指向第一项。
栈操作的精确定义
栈初始只有 ,输出列表 初始为空。只要栈非空,就令 为栈顶顶点,执行以下操作。
- 将 的游标向前移动,跳过边已标记为使用的条目。
- 若仍有条目 ,将游标移过该项,把 标记为已用,并将 的一次新出现压入栈。
- 否则弹出栈顶这一次出现的 ,把 加到 的末尾。
栈空时,把 反转,得到路线。每个压入的栈项还可以记录进入它所用的边编号;弹出时依次记录这些编号,略去最初栈项的空编号,再把边编号列表反转,就得到相应的边顺序。
以后再次访问同一顶点时,不得把游标重置。弹栈也不会把任何边改回未用。栈遵循后进先出:弹出后,算法回到此前的位置,该位置的顶点可能已经出现过多次。
定理 2.1.6
(栈算法返回欧拉回路)
在上述连通性和偶数度假设下,反转后的输出是从 出发的闭迹,恰好使用全部 条边各一次,共有 次顶点出现。
为什么弹出的顺序能够拼成路线
证明
(每个阶段都回到起点)
把连续的压栈操作分成若干阶段:一个阶段从当前栈顶出发,在下一次弹栈之前结束。最初,未用边构成的图处处为偶数度。若阶段从 出发,却在 处无法继续,则本阶段用掉的边在 处贡献奇数度;阶段开始前那里为偶数度,因此还应剩下一条未用边,矛盾。于是每个非空阶段都回到其起点;没有压栈的阶段则直接留在原处。删去闭迹的边会使各点度数减少偶数,所以一个完整阶段结束后,未用边图又处处为偶数度。这个归纳只讨论完整阶段;单次压栈过程中,剩余度数未必是偶数。
因此,第一个弹出的顶点是 。再考虑以后任意一次弹栈。上一个顶点位置 被弹出后,若栈未空,它此前的栈项 成为栈顶。进入这一次 的栈边连接 。在下一次弹栈前插入的压栈阶段从 出发并回到 ,所以下一个弹出的顶点就是 。因此, 中相邻两项总是相邻顶点,连接它们的边正是较早弹出项的进入边。每个新栈项有一条不同的进入边,而且每个栈项只弹出一次。故 以及它的反转都恰好使用每条已选择的边一次。最初的栈底项没有进入边,且最后才弹出,所以 的最后一项也是 ;反转后的路线从 出发并回到 。
还须证明没有漏选边。每个到达过的顶点最终都会在没有未用关联边时弹出。假如正度分支中仍有一条未用边,取从 到它某个端点的路径。若路径上的边全已选择,该端点已经到达;否则,路径上第一条未选边的前一个端点已经到达。两种情况都与已到达顶点的关联边已用尽矛盾。故起始栈项之后共压栈 次,合计弹栈 次。
证明透视
弹栈规定插入次序,并非再次走过边
弹栈不表示实际沿已用边倒着走一遍,而是记录各个顶点位置的完成顺序。在 处探索的闭合绕行,会在输出反转后插入这一次 的位置。边标记保证不重复用边;剩余图的奇偶性保证反向弹出列表能够接起来。这是证明中两个不同的环节。
例题 2.1.7
(追踪共享顶点的两个三角形)
边为 ,从 出发,先选择第一个三角形的边。栈先变为 。最后的 没有未用边,于是弹出,得到 ,栈为 。此时 仍有未用边,沿 压栈,得到 。栈顶 的边已用尽,弹出它。继续弹出后得到
反转后为 ,正是在 中插入 得到的回路。暂时的输出 并不表示全部边已覆盖;较早的一次 仍在栈上等待处理。
运行时间与开放迹
在邻接表模型下,总共有 个条目。每个游标只向前移动,所以累计越过至多 项,其中包括已从另一端选择的边。每条边引起一次压栈,每个栈项引起一次弹栈和追加。反转需要 次操作。统计度数及预先搜索正度顶点的连通性都只需 时间。因此,若顶点和边的编号支持常数时间访问,整个过程的时间和空间均为 。这里 包括孤立顶点。若改用邻接矩阵,并让每个顶点的游标在其对应行中只向前移动,则至多检查 个单元,得到 的实现。若每次访问顶点都从头扫描整行,开销可能更大;表示方式和游标规则都不能忽略。
对于奇数度端点为 的开放迹,使用前面已证明的辅助构造:添加新顶点 和边 ,从 运行回路算法,再删去首尾两条边。由于 度数为二,它在此回路中只会出现在开始和结束处。剩余部分是以 为端点、只用原图边的迹;若方向不合要求,再反转。只增加一个顶点和两条边,不改变线性时间界。对有顶点但无边的图,单独返回该顶点即可。
练习:检查实现是否正确
快速检查
(图是两个互不相连的三角形,程序从其中一个三角形出发。返回序列确实是一条闭迹,为什么仍不能接受为整个图的欧拉回路?)
解答 · 答案
六条边中只有三条被选择,顶点出现次数为四,而不是七。另一个分支不可到达。证书必须覆盖给定图的整个边集,而不只是给出一条闭迹。预先检查正度顶点连通性就会拒绝这个输入。
快速检查
(省略奇偶检查,对中心为 、叶子为 的三边星图,从 出发。先选 ,再选 ,弹出 后再选 。反转输出会发生什么?)
解答 · 答案
弹出列表为 ,反转后为 。虽然三条边都已标记,列表也恰有 次顶点出现,但 不是边。四个奇数度顶点不符合任何一种欧拉判别法。因此,仅检查边数和边标记,不能证明返回的顶点序列正确;还须核对相邻端点及所声称的边编号。定理中的奇偶假设才是压栈阶段能够闭合的保证。
欧拉性质不等于哈密顿性质
概念视角组合
边与顶点回答不同的问题
欧拉回路恰好使用每条边一次;哈密顿圈在返回起点前恰好访问每个顶点一次。两者不同。上面共享一个顶点的两个三角形是欧拉图,却没有哈密顿圈:删除共享顶点后图不连通,而从哈密顿圈删除任意一个顶点后,剩下的边是一条经过其余所有顶点的路径。因此含哈密顿圈的图删除任一顶点后仍连通。这是必要条件,一般不是充分条件。
反过来,四顶点完全图有哈密顿圈 ,但每个顶点度数为 3,故没有欧拉回路。它有六条边,所写的哈密顿圈只使用四条。经过每个顶点的闭游走也不自动是哈密顿圈,因为它可能重复顶点。
快速检查
(正方形 加对角线 。求开放欧拉迹所有可能端点,并给出一条迹。)
解答 · 答案
各点度数依次为 ,所以唯一可能的端点是 。一条迹为 ,四条正方形边和对角线各用一次。
快速检查
(图由一个三角形和一个独立的孤立顶点组成。它有欧拉回路吗?有经过全部四个顶点的哈密顿圈吗?)
解答 · 答案
三角形本身就是欧拉回路,因为孤立顶点没有需要覆盖的边。不存在经过全部四个顶点的哈密顿圈:孤立顶点没有可供进入或离开的边。这一比较使用了孤立顶点不妨碍欧拉回路的约定。
常见错误
常见错误
(第一条闭迹未必完整)
在所有度数为偶数的假设下,沿未用边前进直到无法继续会得到闭迹,但第一条闭迹不一定包含全部边。在共享顶点的两个三角形中, 已经闭合,且 没有未用关联边,另一个三角形却尚未使用。此时停止会得到不完整答案;在 处拼接是把局部闭迹与剩余边连接起来的关键步骤。
这也说明连通性在论证中有两个作用。它是单条路线到达所有边端点的必要条件;在构造证明中,它还保证当前迹上有可连接未用边的位置。取迹上顶点 ,从它沿路径走向一条未用边的端点。若路径的边均已用过,其终点已在迹上,且连接未用边。否则,路径上第一条未用边的前一个端点在迹上,因为此前的路径边均已用过。因此总能找到拼接点。
快速检查
(某图有一个度为 5 的顶点,其他顶点度数都是偶数。这可能吗?)
解答 · 答案
不可能。度数之和将是奇数,与 矛盾;无论图是否连通都成立。这并不意味着只要奇数度顶点数为偶数就存在欧拉迹:四个奇数度顶点已排除单条欧拉迹。
快速检查
(对共享顶点的两个三角形,直接验证 是欧拉回路。)
解答 · 答案
相邻顶点形成的边依次是 ,它们互不重复,恰好是图的六条边;首尾均为 。重复经过 是允许的,因为定义禁止重复的是边而非顶点。
总结
对至少有一条边的有限图,检查连通性时忽略孤立顶点。剩余顶点度数全为偶数时有闭欧拉迹;恰有两个奇数度顶点时有以它们为端点的开放迹。重复顶点的迹仍可能是欧拉迹,重复边则违反定义。奇偶判别法证明存在,边序列提供可核查的路线;哈密顿圈则是不同的顶点条件。
这些判别法适用于上述有限无向图;有向图需要另行检查入度和出度条件。