习题5
本章目录 · 1 节
本章导读
本章保留教材5.1—5.52全部习题组,并给出解法与必要的条件说明。无向图允许自环和重边,只有明确说“简单图”时才排除;环计度数2。简单通路、简单回路要求边不重复,初级通路、圈另要求除首尾外顶点不重复。有向边用有序对,无向边用无序端点对。图中的线条交叉只有标出顶点圆点时才是顶点。邻域不包含顶点自身,闭邻域再加入自身。下述长度不超过4的计数均指长度1—4;若计入零长通路,须另加单位矩阵。
【习题5.1】根据四个图的集合表示画图。四图的顶点均为 。
(1)无向边为 ,注意 上的环。
(2)无向边为 ,即五边形圈。
(3)有向边依次为 。相反方向的两条边必须分别画出。
(4)有向边为 ;图有两个弱连通分支。
【习题5.2】给原题三幅图的顶点标号,写出集合表示。
解:统一把上端标为 ,左上端为 ,右上端为 ,右下端为 ,左下端为 ;图(c)中央的孤立顶点为 。这些标号见重绘图,换用其他一致标号也正确。无向边不能因绘制方向不同而重复计算。
图(a):。
图(b):,边 都连接 ,其余为 。这里 是带边身份的多重集合,不能把两条 间的边合并。
图(c):,边为 , 不与任何边关联。
【习题5.3】写出5.2三图的度数列,并写出有向图的出度列、入度列。
解:严格按5.2的 (图(c)再加 )次序:图(a)为 ;图(b)为 。两图度数和都为10,等于边数的2倍。
图(c)出度列为 ,入度列为 ,总度数列为 。自环在 的出度、入度中各计1,所以总度数计2;出度和、入度和都为7。
【习题5.4】分别求无向图中 的邻域、闭邻域,以及有向图中 的先驱元集、后继元集、邻域、闭邻域。
解:(a) ,。两条通向 的平行边只贡献一个邻点,自环不增加开邻域的元素, 距离2而非邻点。
(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条边,度数按标号均为 。
【习题5.10】9阶图每个顶点度数为5或6,证明至少有5个6度顶点或至少有6个5度顶点。
证明:设5度顶点数为 ,握手定理表明 为偶数。如果6度顶点数 ,前一结论成立;否则 ,结合偶性得 。两种情形覆盖全部可能。
【习题5.11】证明不存在面数为奇数且每个面都有奇数条棱的多面体。
证明:对通常闭合多面体,每条棱恰好属于两个面。各面边数之和因此等于棱数的2倍,为偶数;奇数个奇数相加却为奇数,矛盾。也可对偶为“面作顶点、公共棱作边”的图,得到奇度顶点数必为偶数。结论使用闭合多面体的关联条件,不适用于有边界、棱只属一个面的曲面。
【习题5.12】 阶无向简单图满足 ,求补图的最大度、最小度。
解:对每个顶点 ,。取最大、最小可得 ,。最大度对应原图最小度,不能保留原来的极值方向。
【习题5.13】6阶无向图最大度、最小度都为2,有几类非同构图?其中几类是简单图?
解:每个连通分支都是一个圈:一个顶点上的环记 ,两顶点间两条平行边记 ,其余为通常的 。故所有类型恰与6的整数分拆对应,共11类。下面按分拆逐一画出;不同分拆的分支阶数不同,必不同构。只有分拆 和 不含1、2,对应的两个图才是简单图。
【习题5.14】判断 与 是否可图化;可图化者给三种非同构实现,其中至少两种简单。
解:第一列和为23,违反握手定理,不能图化。第二列和为22,以下给出三种实现,全部按顶点1至8对应原列。前两个简单图的三角形数不同,故不同构;第三个有自环,必与前两个不同构。
简单实现1:,三角形数为1。
简单实现2:,三角形数为0。
第三种取边 ,顶点1、2、3、4、5、6各有一个环,顶点7、8各有两个环;度数恰为给定序列。
【习题5.15】判断三列能否简单图化,并为可简单图化者给出两种非同构实现:(1);(2);(3)。
解:(1)不能。两个6度顶点必须与其余全部顶点相邻;删去这两个顶点后,剩余五顶点度数为 。孤立顶点不能连接任何点,两个3度顶点便都必须连接其余三个非孤立点,迫使原为1度的两个顶点至少2度,矛盾。
(2)、(3)均可以。以下每组两个图的三角形数不同,因此不同构;逐项计度即可验证实现。
,三角形数4。
,三角形数5。
,三角形数0。
,三角形数1。
【习题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边的三类为三角形加孤立点、星 和路径 。
【习题5.17】画出3阶有向完全图的全部非同构子图,指出生成子图和3阶竞赛图。
解:有向完全图在每对不同顶点之间含两个相反方向的弧,不含自环。非空顶点集下,1阶1类、2阶3类、3阶16类,共20类;允许无顶点零图时共21类。所有3阶图均为生成子图。3阶竞赛图恰为两类:传递型三角形和有向三圈,均有3条弧且任意两顶点之间恰有一条弧。
以下列出全部代表。3阶按弧数0至6分组的类型数依次为 ;2弧的四类为有向链、出叉、入叉、二圈加孤立点;4弧类由2弧类在完整6弧中取补得到;3弧类分别为有向三圈、传递三角形、二圈加一条向外的弧、二圈加一条向内的弧。这给出不重不漏的分类。
【习题5.18】三个4阶4边无向简单图中至少有两个同构。
证明:分别取补图,得到三个4阶2边图。两条边或者相邻,或者不相邻,只有两类;由抽屉原理至少两个补图同构,进而原图同构。
【习题5.19】自补图的阶数为什么必须为 或 ?
证明:自补图与补图边数相等,因此 ,即 。检验模4余数得 或1。原题把两式中的 都写作正整数会漏掉 : 的补图仍为 。准确表述为: 时 , 时 (假设图非空)。这是必要条件,不表示任意这些阶数的图都自补。
【习题5.20】 阶简单图有 条边,求补图边数。
解:不同顶点构成 个无序对,每对恰被原图或补图之一选为边,所以 。
【习题5.21】求图中的全部点割集、边割集、割点、桥,以及点连通度、边连通度。
解:这里“割集”按本章定义指包含关系下的极小割集,不是任意能使图不连通的集合。点割集只有 。边割集为 以及四边圈中任取两边的六个集合,即 。割点只有 ,桥只有 ,所以 。凡含 的更大点集、含 的更大边集均不再极小。
【习题5.22】标定原图全部顶点和边,求割点、桥、点连通度、边连通度。
解:左四边圈为 ,右三角形为 ,另有悬挂边 和尾链 。全部割点为4、6、8;全部桥为 。删除其他任一顶点仍可通过相应圈的另一方向连通剩余局部顶点,其他边均在圈中。故 。
【习题5.23】求两侧各含一个 的原图的 。
解:按重绘标号,两侧顶点集为 与 ,中央为6;额外边为 。最小度4。删去 可分开左右两侧,所以 ;删去任意一个顶点,两个完全图内部仍连通,中央两侧各有两个邻点,上跨边又提供另一连接,所以无割点,。
左侧与其余部分之间恰有3条边 ,故 。任删两条边,各侧 仍连通(任何非平凡分割至少切断4条边);中央至左右各有两条边,外加上跨边,在把每侧收缩成一点后得到“两条左中、两条中右、一条左右”的三顶点多重图,其任一割至少含3条边。因此 ,最终 。
【习题5.24】证明简单图同构当且仅当它们的补图同构。
证明:同构双射既保持相邻,也保持不相邻;后者恰是补图的相邻。因此同一个顶点双射也是补图同构。反向对补图再取补,使用 即得。
【习题5.25】画出5阶3边的全部非同构无向简单图。
解:共4类: 加孤立点、 加两个孤立点、 加孤立点、。若含圈,3条边只可能形成三角形;否则为森林,按非平凡分支的边数分配 或 分类( 需6个顶点,排除),得到其余三类。
【习题5.26】画出5阶7边的全部非同构无向简单图。
解:对5.25四个图分别取补,共4类,且彼此不同构。每幅有 条边。取补是同构类上的双射,因此不会遗漏其他类型。
【习题5.27】6阶2正则图有几类非同构情况?
解:若沿用本章一般无向图允许自环、重边的约定,与5.13相同为11类,所有图已在5.13逐一画出;如果题意另限定为简单图,则为 与 两类。不能不说明图的类别就给出唯一数字。
【习题5.28】 阶3正则简单图满足 ,有几类非同构图?
解:握手定理 ,得 。补图为6阶2正则简单图,只有 或 两类,因此原图也恰有两类:三棱柱图与 。前者有三角形,后者没有,故不同构。
【习题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】对原题有向图求非同构圈、简单回路、指定两点短程线与距离、连通类型,并对基图回答相应问题。
解:边为 。注意 的方向,且 无出边。这里按回路所用边及其关联关系分类同构,而不是把改变起点、走向或顶点名称另算一类。
(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】对图求 到 各长度通路数、 的回路数、全图计数及可达矩阵。
解:按 排列,邻接矩阵为 。矩阵乘法用普通整数运算,平行边各算一种选择。
(1)长度1、2、3、4的 通路数为 。(2)相应 回路数为 ,都只能在 的环上重复走。
(3)长度4全部通路数为16,其中回路3条。(4)长度1—4全部通路数为 ,回路为 。(5)含零步可达的矩阵为 。若“长度不超过4”也纳入零步,则通路总数为50、回路12;本题统计采用正文的正长度约定。
【习题5.45】对中心含顶点 的有向图求指定通路、回路计数及可达矩阵。
解:按 排列,。(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表示 上的环;第二、三列表示两条 间平行边;第四列为 ;第五列为 。因此下图在同构意义下唯一。
【习题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的倍数,状态空间有限,可以逐一检查,而不依赖猜测方案。
