习题5

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

本章保留教材5.1—5.52全部习题组,并给出解法与必要的条件说明。无向图允许自环和重边,只有明确说“简单图”时才排除;环计度数2。简单通路、简单回路要求边不重复,初级通路、圈另要求除首尾外顶点不重复。有向边用有序对,无向边用无序端点对。图中的线条交叉只有标出顶点圆点时才是顶点。邻域不包含顶点自身,闭邻域再加入自身。下述长度不超过4的计数均指长度1—4;若计入零长通路,须另加单位矩阵。

【习题5.1】根据四个图的集合表示画图。四图的顶点均为 。

(1)无向边为 ,注意 上的环。

v1v2v3v4v5
5.1(1):带一个自环的无向图

(2)无向边为 ,即五边形圈。

v1v2v3v4v5
5.1(2):五阶圈

(3)有向边依次为 。相反方向的两条边必须分别画出。

v1v2v3v4v5
5.1(3):有向图

(4)有向边为 ;图有两个弱连通分支。

v1v2v3v4v5
5.1(4):两个弱连通分支

【习题5.2】给原题三幅图的顶点标号,写出集合表示。

解:统一把上端标为 ,左上端为 ,右上端为 ,右下端为 ,左下端为 ;图(c)中央的孤立顶点为 。这些标号见重绘图,换用其他一致标号也正确。无向边不能因绘制方向不同而重复计算。

图(a):。

e1e2e3e4e5abcde
5.2(a):五个顶点、五条边

图(b):,边 都连接 ,其余为 。这里 是带边身份的多重集合,不能把两条 间的边合并。

e1e2e3e4e5abcde
5.2(b):保留两条平行边

图(c):,边为 , 不与任何边关联。

e1e2e3e4e5e6e7abcdef
5.2(c):有向边及孤立顶点

【习题5.3】写出5.2三图的度数列,并写出有向图的出度列、入度列。

解:严格按5.2的 (图(c)再加 )次序:图(a)为 ;图(b)为 。两图度数和都为10,等于边数的2倍。

图(c)出度列为 ,入度列为 ,总度数列为 。自环在 的出度、入度中各计1,所以总度数计2;出度和、入度和都为7。

【习题5.4】分别求无向图中 的邻域、闭邻域,以及有向图中 的先驱元集、后继元集、邻域、闭邻域。

v1v2v3v4v5
5.4(a):无向邻域

解:(a) ,。两条通向 的平行边只贡献一个邻点,自环不增加开邻域的元素, 距离2而非邻点。

u1u2u3u4u5
5.4(b):有向先驱与后继

(b) ,,,。按本章约定先驱、后继元集不计自身;环的入度和出度仍分别计1。

【习题5.5】无向图有10条边,3度、4度顶点各两个,其余顶点度数小于3。至少有几个顶点?此时度数列、最大度、最小度是多少?

解:总度数20,四个指定顶点消耗 ,其余度数和为6;每个至多2,故至少还需3个。最少7个顶点,按非降次序的度数列为 ,。该下界能实现:在 上取圈边 ,再加 ;最后一条与原 平行,仍是允许的无向图。度数依次为 。

【习题5.6】(1)证明 。(2)求 阶非连通简单图的最多与最少边数。

证明:(1) 时,把各顶点的不等式 相加,再用握手定理 ,除以 即得。等号成立当且仅当图正则。

(2)设 ,最少0条,由空边图达到。最多为 ,由 加一个孤立顶点达到。若分支阶数为 ,,边数不超过 ;把两个分支的顶点并入同一完全图会增加边数,故最大只需两个分支;两阶数之积至少 ,极值分拆为 。

【习题5.7】有向图总度数列为 ,出度列为 ,求入度列及各种最大度、最小度。

解:逐项相减得入度列 。因此 。出度和、入度和均为5,故共有5条有向边。不能用总度数直接当成出度。

【习题5.8】6条无向边,3度、5度顶点各一个,其余均为2度顶点,求顶点数。

解:,所以 。总度数列为 ;这里不是简单图,5度顶点不受 的限制。

【习题5.9】分别画出度数列为 的简单图和非简单图。

解:简单图取边 :后三边构成三角形 ,顶点1悬挂在4上。非简单图取边 以及顶点2、3、4上的三个自环。两图均有4条边,度数按标号均为 。

