动机
单行道路只能按一个方向行驶。若把它当作无向边,就可能错误地以为可以原路返回。有向图明确表达这种不对称。我们先区分两种常见的连通性,再证明何时能沿每条有向边恰走一次并返回起点。
定义
定义 5.1.1
(有向图、游走与连通性)
有限有向图有有限顶点集 和有限有序边集,边 称为弧。本节排除自环和重弧,但允许不同顶点之间两个相反方向的弧。出度 计算离开 的弧数,入度 计算进入 的弧数。
有向游走沿每条弧的指定方向前进;有向路径是不重复顶点的有向游走。有向迹不重复弧。长度为零的路径使顶点可达自身。若每个顶点都能到达其他每个顶点,图称为强连通;若忽略方向后得到的无向图连通,则称为弱连通。强连通蕴含弱连通,反之不然,例如仅有一条弧 的图。
定义 5.1.2
(有向欧拉(Euler)回路)
有向欧拉回路是恰好使用每条弧一次的闭有向迹。入度和出度之和为零的顶点称为孤立顶点。与无向情形相同,只检查有弧关联的顶点之间的连通性。若图至少有一个顶点而没有弧,我们允许长度为零的回路;下述主要判别法假设至少有一条弧。
定理/命题
定理 5.1.3
(有向欧拉回路判别法)
至少有一条弧的有限有向图存在有向欧拉回路,当且仅当每个顶点满足 ,且所有关联弧的顶点属于同一个弱连通分支。
定理 5.1.4
(平衡使弱连通变为强连通)
若有限有向图每个顶点入度等于出度,且非孤立顶点弱连通,则这些顶点强连通。
证明思路
证明
(进入与离开配对,再拼接闭迹)
必要性:闭有向迹在每个顶点把每次进入与下一次离开配对;起点的最后进入与最初离开配对。若恰好使用所有弧,入度等于出度。忽略回路的方向得到一条经过所有弧端点的游走,因此非孤立顶点弱连通。
充分性:从非孤立顶点出发,沿未用的出弧前进,直到没有可用出弧。所得迹必定终止于起点。因为在其他顶点,若迹当前终止于此,已用入弧比已用出弧多一;原来的入度等于出度,故必有未用出弧。所以不可能停在不同于起点的顶点。
若还有未用弧,暂时删除当前闭迹的弧。闭迹在每个顶点删除相同数量的入弧和出弧,故剩余有向图仍平衡。当前迹上存在与未用弧关联的顶点:从迹沿一条弱路径走到某条未用弧的端点。如果路径中有未用弧,第一条未用弧的前一端点在迹上,因为此前的弧都在迹上;如果路径全由迹上的弧组成,其终点就在迹上,并与最初选定的未用弧关联。剩余弧的平衡性说明剩余入度为正当且仅当剩余出度为正。因此可从该点沿未用出弧走出另一条迹;同样的论证说明它闭合。把新迹拼入原迹,每次至少消耗一条新弧,有限次后使用全部弧。
证明透视
剩余平衡如何允许拼接
平衡在两个不同地方被使用。在“走到无路可走”一步,它用于当前终点:起点以外的顶点进入的次数比离开多一次,原来的入度等于出度,故仍有未用的出弧。只有起点能吸收最后一次进入,因为它的第一次离开没有对应的进入。在拼接一步,平衡用于剩余图:删除一条闭迹会在每个顶点删除同样多的入弧和出弧,所以剩余的弧仍平衡,同一论证再产生一条闭迹。
弱连通只用来找出新闭迹与旧闭迹相接的顶点;它从不提供方向,正是剩余平衡把“与未用弧关联”变成“有未用出弧”。每次拼接至少使用一条新弧,所以过程会终止。没有弱连通,拼接点未必存在,例如两个互不相连的三角形;没有平衡,第一条迹可能停在起点以外,例如 。
证明
(从回路读出有向路径)
第二个定理随之得到:经过所有非孤立顶点的欧拉回路中,从任一顶点到另一顶点都有一段有向游走;删除重复段可得到有向路径。孤立顶点不包括在结论中,因为它不能到达其他顶点。
例题详解
例题 5.1.5
(有向三角形)
弧 、、 使每个顶点各有一条入弧和出弧。路线 是有向欧拉回路。在此例中它也是有向哈密顿(Hamilton)圈,但两者的定义要求不同。
例题 5.1.6
(弱连通但不能返回)
对 ,忽略方向后的图连通,但 不能到达 。两端也不平衡: 出度 1、入度 0, 则相反。不存在使用两条弧的闭有向迹。
例题 5.1.7
(平衡但不连通)
取两个互不相连的有向三角形。每个顶点都平衡,但非孤立顶点属于两个弱连通分支。没有单条有向迹能够使用两个分支的弧,因此只有平衡而无连通条件不够。
常见错误
常见错误
(把弱连通当作可以双向通行)
弱连通忽略箭头方向,一般不能推出双向可达。在 上,底层图连通,但 不能到达任何顶点。上面推得强连通依赖每个顶点的度数平衡。
常见错误
(只检查总数平衡而非逐点平衡)
总入度等于总出度在任意有限有向图中自动成立,因为每条弧对两个总数各贡献一。它不能推出每个顶点各自平衡,而判别法要求的正是逐点平衡。
常见错误
(混淆欧拉回路与哈密顿圈)
欧拉回路关注弧,哈密顿圈关注顶点。回路可在使用不同弧时重复经过顶点。两个有向三角形仅共享一个顶点时,有经过两个三角形的欧拉回路,却没有哈密顿圈:删除共享顶点后,底层无向图不连通。
反例模式
强连通不能代替平衡
断言:强连通有向图必有有向欧拉回路,因为每条弧都可以到达,也可以离开。取弧 、、 与 。圈 使图强连通。但 、,而 、。使用全部四条弧的闭迹要离开 两次却只进入一次,这不可能。事实上迹 用尽所有弧后停在 ,而 唯一的出弧已被用去。判别法要求每个顶点平衡;强连通是平衡加弱连通的推论,而不是平衡的替代品。
总结
平衡是逐点的局部条件,非孤立子图弱连通是全局条件。两者合起来给出使用所有弧的闭路线,进而得到非孤立顶点之间的强连通;没有平衡时,弱连通与强连通不同。
练习
快速检查
(图含 、,另有孤立顶点 。按上述约定,它有有向欧拉回路吗?)
判断连通条件涉及哪些顶点。
解答 · 答案
有。迹 使用两条弧。孤立顶点没有待经过的弧,不计入连通性检查。
快速检查
(图含 、、。指出一个失败的欧拉条件。)
计算每个顶点的入度和出度。
解答 · 答案
的出度为 、入度为 ,平衡失败。所以图没有有向欧拉回路,即使非孤立底层无向图连通。
顶点集边界上的度数平衡
对 ,以 记从 指向其补集的弧数,以 记从补集进入 的弧数。
引理 5.1.8
(边界平衡恒等式)
在任意有限有向图中,对每个 ,
特别地,若每个顶点平衡,则对每个 都有 。
证明
( 内部的弧相互抵消)
对 中各顶点 求 之和,并按端点位置把弧分类。两端均在 内的弧在尾端贡献 、在头端贡献 ,相互抵消。离开 的弧只在尾端贡献 ,进入 的弧只在头端贡献 ,两端都不在 的弧没有贡献。所以总和为 。
若每个顶点平衡,则每个顶点集的进入弧数与离开弧数相等。这解释了平衡有向图为何不能在两个组之间有单向瓶颈。但这一恒等式本身不能排除互不连通的组,因此仍需要弱连通假设。
有限有向图中,要求两个顶点互相可达得到一个等价关系,其等价类称为强连通分支。把每个强连通分支收缩成一个顶点,并保留不同分支之间的弧,所得缩点图是有向无圈图:若不同分支形成有向圈,圈上各分支将互相可达,本应属于同一分支。
这给出“平衡加弱连通蕴含非孤立顶点强连通”的另一证明。
证明
(经缩点图的第二个证明)
先限制在非孤立顶点诱导的子图;它仍然平衡,且依假设弱连通。对该子图缩点,假设所得缩点图有不止一个顶点。有限有向无圈图必有源点:从任一顶点反复沿入弧向前追溯;有限且没有有向圈,所以最终停在没有入弧的顶点。在有不止一个顶点的弱连通缩点图中,该源点必须有出弧。令 为其对应的原图顶点集,则 、,与边界平衡矛盾。所以非孤立顶点只有一个强连通分支。
此证明没有假定弱路径有一致方向。它仅在缩点后用弱连通保证所选源点至少关联一条弧,再用平衡排除这些弧全向外的可能。若本来只有一个非孤立强分支,结论已经成立;没有弧的图不在该非孤立连通结论的范围内。
快速检查
(平衡有向图中,若恰有三条弧离开顶点集 ,有多少条弧进入 ?)
应用边界平衡恒等式。
解答 · 答案
边界平衡恒等式给出 。两端都在 的弧不影响此计数。
可达性与矩阵
将顶点编号为 。定义邻接矩阵 :存在弧 时 ,否则为零。
命题 5.1.9
(邻接矩阵的幂计算游走数)
按这个行到列的约定,对每个非负整数 , 等于从 到 的长度 有向游走数; 计算长度零游走。
证明
(对游走长度作归纳)
时,从 到 的长度零游走存在当且仅当 ,与 相符。设命题对 成立,则
每条从 到 、长度为 的游走,都唯一地分拆为从 到其倒数第二个顶点 的长度 游走,再接上弧 。对应 的项恰好计算这些游走,所以总和计算了全部游走。
例如有向三角形 有
计算游走 ;,因为从 3 出发的两步游走终止于 2。矩阵计数的是游走,不一定是路径:较长游走可以重复顶点或弧。如果有向游走连接两顶点,删除重复顶点之间的段,便得到相同端点的有向路径。
概念视角代数
可达性即矩阵和的正性
令 。路径长度至多为 ,每条游走都可缩短为路径,而每条路径都是游走。因此 可由 到达当且仅当 ;不同顶点互相可达当且仅当 且 。图强连通当且仅当 的每个元素都为正。关于路线是否存在的命题,变成了一个可计算的整数矩阵的符号条件。
矩阵元素是整数计数,不是模二算术:若两条不同的两步游走连接 ,整数项为 2,但在 中为零,可能错误地暗示不可达。
快速检查
(上面的有向三角形中,从 出发走四步终止于何处?)
每个顶点恰有一条出弧。
解答 · 答案
三步后返回 ,再走一步到 ,所以 。每一步只有一个选择。
开放有向欧拉迹
定理 5.1.10
(有向欧拉迹判别法)
设有限有向图至少有一条弧, 为顶点。存在从 到 、恰好使用每条弧一次的有向迹,当且仅当 、、其余顶点都平衡,且非孤立顶点弱连通。
证明
(用辅助顶点把迹闭合)
设有向迹恰好使用每条弧一次,且起点 与终点 不同。在所有内部访问处将进入与离开配对; 有一条未配对的出弧, 有一条未配对的入弧。因此
其余顶点都平衡;沿迹忽略方向,可见非孤立顶点弱连通。这些条件加上非孤立顶点弱连通也充分。添加新辅助顶点 ,以及弧 、。扩充图平衡且非孤立顶点仍弱连通,故存在有向欧拉回路。把回路旋转到从 开始,再删除首尾两条弧,剩余迹从 到 ,恰好使用每条原弧一次。使用新顶点避免 原已存在时产生重弧。
这时所有弧可分成最少若干条迹,条数等于出度盈余的总和。
通往推广的路径
若许多顶点都不平衡会怎样?
这时所有弧可分成最少若干条迹,条数等于出度盈余的总和。
仍设非孤立顶点弱连通,并令 。一条开迹只在起点使 的计数加 ,在终点减 ,所以覆盖所有弧至少需要 条弧不交的迹。反过来,把盈余单位与亏缺单位配对,对每一对 加入一个新顶点 及弧 。扩大后的图满足回路判别条件;删去这 个新顶点,就把它的欧拉回路切成恰好 条迹。
快速检查
(弧为 、、、。是否存在使用全部弧的有向欧拉迹?若有,给出一条。)
找出不平衡的顶点。
解答 · 答案
平衡, 的出度多一, 的入度多一。非孤立底层图连通。迹 从 出发、以 为终点,恰好使用四条弧。它不能是回路,因为两个端点不平衡。