习题6

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

本章逐组保留习题6.1—6.23。欧拉问题要求每条边恰过一次;哈密顿问题要求每个顶点恰访一次。无向图默认允许重边,题目明确“简单图”时才排除。下文为原本未标号的习题图补上字母,仅用于说明对应关系,不增加顶点;线条相交且没有圆点的地方不是新顶点。

【习题6.1】判断四幅图的欧拉性;不是欧拉图时,至少加几条边才能变成欧拉图?

解:(a)就是6.1中的八顶点外圈与内圈之并,连通且各点为偶度,已经是欧拉图,加0条。

v1v2v3v4v5v6v7v8
6.1(a):连通偶度图

(b)由两个分离的三角形组成,各点虽为偶度,却不连通,因此不是欧拉图。至少加2条边:只加一条连接两分支的边,会使两端变奇,且该边为桥;在两分支各选一个顶点,加入两条相同端点、不同身份的平行边即可,既连通又保持偶度。

abcdef
6.1(b):两个分离的三圈

(c)由外五圈 、四圈 和三圈 相接构成; 为4度,其余点为2度,图连通,所以已经是欧拉图,加0条。应逐个数清原图圆点,不能把曲折的边看成开口通路。

abcdefghij
6.1(c):三个圈相接,十个实际顶点

(d)是两条互相分离的长2路径 与 ,交叉处没有顶点。四个奇度端点为 ,至少加2条边;加 可把两条路径接成六圈,所以最少2条。

abcdef
6.1(d):交叉处不连通的两条路径

【习题6.2】判断:(1) 时 都欧拉;(2) 阶有向完全图都欧拉;(3)正偶数 下 欧拉。

解:(1)假,每点度数为 ,当且仅当 为奇数时欧拉,例如 不欧拉。(2)真,图强连通,每点出入度都为 。(3)真,完全二部图连通,两部各点度数分别为 ,都为偶数。

【习题6.3】各画一个无向欧拉图,分别具有偶点偶边、奇点奇边、偶点奇边、奇点偶边。

解:依次取 ,,一个三圈和一个四圈只共一个顶点,一个三圈和另一个三圈只共一个顶点。对应 分别为 。后三种拼接都不合并边,每个接点度数为4,其余为2,所以满足欧拉判定。

abcd
6.3(1):四点四边
abc
6.3(2):三点三边
abcdef
6.3(3):六点七边
abcde
6.3(4):五点六边

【习题6.4】各画一个有向欧拉图,四种奇偶要求同6.3。

解:把6.3各组成圈都定成首尾相接的有向圈即可。接点出入度均为2,其余点出入度均为1;任一点可沿圈走到接点,再走到另一圈任一点,故强连通。顶点数与边数仍分别为 。

abcd
6.4(1):有向四圈
abc
6.4(2):有向三圈
abcdef
6.4(3):共一点的有向三圈与四圈
abcde
6.4(4):共一点的两个有向三圈

【习题6.5】 个互相分离、长度至少3的圈之间,最少加多少边可得到欧拉图?分别讨论无向、有向。

解:两者最少均为 条。无向情形把每个原圈收缩成一点;原圈各点为偶度,所以每个分支新增的外接边总数必须为正偶数,至少2,总新增边至少 。在每圈选一点,按圈的先后顺序把这些点接成一个连接各圈的循环,就用 边达到; 时用两条平行边。

有向情形中每个原圈对外至少需要一条入弧、一条出弧,才能使全图强连通,且新增出入差应平衡,故至少 弧。在选出的代表点之间加入一个有向 圈即可; 时是相反方向的两弧。若另禁止平行无向边,则 的构造约束改变,需要另行说明,原题没有这项限制。

【习题6.6】有向欧拉图必强连通。

证明:取欧拉回路。任意两点 都在回路上,从 沿回路方向能走到 ,再继续沿回路能走回 。两方向都可达,所以强连通。不能只因基图连通就断言有向图强连通。

【习题6.7】连通无向图恰有 个奇度顶点,证明所有边可分成 条两两边不重的简单通路。

证明:把 个奇度点任意配成 对,每对加一条带新身份的边。加边后连通且全偶,有欧拉回路。沿回路删去这 条新边,在各删除处切开,就得 段原图通路;各条原边恰落在一段中。新边的端点两两不同,因此两个新边不可能在回路上直接相接,切下的每段都至少含一条原边。各段没有重复边,符合本教材“简单通路”的定义;可能重复顶点,不应误写成 条顶点都不重复的初级通路。