1234
5.9:三角形附一条悬挂边
1234
5.9:含自环的另一实现

【习题5.10】9阶图每个顶点度数为5或6,证明至少有5个6度顶点或至少有6个5度顶点。

证明:设5度顶点数为 ,握手定理表明 为偶数。如果6度顶点数 ,前一结论成立;否则 ,结合偶性得 。两种情形覆盖全部可能。

【习题5.11】证明不存在面数为奇数且每个面都有奇数条棱的多面体。

证明:对通常闭合多面体,每条棱恰好属于两个面。各面边数之和因此等于棱数的2倍,为偶数;奇数个奇数相加却为奇数,矛盾。也可对偶为“面作顶点、公共棱作边”的图,得到奇度顶点数必为偶数。结论使用闭合多面体的关联条件,不适用于有边界、棱只属一个面的曲面。

【习题5.12】 阶无向简单图满足 ,求补图的最大度、最小度。

解:对每个顶点 ,。取最大、最小可得 ,。最大度对应原图最小度,不能保留原来的极值方向。

【习题5.13】6阶无向图最大度、最小度都为2,有几类非同构图?其中几类是简单图?

解:每个连通分支都是一个圈:一个顶点上的环记 ,两顶点间两条平行边记 ,其余为通常的 。故所有类型恰与6的整数分拆对应,共11类。下面按分拆逐一画出;不同分拆的分支阶数不同,必不同构。只有分拆 和 不含1、2,对应的两个图才是简单图。

123456
5.13:分支阶数 1+1+1+1+1+1
123456
5.13:分支阶数 1+1+1+1+2
123456
5.13:分支阶数 1+1+1+3
123456
5.13:分支阶数 1+1+2+2
123456
5.13:分支阶数 1+1+4
123456
5.13:分支阶数 1+2+3
123456
5.13:分支阶数 1+5
123456
5.13:分支阶数 2+2+2
123456
5.13:分支阶数 2+4
123456
5.13:分支阶数 3+3
123456
5.13:分支阶数 6

【习题5.14】判断 与 是否可图化;可图化者给三种非同构实现,其中至少两种简单。

解:第一列和为23,违反握手定理,不能图化。第二列和为22,以下给出三种实现,全部按顶点1至8对应原列。前两个简单图的三角形数不同,故不同构;第三个有自环,必与前两个不同构。

简单实现1:,三角形数为1。

12345678
5.14:简单实现1

简单实现2:,三角形数为0。

12345678
5.14:简单实现2

第三种取边 ,顶点1、2、3、4、5、6各有一个环,顶点7、8各有两个环;度数恰为给定序列。

12345678
5.14:含自环的实现

【习题5.15】判断三列能否简单图化,并为可简单图化者给出两种非同构实现:(1);(2);(3)。

解:(1)不能。两个6度顶点必须与其余全部顶点相邻;删去这两个顶点后,剩余五顶点度数为 。孤立顶点不能连接任何点,两个3度顶点便都必须连接其余三个非孤立点,迫使原为1度的两个顶点至少2度,矛盾。

(2)、(3)均可以。以下每组两个图的三角形数不同,因此不同构;逐项计度即可验证实现。

,三角形数4。

12345678
5.15(2):实现1

,三角形数5。

12345678
5.15(2):实现2

,三角形数0。

123456
5.15(3):实现1

,三角形数1。

123456
5.15(3):实现2

【习题5.16】画出 全部非同构子图,指出生成子图和自补图。

解:按子图自身的顶点集判断同构和自补。非空顶点集下,1、2、3、4阶分别有1、2、4、11类,共18类。下图逐一列出,同一阶按边数排序。所有4阶图都是 的生成子图;低阶图不是。自补图只有1阶无边图和4阶路径 (4阶3边、度数列 的那幅)。若把无顶点的零图也作为子图,再增加1类,合计19类;它也自补。

完整性说明:1—3阶直接按边数和度数列分类;4阶0、1、2、3边分别有1、1、2、3类,4、5、6边分别由2、1、0边图取补得到2、1、1类,合计11。3边的三类为三角形加孤立点、星 和路径 。

