顶点可以重访,边不能重用
假设要恰好检查每一段道路一次。经过同一个路口多次可以,但不能重复经过同一道路。区分顶点和边十分重要:欧拉(Euler)回路可以多次经过一个顶点,因而不必是通常意义下的简单圈。
以下 是至少有一个顶点的有限无向多重图。平行边是不同的边;允许自环,且一个自环对其顶点的度数贡献二。
定义 2.2.1
(迹、欧拉迹与欧拉回路)
迹是没有重复边的游走;欧拉迹恰好使用每条边一次。起点和终点不同时称为开放欧拉迹;起终点相同的欧拉迹称为欧拉回路。正度数顶点称为非孤立顶点,零度的孤立顶点不需要由正长度迹访问。
对于没有边的图,约定任取一个顶点处长度为零的游走是欧拉回路;不存在开放欧拉迹。以下判据单独讨论至少有一条边的情形,因而非孤立顶点集合非空。
定理 2.2.2
(欧拉回路判据)
设 至少有一条边。存在欧拉回路,当且仅当所有非孤立顶点属于同一连通分支,且每个顶点的度数都是偶数。
定理 2.2.3
(开放欧拉迹判据)
设 至少有一条边。存在开放欧拉迹,当且仅当所有非孤立顶点属于同一连通分支,且恰有两个奇度顶点;这两个顶点就是开放迹的端点。
为什么度数必须满足奇偶条件?
证明
(把进入和离开配对)
迹经过一个顶点时,将进入所用的关联次数与离开所用的关联次数配对。自环在该顶点有两次关联,一次用于离开、一次用于进入,故对度数贡献二。闭迹在起点也能配对所有进入与离开,因此若闭迹恰用每条边一次,各顶点的度数均为偶数。
开放迹从 到 时,除 的首次离开和 的最后进入外,其他关联次数均可配对。因此 为奇度顶点,其余顶点度数为偶数。此外每条边的端点都出现在这条迹上,所以非孤立顶点在同一连通分支。以上只证明必要性,还没有构造所需的迹。
度数全偶时,拼接闭迹
证明
(延长并拼接闭迹)
假设非孤立顶点连通且所有度数为偶数。从任一非孤立顶点 出发,只沿未用过的边前进;只有当前顶点没有未用关联边时才停止。图的边数有限,过程必停止。
它不可能停在不同于 的顶点:在这样的顶点,一次到达后、离开之前,已用的关联次数为奇数;总度数为偶数,所以还存在未用的关联次数。自环按两次关联计数并作为整条边使用,不改变奇偶论证。因此这条不能继续延长的迹回到 ,是一条闭迹。
若它已用完所有边,便得到欧拉回路。否则暂时移去已用边。闭迹在每个顶点用掉偶数次关联,因此剩余图各顶点的度数仍为偶数。原图的非孤立部分连通,所以原闭迹上必有顶点与未用边相接:从闭迹出发沿原图走向一条未用边,取路径上第一条尚未使用的边,其起点就在闭迹上。
从这个共同顶点沿剩余未用边再次行走直到不能继续;同一奇偶论证给出另一条闭迹。将新闭迹拼入旧迹:沿旧迹走到共同顶点,走完新闭迹回到该点,再继续旧迹。所得迹仍闭合且不重复边。每次拼接至少使用一条先前未用边,而边数有限,因此过程最终用尽所有边。这同时证明回路存在并给出构造方法。
证明透视
每个假设在哪里用上
每个假设都在一个可以指明的位置用上。偶数度数用了两次,形式相同。起点以外的顶点一旦被进入,已用的关联次数为奇数,因此还有未用的关联,这迫使每条不能延长的游走回到起点闭合。一条闭迹在每个顶点用掉偶数次关联,所以剩余图的度数仍全为偶数,同一论证可以在其上再次进行。非孤立顶点的连通性在每次拼接时用一次,只用来保证当前闭迹碰到某条未用边;缺少它,构造会在另一个分支仍有边时停止,如下面两个互不相连的三角形。有限性两次给出终止:每次行走会停止,而每次拼接至少用掉一条新边。论证不依赖起点,也不依赖选取哪条未用边,所以这是一个构造方法,而不是搜索。
例题 2.2.4
(把两个三角形拼起来)
取顶点 ,边为 。两个三角形只共享顶点 。有 ,其余顶点度数均为 2。先走闭迹 ,再在 处拼入未用闭迹 ,得到
这条游走恰用六条边各一次。它重复经过 ,但没有重复边,因此是欧拉回路,尽管不是简单圈。
例题 2.2.5
(拼入一个自环)
设 的顶点为 ,边为 ,并在 处有自环 。则 ,,全为偶数,且图连通。从 出发走 ;回到 时它的两次关联都已用完,游走如证明所预言般停在起点。自环尚未使用,并在 处与这条迹相接。把闭迹 在 处拼入,得到 ,恰用四条边各一次。若自环只算一次, 的度数看似是奇数 ,判据便会错误地否定回路的存在。
恰有两个奇度顶点时
证明
(添加一条有标记的临时边)
假设非孤立部分连通,恰有 两个奇度顶点。添加一条连接 的新临时边;即使原图已有这两个顶点之间的边,也把新边作为另一条不同的边。现在 的度数变偶,其余度数不变,图仍连通。根据回路判据,扩充后的图有一条使用全部边的欧拉回路。
从回路的循环表示中选取起点,使临时边成为最后一条边,再删去它。剩下的游走恰用原图每条边一次,端点分别是 ,因此是开放欧拉迹。在多重图中必须标记临时边,以免与已有平行边混淆。
例题 2.2.6
(连接两个奇度顶点的开放迹)
在上述两个三角形的图中,给原图增加一条边 ,则只有 度数为奇数。一条从 到 的迹是
它依次使用 ,每条恰一次。这里 是题目图中的一条原边;证明中添加的临时边则是另外一条需要标记的边。
反例模式
仅有偶度不足以连接不同部分
两个互不相连的三角形中,每个顶点度数都是 2,但没有一条游走能够使用两个分支的所有边。有欧拉回路的图可以有孤立顶点,因为它们没有需要覆盖的边;却不能有两个各自含边的连通分支。故连通条件只针对非孤立顶点。
常见错误
(走到卡住得到的是闭迹,未必用完所有边)
当所有度数为偶数时,沿未用边走到不能继续,必定回到起点,但不一定用完每条边。在两个三角形的图中,游走 停在 ,而 仍未使用。拼接步骤是构造的一部分,不是可有可无的改良。
常见错误
(自环要算两次)
自环对其顶点的度数贡献二。在下面第一题中,若把 处的自环只算一次,会得到 、,即只有一个奇度顶点,而这在任何图中都不可能。正确的计数 表明欧拉回路存在。
练习与解答
快速检查
(设 的顶点为 , 之间有两条不同边 , 处有自环 。判断 是否有欧拉回路;若有,给出一条。)
解答 · 答案
自环贡献二,故 、。非孤立部分连通,因此有欧拉回路,例如 。标记边以区分两条平行边。
快速检查
(对路径 ,判断是否存在欧拉回路或开放欧拉迹。)
解答 · 答案
对 ,度数依次为 。非孤立部分连通,恰有奇度端点 ,因此有开放欧拉迹,图中显示的路径就是一条。由于有奇度顶点,不存在欧拉回路。
快速检查
( 有欧拉回路或开放欧拉迹吗?)
解答 · 答案
在 中每个顶点度数为 3,共有四个奇度顶点。尽管图连通,它既没有欧拉回路,也没有开放欧拉迹。两个奇度顶点的条件必须恰好满足。
应用判据时,先明确有无自环和平行边,自环按二计算;再忽略孤立顶点检查连通性,最后看度数的奇偶性。