6.2 哈密顿图
本章目录 · 2 节
本章导读
【定义6.2.1:顶点必须恰好经过一次】经过图中每个顶点一次且仅一次的通路,称哈密顿通路;经过每个顶点一次且仅一次、并回到起点的回路,称哈密顿回路。回路的起点在书写时也作为终点重复一次,这不算重复经过一个中间顶点。存在哈密顿回路的图称哈密顿图;存在哈密顿通路但没有哈密顿回路的图称半哈密顿图。平凡图按教材约定为哈密顿图。
欧拉问题关注边:每条边恰用一次,允许重复顶点。哈密顿问题关注顶点:每个顶点恰到一次,许多边可以不用。对至少3个顶点的简单图,哈密顿回路就是经过全部顶点的圈。存在哈密顿通路并不等于“半哈密顿”:还须排除哈密顿回路。
回看图6.1.1:三个无向图(a)、(b)、(c)均包含外围四边圈,因此全为哈密顿图,虽然它们的欧拉性质不同。有向图(d)有有向四圈;图(e)有通路 ,但源点 无入边,不能有哈密顿回路,故为半哈密顿图;图(f)中从 或 出发只能到达无出边的 或 ,无法覆盖四点,因而两种性质都没有。六幅图及全部箭头见6.1。
【定理6.2.1:删点后的分支数必要条件】设无向图 为哈密顿图,则对任意非空真子集 ,有 ,其中 表示连通分支数。
证明:取哈密顿圈 。删去 个顶点,至多把圈切成 段,每段是一条路径;若被删顶点相邻,段数还会减少。原图 含有 的全部边,额外边只能合并分支,不能增加分支,所以 。这个证明只要求“至多”,不需要假定任意给定的 都能在圈上互不相邻。
这个条件是必要条件,不是充分条件。彼得松图满足该删点条件,却没有哈密顿回路。可从3正则性进一步检查:假若存在哈密顿回路,删去回路后余下的边必为完美匹配;彼得松图的6个完美匹配逐一取补后均为两个互不相交的5圈,而不是一个10圈,故不可能。
【推论6.2.1:哈密顿通路的必要条件】只要图有哈密顿通路,就有 ,对半哈密顿图当然也成立。证明:删去一条覆盖全部顶点的路径上的 个点,至多留下 段,加入其他边不会增加分支。也可在原通路两端加一条新边闭合,再用定理6.2.1;直接切路径的证明更容易处理端点被删除的情况。若发现某个 使分支数超过这个界,就能同时排除哈密顿图和半哈密顿图。
【例6.2.1:三幅二部图】二部图的回路必须在两部之间交替,因此哈密顿回路要求两部顶点数相等;哈密顿通路只允许两部数量相等或相差1。数量满足只是必要条件,还必须检查实际连边。
图(a)两部为 、。删去 留下4个孤立点,而 ,所以连哈密顿通路也不存在,既非哈密顿图也非半哈密顿图。
图(b)两部为 、。删 留6个孤立点,大于 ,所以无哈密顿回路;但 是经过全部11点的通路,每一相邻对都有边。因此它为半哈密顿图。
图(c)两部为 、; 是一条哈密顿回路,故为哈密顿图。判断依据是实际找到了该回路,不能只凭两部大小相等。(例完)
【注6.2.1:二部图的数量障碍】若两部大小为 ,且均至少2,则哈密顿图必有 ;半哈密顿图只可能 或 ; 时两者都不是。平衡二部图也可能没有哈密顿通路,例如图的连边不足时,数量条件不能补救。
【定理6.2.2:哈密顿通路的度数和充分条件】设 为 阶无向简单图。若每对不相邻的不同顶点 都满足 ,则存在哈密顿通路。这里是“每对不相邻顶点”,不是“找到一对”即可。
先证连通。若 属于两个不同分支,分支阶数为 ,则 ,与条件矛盾;原证明这一步宜写不等号 ,允许图恰有两个分支的情形。
再取一条最长初级通路 。用“最长”保证无法得到更长通路会产生矛盾;只任取一条两端不能延长的通路不足以替代最长性。若 ,已经完成。若 ,两端的全部邻点均在 上。若两端相邻,闭合得到过全部 点的圈;否则令 ,。
有 ,所以 。取交集中一个 ,得到圈 ,经过原通路全部顶点一次。这里 的情况可直接检验;在 的连通图中最长通路至少含3个顶点,闭合圈的步骤没有长2的简单图退化问题。
圈外还有顶点。由连通性,存在圈外顶点 与圈上某顶点相邻。切开该顶点的一条圈边并接上 ,得到比 多一个顶点的初级通路,与最长性矛盾,所以必须 。
图(a)具体加入 与 ,可形成 ;图(b)删去其中边 并接 ,得到 。示意只固定下标以便看清构造,一般证明仍用任意 。
【推论6.2.2:哈密顿回路的度数和充分条件】设 ,若无向简单图中每对不相邻的不同顶点都满足 ,则有哈密顿回路。
由定理6.2.2先取哈密顿通路 。若两端相邻,直接闭合;否则仿上面的指标集合 ,此时大小之和至少 ,而下标只有 个,故必相交,从而按交叉连接构成经过全部顶点的圈。条件不满足时不能反推无哈密顿回路,例如长5圈本身就是哈密顿图,但某些不邻接点度数和只有4,小于5。
【定理6.2.3:满足度数和的新边可以安全加入】设 是 阶无向简单图中不相邻的两点,且 ,则 为哈密顿图当且仅当 为哈密顿图。
正向显然,加边不会破坏原回路。反向取 的哈密顿回路:若未用新边,它已在 中;若用了新边,删去新边得到 中从 到 的哈密顿通路。把两端记作 ,由前一推论证明里的指标交集方法,原图已有足够的交叉边来重新闭合,得到 中的哈密顿回路。注意度数是在加边前的 中计算。
【例6.2.2:八人的圆桌交谈】八位与会者中,对任意不能直接交谈的两人,各自能够交谈的其他人数之和至少8。证明可以排成一圈,使每个人都能同左右邻座交谈。
把人作为顶点,两人能够用至少一种共同语言交谈时连边,得到8阶简单图; 是与此人能交谈的其他人数。条件恰为每对不相邻点的度数和至少8,由推论6.2.2存在哈密顿回路。按回路顺序安排座次即可;不要求全体使用同一种语言,邻座之间有共同语言便足够。(例完)
【定理6.2.4:竞赛图必有哈密顿通路】每个 阶竞赛图都含哈密顿通路,但未必有哈密顿回路。
归纳证明:两顶点时唯一有向边就是所需通路。设已为删去一个顶点 后的竞赛图找到 。从左到右寻找第一个满足 的顶点。如果 ,把 放最前面;如果 ,此前各点都指向 ,故 ,可把 插在两者之间。如果根本没有这样的 ,所有 ,把 放最后。于是逐次插入可构造覆盖全部顶点的有向通路。
图中的弧是所需竞赛图的一部分,没有画出的非相邻顶点间弧可以取任一符合竞赛图定义的方向,不影响插入论证。传递竞赛图没有任何有向圈,所以本定理不能升级成“必有哈密顿回路”。
例6.2.3:三种典型图的判定
图(a)中按字母顺序 就得到哈密顿回路,共经过20个不同顶点,因此为哈密顿图。除这个20圈外的10条边为 ,方便逐边核对;所有顶点度数均为3。
图(b)删除 后,外五圈、内五圈各为一个分支,中间另有5个孤立点,共7个分支,大于 。所以没有哈密顿通路,也没有哈密顿回路;两种图都不是。画面只标出证明所用的五点,其余顶点圆点仍全部保留。
图(c)删 后, 各自孤立, 形成三角形,共4个分支,大于 ,故不是哈密顿图。但 是一条覆盖全部9点的通路,所以是半哈密顿图。(例完)
【周游世界问题与图6.2.5】1859年哈密顿设计在正十二面体上周游城市的游戏:20个顶点看作城市、棱看作道路,要求每城恰访一次并返回出发城市。它寻求的是哈密顿回路,绝非要求把全部30条棱都走一遍。
正十二面体有20个顶点、30条棱、12个五边形面,每个顶点关联3条棱。把一个面作为外部区域展开,得到与图6.2.4(a)同构的平面图;展开只改变画法,不改变顶点、边的关联。图(a)的字母顺序已给出游戏的一种解法。以上删点必要条件、度数和充分条件各有适用范围;不满足某个充分条件时,应继续寻找实际回路或其他反证,不能直接判为非哈密顿图。