1
5.16:1阶第1类,0条边
12
5.16:2阶第1类,0条边
12
5.16:2阶第2类,1条边
123
5.16:3阶第1类,0条边
123
5.16:3阶第2类,1条边
123
5.16:3阶第3类,2条边
123
5.16:3阶第4类,3条边
1234
5.16:4阶第1类,0条边
1234
5.16:4阶第2类,1条边
1234
5.16:4阶第3类,2条边
1234
5.16:4阶第4类,2条边
1234
5.16:4阶第5类,3条边
1234
5.16:4阶第6类,3条边
1234
5.16:4阶第7类,3条边
1234
5.16:4阶第8类,4条边
1234
5.16:4阶第9类,4条边
1234
5.16:4阶第10类,5条边
1234
5.16:4阶第11类,6条边

【习题5.17】画出3阶有向完全图的全部非同构子图,指出生成子图和3阶竞赛图。

解:有向完全图在每对不同顶点之间含两个相反方向的弧,不含自环。非空顶点集下,1阶1类、2阶3类、3阶16类,共20类;允许无顶点零图时共21类。所有3阶图均为生成子图。3阶竞赛图恰为两类:传递型三角形和有向三圈,均有3条弧且任意两顶点之间恰有一条弧。

以下列出全部代表。3阶按弧数0至6分组的类型数依次为 ;2弧的四类为有向链、出叉、入叉、二圈加孤立点;4弧类由2弧类在完整6弧中取补得到;3弧类分别为有向三圈、传递三角形、二圈加一条向外的弧、二圈加一条向内的弧。这给出不重不漏的分类。

1
5.17:1阶第1类,0条弧
12
5.17:2阶第1类,0条弧
12
5.17:2阶第2类,1条弧
12
5.17:2阶第3类,2条弧
123
5.17:3阶第1类,0条弧
123
5.17:3阶第2类,1条弧
123
5.17:3阶第3类,2条弧
123
5.17:3阶第4类,2条弧
123
5.17:3阶第5类,2条弧
123
5.17:3阶第6类,2条弧
123
5.17:3阶第7类,3条弧
123
5.17:3阶第8类,3条弧
123
5.17:3阶第9类,3条弧
123
5.17:3阶第10类,3条弧
123
5.17:3阶第11类,4条弧
123
5.17:3阶第12类,4条弧
123
5.17:3阶第13类,4条弧
123
5.17:3阶第14类,4条弧
123
5.17:3阶第15类,5条弧
123
5.17:3阶第16类,6条弧

【习题5.18】三个4阶4边无向简单图中至少有两个同构。

证明:分别取补图,得到三个4阶2边图。两条边或者相邻,或者不相邻,只有两类;由抽屉原理至少两个补图同构,进而原图同构。

【习题5.19】自补图的阶数为什么必须为 或 ?

证明:自补图与补图边数相等,因此 ,即 。检验模4余数得 或1。原题把两式中的 都写作正整数会漏掉 : 的补图仍为 。准确表述为: 时 , 时 (假设图非空)。这是必要条件,不表示任意这些阶数的图都自补。

【习题5.20】 阶简单图有 条边,求补图边数。

解:不同顶点构成 个无序对,每对恰被原图或补图之一选为边,所以 。

【习题5.21】求图中的全部点割集、边割集、割点、桥,以及点连通度、边连通度。

e1e2e3e4e5abcde
5.21:标定顶点和边

解:这里“割集”按本章定义指包含关系下的极小割集,不是任意能使图不连通的集合。点割集只有 。边割集为 以及四边圈中任取两边的六个集合,即 。割点只有 ,桥只有 ,所以 。凡含 的更大点集、含 的更大边集均不再极小。

【习题5.22】标定原图全部顶点和边,求割点、桥、点连通度、边连通度。

e1e2e3e4e5e6e7e8e9e10123456789
5.22:顶点1至9、边e1至e10

解:左四边圈为 ,右三角形为 ,另有悬挂边 和尾链 。全部割点为4、6、8;全部桥为 。删除其他任一顶点仍可通过相应圈的另一方向连通剩余局部顶点,其他边均在圈中。故 。

【习题5.23】求两侧各含一个 的原图的 。

1234567891011
5.23:两侧完全图、中央顶点及上方跨边