【习题6.8】所有 都是哈密顿图吗?

解:按本书平凡图约定, 是; 时按任意顶点顺序绕一圈,都是。 只有一条边,不能形成由不同边组成的长2圈,因此不是哈密顿图,但有哈密顿通路。不能把同一条无向边往返两次当作哈密顿圈。

【习题6.9】无向连通图含桥或割点时不是哈密顿图。

证明:若含桥,桥两侧都有顶点,任何覆盖全部顶点的回路要跨到另一侧再回来,必须重复经过这条唯一跨边,不能是哈密顿圈。若含割点 ,则 ,违反定理6.2.1。反过来,“无桥、无割点”并不足以保证哈密顿性,彼得松图就是反例。

【习题6.10】证明定理6.2.3的加边等价性。

证明: 的哈密顿回路当然也属于 。反向若 的哈密顿回路不用新边,已经完成;若用新边,删去它得 中哈密顿通路 。令 ,,下标范围为1至 。,故存在公共下标 。于是 是原图中的哈密顿回路。

【习题6.11】彼得松图最少加几边能成为欧拉图?最少加几边能成为哈密顿图?

解:用外五圈 、内五角星 标号,辐条为 ,内边为 ,下标模5。原图10点全为3度,加一边至多改变两个奇度点,所以至少5条边才能全偶。加入 ,每点恰多一度,得到连通4正则图,恰用5条;这些都是原图没有的新边,即使要求新增后仍简单也可实现。

原图非哈密顿,所以至少加1条。序列 是原图的哈密顿通路,加新边 即闭合,因此最少1条。原图的准确结构见下图;字母标号与外内两层的对应已在文字中指定。

6.11:彼得松图,外五圈、内五角星及五条辐条

【习题6.12】证明原图(a)非哈密顿但半哈密顿,(b)为哈密顿图。

abcdefg
6.12(a):为原图七个顶点补上a至g标号

解:(a)顶点 都为2度,任一哈密顿回路必须使用它们各自的两条关联边,因而必须同时使用 ,使 在回路中至少关联三条边,矛盾。但 是哈密顿通路,故它为半哈密顿图。外侧曲线直接连到 ,曲线与其他线的无圆点交叉不能改成新顶点。

abcdefghijk
6.12(b):为原图十一点补上a至k标号

(b)哈密顿回路可取 ,其中11个点恰各出现一次,末尾返回起点;逐对检查都是原图边,故为哈密顿图。

【习题6.13】 人、,每人至少可与另外 人中的任一人配成二人组,共同完成熟悉的任务。能否把全部人分成 组?

解:若问题指能否把每个人恰分入一组、且每组成员能合作,答案是能。作兼容图,能合作连边,图有 点、最小度至少 ,任意不邻接两点度数和至少 ,所以有哈密顿回路;沿偶数长回路取第1、3、5、……条边,便得到覆盖全部人的 个互不相交二人组。

但若“完成 项任务”还要求 种指定任务各完成一次,原题缺少人、任务的对应条件,不能从上述无标号兼容图直接推出。例如所有人只共同熟悉任务1,仍满足每人可与至少 人合作,却无人能完成任务2。要证明不同指定任务的分配,还需要任务标签及相应匹配条件。不能用能组队冒充已完成任务分派。

【习题6.14】任意二人合起来认识其余全部 人;证明 时能排成邻者互识的队列, 时能排成邻者互识的圆圈。

证明:把认识关系看成对称的无向边。任一点若有两个不认识的人,这两人合起来就不认识它,违反条件,所以每点至多有一个非邻点,。当 ,不邻接两点度数和至少 ,由定理6.2.2有哈密顿通路;当 ,又有 ,由推论6.2.2有哈密顿回路。两者分别给出队列和圆桌次序。

【习题6.15】六种纱色,每色至少搭配其他三色;证明能选三种双色布,恰覆盖六种不同颜色。

证明:颜色作顶点、存在该双色布作边,得到6阶简单图,最小度至少3。不邻接两点度数和至少6,有哈密顿回路;沿六圈隔一条取一条边,得三条顶点互不重合的边,对应所需三种双色布。这是在求完美匹配,而不是必须生产这条六圈上的全部布种。

【习题6.16】 中有多少条不同哈密顿回路?原题特别约定顶点排列顺序不同就算不同。

解:按该约定答案为 :任意 个顶点的排列都可首尾相接,且依题意把不同起点、不同方向的排列分别计算。若固定起点只剩 ;若忽略起点及反向,通常的无向圈数为 。三种计数不能混用,6.3的四城例子采用最后一种,所以只有3条;本题则四城有24个排列。

