6.1 欧拉图
本章目录 · 1 节
本章导读
【定义6.1.1:边必须恰好经过一次】欧拉通路经过图的每条边一次且仅一次,并经过全部顶点;欧拉回路还要求起点、终点相同。存在欧拉回路的图称欧拉图;存在欧拉通路但不存在欧拉回路的图称半欧拉图。通路允许多次经过同一个顶点,只禁止重复边。教材规定平凡图 为欧拉图,其零长通路视作退化的欧拉回路。
本节要求覆盖全部顶点,因此多个孤立顶点不能被忽略;若采用只要求覆盖全部边的另一约定,则应先删去孤立顶点再应用相应判定。无向环算一条边,计度2;有向环使出度、入度各增1。平行边按不同边身份分别经过。
【图6.1.1:六个基本例图】为便于核查,在四角统一标号: 左上、 左下、 右下、 右上。
图(a)度数为 ,为欧拉图。例如从 出发,边序列 恰好覆盖全部边并返回 。
图(b)中 为奇度顶点,只有开放的欧拉通路,故为半欧拉图。从 出发, 终止于 。
图(c)四个顶点全为3度,既不是欧拉图,也不是半欧拉图;外侧曲线 直接连接 ,不经过 ,图中没有额外顶点。
图(d)是强连通有向图,各顶点入度、出度均为1,所以是欧拉图, 是一条欧拉回路。
图(e)按 的出度减入度依次为 ,不符合开放或闭合欧拉通路的平衡要求。
图(f)也不满足欧拉判定: 各有两条出边而无入边, 各有两条入边而无出边。因此图(e)、(f)都不是欧拉图或半欧拉图。
【定理6.1.1:无向欧拉图判定】无向图 为欧拉图,当且仅当 连通且没有奇度顶点。
必要性:一条覆盖全部边、全部顶点的回路保证图连通。在任一顶点,每次进入与随后离开贡献2度,起终点也配对,故所有度数为偶数。
充分性采用逐步插入回路的构造。非平凡连通图中,任选有边的顶点出发,每次选一条未使用边。只要尚未回到起点,当前点已经用掉的关联边数为奇数,而原度数为偶数,故一定还存在可离开的边;有限步后可在起点闭合。若仍有未使用边,连通性保证已走回路上某顶点关联未使用边;从该点在剩余图中再走闭合回路,然后插入原回路。每次至少使用一条新边,最终全部边均被用一次,得到欧拉回路。每次删去闭合回路后,剩余各顶点的度数仍为偶数,是构造能反复进行的关键。
图中主圈为 ,在 分别接上小圈。沿主圈每到一个接点,先走完该小圈回到接点,再继续主圈。小圈之间、与主圈之间都不重复边,接点可以重复。
【哥尼斯堡七桥问题】把两个岛记为 ,两岸记为 ;每座桥对应一条无向边,两座连接同一对陆地的桥必须保留为两条平行边。
边的重数为 两条、 两条、 一条、 一条、 一条,因此 。四点全为奇度,既无欧拉回路,也无开放欧拉通路:不论是否要求回到起点,都不可能每桥只过一次。欧拉于1736年发表对此类问题的研究,七桥问题也是本节名称的来源。
【定理6.1.2:无向半欧拉图判定】无向图为半欧拉图,当且仅当图连通且恰有两个奇度顶点。两个奇度顶点必为开放欧拉通路的起点、终点;它们可以相邻,不需要添加“不相邻”的限制。
必要性:除起终点外,进入与离开都配对;起点多一次离开,终点多一次进入,因此恰有两个奇度点。充分性:设两奇度点为 ,加一条带新身份的边 ,即使原来已有边也允许增加平行边。新图连通且全为偶度,有欧拉回路;把该回路从新边处切开并删除新边,就得到原图从 到 的开放欧拉通路。切开是把剩余边按回路顺序重新选起点,不能把任意边直接删除后仍当作闭合回路。
【定理6.1.3:有向欧拉图判定】有向图 为欧拉图,当且仅当 强连通且每个顶点满足 。平凡图按前述约定处理。
必要性由沿回路的可达性和每次进入、离开配对得到。充分性与无向图的插入构造相同,只能沿弧的方向走:若在非起点停住,已用入弧比出弧多1,与原入出度相等矛盾;故可先形成有向回路,再插入剩余有向回路。
【定理6.1.4:有向半欧拉图判定】有向图为半欧拉图,当且仅当图单向连通,且存在两个不同顶点 ,满足 、,其余顶点出入度相等。 是起点, 是终点;总度数为奇数的恰为这两点,但仅仅数奇度点不够,还必须检查各点的出入差。
说明与证明:在这组度数条件下,可将“单向连通”换成便于检查的“基图连通”。加弧 后得到基图连通且每点出入平衡的图。这样的图必强连通:若强连通分支不止一个,其凝聚图有一个没有入弧的源分支;对分支内顶点的出入差求和为0,便也不可能有出弧,与基图连通矛盾。故加弧后的图有欧拉回路,去掉新弧就得到从 到 的欧拉通路。反向由开放欧拉通路直接看出单向连通及这些度数差。两种连通写法只有与全部平衡条件一起使用才等价。
【圈分解与定理6.1.5】非平凡无向图是欧拉图,当且仅当它连通,且全部边可以分拆为若干个两两边不重的圈。这里各圈可以共享顶点,“边不重”不要求顶点也不重。
正向从欧拉回路中遇到重复顶点便切出圈,有限次切分可把全部边分完;反向每个圈对任一顶点贡献0或2度,若有自环也贡献2度,所有度数均偶,再结合连通性应用定理6.1.1。只有圈的并而不要求连通是不够的,例如两个互不相交的三角形。
这个图可分为四个三圈 、、、,如下分别展开。
也可分为外圈 与内圈 ,说明圈分解不唯一。
【例6.1.1:欧拉图没有桥】设无向欧拉图至少有两个顶点,证明 。由圈分解,每条边都在一个圈上;删除它仍有圈的其余部分提供替代通路,所以没有桥。图连通且无1边割集,故边连通度至少2。若允许单顶点带自环的图,它也可为欧拉图且没有桥,但通常的边连通度并无非平凡顶点分割可用,应单独约定,不能无条件把此数值结论套到该退化情形。
【弗勒里算法:桥必须在剩余图中判断】输入为已通过判定的无向欧拉图;输出应是一条欧拉回路,而不是“无输出”。从任一顶点开始,维护未使用边集合 与当前顶点 。若 关联未使用边,优先选其中在剩余图 中不是桥的一条;只有没有其他边可选时才允许走桥。把该边加入答案、从 删除,并移动到另一端。重复直至 为空,最后应回到起点;若仍有边却在当前点无法继续,则应检查输入是否欧拉图或此前选桥是否违规。
环不可能是桥;若有多条平行边,删除其中一条时仍可沿另一条连通。不能只在最初的图上检查一次桥,因为随着走过的边被删去,桥的位置会变化。简单实现每次重新搜索桥,时间约为 ;上文的插入回路法用适当邻接表与边身份记录可实现为 。这里两种方法用于同一判定,不改变教材目录。
【例6.1.2:提前走桥造成停路】图中外边依次为 ;内部为 。
有人从 依次走 ,回到 后无法继续,却仍有未走边。错误发生在选择最后的 时。此前六条边已删除,剩余图如下; 是通向只剩一条关联边的 的桥,而当前 还可选非桥 或 ,所以不得先走 。
一种正确边序列是 。对应顶点依次为 ,十四条边各用一次。走到 时选 、走到 时选 ,虽然当时这些边是桥,却因没有其他可走边而合法;第一次到 时应选 或 ,不能抢先走当时的桥 。
【一笔画的含义】本节教材所说“能一笔画出”特别要求画完返回起点,对应欧拉回路。日常也把不抬笔但允许不同终点的画法称一笔画,这时半欧拉图同样可以;解题时应先读清是否要求返回起点。