解:按重绘标号,两侧顶点集为 与 ,中央为6;额外边为 。最小度4。删去 可分开左右两侧,所以 ;删去任意一个顶点,两个完全图内部仍连通,中央两侧各有两个邻点,上跨边又提供另一连接,所以无割点,。

左侧与其余部分之间恰有3条边 ,故 。任删两条边,各侧 仍连通(任何非平凡分割至少切断4条边);中央至左右各有两条边,外加上跨边,在把每侧收缩成一点后得到“两条左中、两条中右、一条左右”的三顶点多重图,其任一割至少含3条边。因此 ,最终 。

【习题5.24】证明简单图同构当且仅当它们的补图同构。

证明:同构双射既保持相邻,也保持不相邻;后者恰是补图的相邻。因此同一个顶点双射也是补图同构。反向对补图再取补,使用 即得。

【习题5.25】画出5阶3边的全部非同构无向简单图。

解:共4类: 加孤立点、 加两个孤立点、 加孤立点、。若含圈,3条边只可能形成三角形;否则为森林,按非平凡分支的边数分配 或 分类( 需6个顶点,排除),得到其余三类。

12345
5.25:第1类
12345
5.25:第2类
12345
5.25:第3类
12345
5.25:第4类

【习题5.26】画出5阶7边的全部非同构无向简单图。

解:对5.25四个图分别取补,共4类,且彼此不同构。每幅有 条边。取补是同构类上的双射,因此不会遗漏其他类型。

12345
5.26:5.25第1类的补图
12345
5.26:5.25第2类的补图
12345
5.26:5.25第3类的补图
12345
5.26:5.25第4类的补图

【习题5.27】6阶2正则图有几类非同构情况?

解:若沿用本章一般无向图允许自环、重边的约定,与5.13相同为11类,所有图已在5.13逐一画出;如果题意另限定为简单图,则为 与 两类。不能不说明图的类别就给出唯一数字。

【习题5.28】 阶3正则简单图满足 ,有几类非同构图?

解:握手定理 ,得 。补图为6阶2正则简单图,只有 或 两类,因此原图也恰有两类:三棱柱图与 。前者有三角形,后者没有,故不同构。

123456
5.28:完全二部图K3,3
123456
5.28:三棱柱图

【习题5.29】 阶图有 条边,证明有顶点度数至少3。

证明:若全部度数不超过2,则度数和不超过 ,而握手定理给出 ,矛盾。等价地,平均度大于2。

【习题5.30】证明无向图的边是桥当且仅当它不在任何圈中。

证明:若边在圈上,删边后可沿圈的其余部分绕行,所以分支数不增加,不是桥。反之,非环边 若不是桥,删边后 仍连通;选一条最短的 通路,与 构成圈。环自身就是长1圈,且不是桥,也符合结论;两条平行边构成长2圈。

【习题5.31】已知简单图及其补图边数 ,确定阶数。

解:,所以 。须取非负整数阶数并检验根号及奇偶条件;给定整数若不满足条件,就不存在这样的图。约定非空图且 时为 ;若也允许无顶点零图,这一退化数据另有 。

【习题5.32】求彼得松图的点连通度和边连通度。

解:。度数全为3,故上界均为3。说明点连通度下界:采用外五圈 、内五角星 、辐条 的标号,下标模5,内边为 。删两点若都在同一层,另一层五圈完整,剩余各点经辐条连入;若各删一点,两层各剩一条连通路径,并仍有至少三条辐条连接,故仍连通。删一个或不删更连通,所以 。由 得结论。三个圈图形见5.2的彼得松图。

【习题5.33】桥 的端点 是割点当且仅当它不是悬挂顶点吗?

解:原题在允许自环的一般图中缺少条件。反例:只有 两点,边为桥 加 上一个环。, 不是悬挂顶点,但删 后只剩一个顶点,分支数没有增加, 不是割点。

若补充图无自环,则命题成立:桥把原所在连通分支分成 ,。 不是悬挂点意味着它还有不同于 的邻点(不能靠平行 ,否则 不是桥),所以 非空;删 后它与 分开, 为割点。反向若 ,删悬挂点不会增加分支数,故不是割点。更一般的准确条件为:删去桥后,含 的一侧还含其他顶点。

【习题5.34】 的简单连通图至少有两个非割点。