【习题6.17】证明3×4棋盘有马的周游,3×3棋盘没有;周游不要求最终回到起点。

解:以“行、列”从1开始,3×4可按下图格内编号1至12走。具体为 ;相邻坐标差绝对值恰为1和2,且12格全部不同。

147108112536912
6.17:3行4列棋盘的开放马周游编号

3×3棋盘中心 没有任何合法马步邻点,是马步图的孤立顶点,所以不可能存在覆盖全部9格的通路。仅凭黑白格数差来判定本题不够:3×3的黑白格数量只差1,仍允许开放通路的颜色数量要求,真正障碍是中心孤立。

【习题6.18】 阶简单图有 条边,证明必哈密顿;少一条边则不一定。

证明:任取不邻接点 ,除去二点后的边至多 条,故 。如果 ,则 ,矛盾。所以所有不邻接两点度数和至少 ,应用推论6.2.2。少一条的反例为 上再附一个悬挂点,边数恰为 ,悬挂点使哈密顿回路不可能。

【习题6.19】删点条件 对每个非空真子集都成立,能推出哈密顿吗?

解:不能。彼得松图满足全部删点条件,却不是哈密顿图。6.2已用它的6个完美匹配说明没有哈密顿回路;这是必要条件并非充分条件的反例。不能把定理6.2.1的方向倒过来使用。

【习题6.20】哈密顿简单图是否必对每对不邻接点满足度数和至少 ?

解:不是。取 ,它本身就是哈密顿回路,但任意不邻接两点度数和均为4,小于 。度数和条件是充分条件,并非必要条件。

【习题6.21】按原两幅带权图,用迪杰斯特拉法求 到其余各点的最短路径和距离。

636322581136v1v2v3v4v5v6v7v8z
6.21(a):保留上方未印标号的孤立圆点,单独记z

解:(a)依编号打破同距并列,永久标号次序为 。最终距离按 顺序为 。最短路径依次为:到 走 ;到 走 ;到 走 ;到 走 ;到 走 ;到 走 ;到 走 。原图上方还有一个无关联边的圆点,这里记 ,它不可达,距离 ,不得擅自删掉或连边。

4826323186v1v2v3v4v5z
6.21(b):中央原未标号的实际顶点记z

(b)中央圆点是实际顶点,记 ,与四个角点都有图示边;不能把它当作无圆点的交叉。永久标号次序为 。最终距离到 分别为4、6、10、8、7;一组对应最短路为 、、、、。到 另可走 ,同为10;并列路径不影响最短距离。

【习题6.22】设备首年价格11万元,逐年涨1万元;第1至5年维修费为5、6、8、11、18万元;使用1年后残值4万元,以后每多用1年减少1万元。求五年购置、维修计划。

解:按规划开始时购入第一台、期末计入残值的模型,以第 年年初为状态 ,终点6表示第五年末。若第 年购新机,到第 年初更新或结算,年龄 ,这段净成本为 ,其中累计维修费 ,金额单位万元。

有向无圈网络各边成本为:从1到2、3、4、5、6分别12、19、28、40、59;从2到3、4、5、6分别13、20、29、41;从3到4、5、6分别14、21、30;从4到5、6分别15、22;从5到6为16。只允许向后连接年份,不能倒退时间。

用 ,,得到 。最短状态路径为 :第一台用第1、2年,第3年初以3万元残值出售,买价13万元的新机;第二台使用第3、4、5年,期末残值2万元。净成本为 万元。

若题意是不在第五年末出售设备、只统计实际付出的现金,则同一购置计划现金净支出为51万元,期末仍持有价值2万元的设备;应明确结算口径。如果规划开始前已经有一台旧设备,还需给其初始年龄等条件,不能自行编造旧机状态替换本题模型。

【习题6.23】从派出所 出发覆盖全部街道并返回,求最短巡逻路线,单位为百米。

18937115810246766791012ABCDEFGHIJKL
6.23:原十二路口、十九街段及全部权值

解:街道总长度131。奇度点为 。三种配对成本为 ,,。最优配对把 沿 连接,再把 沿直连街道连接,即额外走 各一次,增加10。

一条达到下界的路线为 。它起终点都是 ,覆盖原19条边,额外重复恰为 ,总长度 个单位,即14100米。选择别的欧拉回路顺序也可以,但必须同时核对原边覆盖、重复次数、起终点和总长度。