证明:取一条顶点数最多的初级通路 。若端点 是割点,删它后,通路其余顶点均在同一分支;在另一分支中必有原来与 相邻的点,可接在通路前端,得到更长初级通路,矛盾。同理 不是割点。因连通且 ,两端点不同。

【习题5.35】奇数阶简单图与其补图的奇度顶点数相等。

证明: 奇时 偶,而 ,两度数奇偶性逐点相同;所以不只数量相等,奇度顶点集合本身也相同。

【习题5.36】 时 中有几类非同构偶圈,长度各为何?

解:每个允许长度恰对应一类圈。长度为 ,共 类。简单图无长2圈;不能把同构圈的不同顶点选法重复计为不同类型。

【习题5.37】 阶有向完全图有几类非同构圈?

解:长度为 ,共 类。因为每对不同顶点间两方向都存在,所以长2有向圈允许;无自环,长1不允许。

【习题5.38】 阶竞赛图至多含几类非同构圈?

解:只有长度 可能,故至多 类。这个上界可达到:把顶点排成 ,除 外,其他边一律从小号指向大号。对任意 ,选 个中间顶点,依递增次序接成 ,便得长 圈。一般竞赛图不一定达到上界,例如传递竞赛图一个圈也没有。

【习题5.39】恰有两个奇度顶点的无向图中,这两点必然连通。

证明:每个连通分支自身也满足握手定理,奇度顶点数必须为偶数。若两个奇度点在不同分支,每个相应分支便恰有一个奇度点,矛盾。

【习题5.40】不同两点在无向完全图、有向完全图中的距离各为何?竞赛图中也恒定吗?

解:前两种图均为1,因为所需方向的边直接存在。竞赛图中不是常数:在传递型三顶点竞赛图 中 ,但 (不可达);即使只看强连通竞赛图,三圈中的顺向距离1、反向距离2,也不相等。

【习题5.41】简单图最小度至少2,证明存在长度至少 的圈。

证明:取最长初级通路 。 的所有邻点都在通路上,否则可以延长。设相邻的最大下标为 ,因至少有 个互异邻点,;边 与前段通路组成长 的圈。简单性排除自环、重边,保证邻点数等于度数。

【习题5.42】有向简单图最小入度、出度均大于0,证明存在长度至少 的圈。

证明:取最长有向初级通路 。 的所有先驱都在通路上,最大先驱下标 ,因此 是长至少 的圈。相似地, 的所有后继都在通路上,最小后继下标 ,得到 ,长至少 。从两圈中取较长者即可;不要求两个界由同一个最初构造的圈同时达到。原题的总最小度条件在两方向最小度均为正时自动满足。

【习题5.43】对原题有向图求非同构圈、简单回路、指定两点短程线与距离、连通类型,并对基图回答相应问题。

abcde
5.43:保留所有八条有向边

解:边为 。注意 的方向,且 无出边。这里按回路所用边及其关联关系分类同构,而不是把改变起点、走向或顶点名称另算一类。

(1)有向圈两类:长2的 与长3的 ( 同属长3类)。简单回路共3类:上述两类,加上一个三圈和一个二圈在一点相接的长5回路,例如 。不能再加长6回路:两个三圈共享弧 ,拼接会重复边,违反“简单回路”。

(2) 只有后继 ,故最短为 ,。(3) 到 最短为 ,距离3。(4) 为强连通分支,且都可到达 ,反向不行;任意两点至少一方向可达,所以是单向连通、非强连通图。

(5)基图保留 间的两条不同边,所以是多重图。非同构圈有4类,长度分别为2、3、4、5;代表为 ,,,。简单回路有7类:这四种圈,再加二圈与三圈相接的长5型、两个三圈相接的长6型、使用全部8条边的长8型。代表依次可取 ,,;长8型是三个分支顶点度4的欧拉子图。枚举闭合且每条边只用一次的边子图,可排除其他类型。基图中 与 不相邻,、 都是短程线,故两方向距离均为2。

【习题5.44】对图求 到 各长度通路数、 的回路数、全图计数及可达矩阵。

v1v2v3v4
5.44:自环在v1上,不在v4上

解:按 排列,邻接矩阵为 。矩阵乘法用普通整数运算,平行边各算一种选择。

(1)长度1、2、3、4的 通路数为 。(2)相应 回路数为 ,都只能在 的环上重复走。

(3)长度4全部通路数为16,其中回路3条。(4)长度1—4全部通路数为 ,回路为 。(5)含零步可达的矩阵为 。若“长度不超过4”也纳入零步,则通路总数为50、回路12;本题统计采用正文的正长度约定。

【习题5.45】对中心含顶点 的有向图求指定通路、回路计数及可达矩阵。

v1v2v3v4v5
5.45:中心处是实际顶点v5

解:按 排列,。(1) 长度1至4的通路数为 。(2) 相应回路数为 。(3)全图长4通路32条。(4)长度1—4的回路共12条,全部长度3;若含零长回路则另加5。(5)图强连通,可达矩阵为5阶全1矩阵。

复算方法:顶点分成三组 ,弧只按这三组依次循环。故回路长度只能为3的倍数。 的对角线为 ,和为12;各阶矩阵元素总和依次为8、12、20、32。

【习题5.46】给定邻接矩阵,求各顶点入度与出度。

解:矩阵为 。行和给出出度列 ,列和给出入度列 。两列之和各为7,与边数相等; 上的环各计一次出度与入度。

【习题5.47】由四行五列关联矩阵画出无向图。

解:。第一列2表示 上的环;第二、三列表示两条 间平行边;第四列为 ;第五列为 。因此下图在同构意义下唯一。

e1e2e3e4e5v1v2v3v4
5.47:由关联矩阵恢复的无向图

【习题5.48】为5.47的图写邻接、可达矩阵,计算 通路与 回路的长度1—4计数。

解:为使矩阵幂直接数“每次选择一条边”的通路,邻接矩阵对角元按自环条数计1,因此 。图连通,可达矩阵为4阶全1矩阵。 的通路数依次为 ; 的回路数依次为 。

这里必须区分两个常见约定:无向关联矩阵、顶点度数中的环计2;若有人把无向邻接矩阵对角元也定义为2倍环数,就不能直接把该矩阵的幂当作本题的边选择计数矩阵。例如本图 只有一个自环,长1回路只能是1条,绝不是2条。计数前统一约定,才不会系统性翻倍。

【习题5.49】,求完全二部图 中的圈类型数、最大独立顶点数、最大互不相邻边数、点连通度、边连通度。

解:(1)圈必须交替经过两部,长度为 ,恰 类。(2)最大独立集大小为 :同一部全部顶点互不相邻,跨两部任取一对却必相邻。(3)最大匹配大小为 :每条匹配边消耗小部一个顶点,至多 ,且可把小部逐点匹配到大部不同顶点达到。

(4)删去小部全部 个顶点使余下 点孤立,故 ;删少于 点,两部都仍非空,剩下完全二部图仍连通,故 。又 ,由 得 。

【习题5.50】证明 阶 边无向连通图满足 。

证明:从一个顶点开始,每次沿连接已访问集与未访问集的边加入一个新顶点。连通性保证只要未全部访问就能继续;加入剩余 点使用 条互异边,它们组成生成树,所以原图至少含这些边。 时为 ,仍成立。

【习题5.51】证明6阶简单图或其补图含三个彼此相邻的顶点。

证明:取顶点 ,其余5点中,至少3点都与 相邻,或至少3点都与 不相邻。前一情形选这3点:若其中某一对相邻,该对与 成三角形;若没有任何一对相邻,三点在补图中成三角形。后一情形交换原图、补图应用同样论证。这里“或”允许两图都存在三角形。

【习题5.52】容量500g、350g、150g的三个瓶从 出发,把油分为两个250g,至少倒几次?

解:按“每次倒至来源瓶空或目标瓶满、瓶上没有刻度”的规则,最少9次。按三个瓶容量的既定顺序,状态依次如下;每个箭头代表一次实际倒油。

。

例如第一步从500g瓶向350g瓶倒满,第二步从350g瓶向150g瓶倒满;最后从150g瓶把油倒回500g瓶,得到 。

最少性的检验:把每个状态作为顶点、每次合法倒油作为边,按距离0、1、2、……逐层扩展。从起点出发,第一次出现目标状态在第9层;每条边均对应一次倒油,因此不存在少于9次的方案。所有可达量都是50g的倍数,状态空间有限,可以逐一检查,而不依赖猜测方案。