习题9

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【习题9:约定】沿用 支配数、 点独立数、 点覆盖数、 匹配数、 边覆盖数; 分别为点、面、边色数。极大、极小按包含关系,最大、最小按基数。交叉处无圆点就不增加顶点;颜色图中点内数字表示颜色编号,外侧标号表示原顶点身份。

【9.1】求题图两个极小支配集、一个最小支配集与支配数。

v1v2v3v4v5v6
题9.1图:左侧四边形与右侧三角形只共用v3

可取 、,两者都极小。 支配全部六点,但删 后 无人支配,删 后 无人支配。对 ,分别删除 时,依次有 失去支配。图中没有邻接其他全部五点的单点,所以 , 最小,而 极小但不最小。

【9.2】求上一图两个极大独立集、一个最大独立集与点独立数。

取 与 ,均独立且无法再加点。 最大,。证明上界可将六点分成三对相邻点 ,独立集每对至多选一点,故至多3点。 虽只含2点,仍是极大集,不能混称最大集。

【9.3】求两个极小点覆盖、一个最小点覆盖及点覆盖数。

对上一题两独立集分别取补集,得 、。二者均极小, 最小,。极大独立集对应极小覆盖,最大独立集才对应最小覆盖。

【9.4】求题图两个极小边覆盖、一个最小边覆盖和边覆盖数。

abcdef
题9.4图:a至f为边名,不是顶点名;图是K2,3

可取 、,均覆盖五个顶点。每个集合中各边至少负责一个仅由它覆盖的端点,所以均极小;五点至少需 边,两集都只有3边,故都最小,。

【9.5】求上一图两个极大匹配、一个最大匹配和匹配数。

取 与 。各自两边互不共端点,五点不可能有三条匹配边,所以它们都是最大、也都是极大匹配,。另由 复核 。

【9.6】上一图是否有完美匹配?

没有。图有奇数个顶点5,而每条匹配边恰饱和两个不同顶点,完美匹配必须使顶点数为偶数。它虽然是二部图,却不因此自动有完美匹配。

【9.7】求彼得松图最大独立集、最小点覆盖及相应参数。

abcdefghij
彼得松图的统一标号:外圈a至e,内层f至j

可取最大独立集 ,对应最小点覆盖 ,所以 。验证最大性:任取一点 加入独立集后,它的三个邻点不能再选;其余六点诱导一个六圈,而六圈最多选3个独立点,所以全图最多选4点。图的对称性使所取点不影响这个论证;也可按外五圈与内五圈各自至多选2点,直接得到总数至多4。

【9.8】找出彼得松图中既是最小边覆盖又是最大匹配的边集。

五条辐条 两两不共端点并覆盖全部十点,是完美匹配。故 ,边覆盖至少需5边而该集达到,。同一集合同时满足两个最优目标,并非仅说两种最优值相等。

【9.9】找出图示 中含 的全部完美匹配。

e1e2e3e4e5e6e7e8e9e10
题9.9图:e1至e5为外围边,e6至e10为辐条
e1e2e3e4e5e6e7e8e9e10
第一种:实线{e1,e3,e9}
e1e2e3e4e5e6e7e8e9e10
第二种:实线{e1,e4,e7}

恰有上述两种。选中 后,它的两个端点已饱和;剩余四点必须由两条不相邻边覆盖。中心若连右上外围点,只能配 ,剩余两点用 ;中心若连左下点,只能配 ,其余用 。中心连右下点 时,剩余两外围点不相邻,不能完成,所以没有第三种。

【9.10】给出四种“极值概念不可混用”的反例。

abcd
路径a-b-c-d

(1)在这条路径中 是极小支配集,但 为边,不是独立集。(2)在星图中,全体叶点是极小支配集,中心单点才最小。(3)同一星图的中心单点是极大独立集,全体叶点才最大。(4)在路径中 极大,但 更大,故前者不是最大匹配。第(4)说明不能只尝试“再添一条边”来判断最大匹配。

【9.11】举例说明Hall条件成立不推出t条件。

取正文图9.3.1(a):左侧邻集分别为 。匹配 完备,所以满足Hall条件;左部最小度2、右部最大度3,要求的正整数 必须同时 与 ,不可能。

【9.12】证明 中 且 。

完全图 、、、。 时, 且 ,两不等式成立。 时两处均可取等,因此前提不能省。

【9.13】完全二部图 中证明 。

设 。匹配可饱和较小一部,故 。选该部全部 点可覆盖所有边;一个 边匹配要求至少 个覆盖点,故 。最大独立集为较大一部的 点,因此 ,再由边覆盖恒等式 。若某一部为空,会出现孤立点,不能仍沿用边覆盖数的结论。

【9.14】任意非空顶点集简单图满足 。

取最小点覆盖 。若 ,不等式显然;否则取 ,其每条关联边的另一个端点必须在 中,所以 。因此 。即使存在孤立点也成立,此时 。

【9.15】移去八乘八棋盘一条主对角线两端方格后,不能用一乘二骨牌铺满。

题9.15:两个被移去的角格同色,用叉号表示

按棋盘黑白相间着色,每块骨牌恰覆盖一黑一白。主对角线两端同色,原有黑白各32格,移去后为30格与32格。两色格数不等,不可能由骨牌不重叠地铺满;只计算总格数62为偶数并不足以保证可铺。

【9.16】正整数 的k正则二部图有完美匹配。

由两部度数和相等,,因 得两部大小相等。又满足t条件,取 ,存在从左到右完备匹配;两部等大,故完美。 时图可全是孤立点,不能如此推断。

【9.17】n位教师与n门课,教师至少能教两门,每门课至多两位教师能教,是否可一人一课?

可以。以教师、课程为两部,以具备授课资格为边,左度至少2、右度至多2,取 即有完备匹配;两部同为 点,所以是完美匹配。这里保证的是存在合法分配,实际安排可用增广路径方法求得。

【9.18】五名学生报名三个小组,能否选三名不同组长?

第一种报名为:张参加物理、化学;王只物理;李、赵参加化学、生物;陈只生物。可以选王任物理组长、张任化学组长、陈任生物组长,三人不同且都已报名。第二种中只有张报名物理、化学,其余四人只报名生物,不能选全:取物理、化学这两个组,其候选人并集仅有张一人,违反Hall条件。不能让张同时担任两组来充当一对一匹配。

【9.19】四名教师教数学、物理、电工学、计算机基础,有几种合法一人一课安排?

ZWLQMPEC
题9.19:Z、W、L、Q为张、王、李、赵;M、P、E、C为四门课,实线为唯一方案

只有一种:张教计算机基础、王教物理、李教数学、赵教电工学。赵只有电工学可教,先固定;王原能教物理和电工学,故只能选物理;李原能教数学、物理、电工学,继而只能选数学;张遂选计算机基础。每一步都是被迫选择,既证明方案合法,也证明唯一性。

【9.20】给七种指定图用最少颜色点着色。

11111
五阶零图N5:1色
12123
五圈C5:3色
121212
六圈C6:2色
123456
完全图K6:6色
232341
六阶轮图W6:4色
2323231
七阶轮图W7:3色
1112222
完全二部图K3,4:2色

结果依次为 。零图无边可同色;偶圈交替两色而奇圈需第三色;完全图任意两点相邻;轮图在其外圈最少颜色外另需中心新色;非空完全二部图分别给两部两色即可。

【9.21】求题图三图的点色数。

3131232
题9.21(a):七个实际顶点,三色方案

(a)色数3。四个外围点从左上顺时针记为 ,三个内部点沿左上至右下依次为 。可取颜色类 ;每类内部均无边。图有三角形 ,至少需3色,所以最优。

321112345
题9.21(b):九个实际顶点,五色方案;无圆点交叉不增加顶点

(b)色数5。上方中点、左右中点及下方两个非角点,这五点之间的十条边完整存在,构成 ,至少需5色。四个外角点各只邻接其中两点,均可从五种颜色中选未被邻点占用的一种,所以上界也是5。此图不是平面图,不能因为边画在矩形里就套四色定理。

21212222
题9.21(c):K2,6的另一种画法,两色方案

(c)色数2。左下、右上两点为一部,另六点为另一部;每条边都跨两部。图有边不可能只用1色,故两色最优。中间几个圆点分别位于不同的两边通路上,不能因视觉靠近就合成一个点。

【9.22】非平凡无向树的点色数为2。

任选根,按与根的距离奇偶分两类。树的每条边连接相邻层,不会连接同一奇偶类,否则与根路径合成圈,违背树无圈。故可两色;非平凡树有边,至少需两色,得到等号。

【9.23】n阶k正则简单图满足 。

任取一个非空独立颜色类 与 。 的 个不同邻点全部在 外,故 。若用 色,把全部 点分成不超过 个独立类,则 。因简单图有 ,分母为正,故 ;由于色数为整数,也可写成 。

【9.24】任意无自环平面图均6可着色。

先删去多余平行边,点着色约束不变,得到简单平面图。它的非空子图仍有一个度不超过5的点。按阶数归纳,删该点后先用6色着色,再加回时至多5种邻点颜色受禁,至少剩1色可用,故可完成。这是直接构造,不是只援引更强的四色定理;含自环的图不适用。

【9.25】给三幅地图用最少颜色面着色。

R0R1R2R3
题9.25(a):外部面R0、方形面R1、三角面R2、环面R3,三色方案
R0T0T1T2T3T4
题9.25(b):六阶轮图地图,四色方案
R0T0T1T2T3T4T5
题9.25(c):七阶轮图地图,三色方案

(a)外部面、方形面、三角面两两共享边,至少需3色;环内面只邻接外部面,可复用方形面的颜色,故恰3色。(b)五个内部三角面依次成奇圈,需要3色,外部面邻接它们全部,另需第4色。(c)六个内部三角面交替两色,外部面取第三色即可。外部面均已计入着色,不把只在一点接触视为相邻。

【9.26】通过上述地图的对偶点色数复核面色数。

1R02R13R22R3
题9.26(a)对偶:三角形骨架加一个叶点,含原边对应的平行边
2T03T12T23T34T41R0
题9.26(b)对偶:W6的四色点着色
2T03T12T23T32T43T51R0
题9.26(c)对偶:W7的三色点着色

(a)对偶的 构成三角形, 为只邻接 的叶点;平行边不增加点着色约束,。(b)、(c)由轮图自对偶,色数分别4和3。故面色数再次为 。原图的环对应对偶桥,不能错画成对偶自环。

【9.27】求 与 地图面色数,。

轮图自对偶,所以面色数等于同阶轮图的点色数。 的外围奇圈需3色,加中心需4色; 的外围偶圈需2色,加中心需3色。因此 ,。这里下标为总点数。

【9.28】画题图的对偶,求面色数。

R0LRTQBP
题9.28原图及两色面着色:中央圆点是实际顶点
1R02L2R2T1Q2B1P
题9.28的对偶关系图:位置重新排列,平行边保留,点可分两色

原图有7点12边7面。把外部面记为 ,左右端三角面记 ,中间四个三角面按上、右、下、左记 。对偶边为两条 、两条 ,另有 ,共12条。它的二部划分为 与 ,且有边,故点色数2,原图面色数也为2。左、右两个端面都通过两条不同外边邻接外部面,不能把两条对偶边漏成一条。

【9.29】给 的边用最少颜色着色。

123
K4等于W4,三色边着色
12345
K5的五色边着色,图例给出五种颜色

最大度3,图示3色达到下界,。 有10边,每种颜色最多是两条互不相邻的边,至少5色;图示5色达到,。构造也可用正文的模5规则 。

【9.30】给 边着色。

123
K3,3的三色边着色

左右各编号 ,给跨部边 颜色 。每个顶点关联三边颜色均不同,故3色可行;最大度3给下界,。图中无圆点交叉不是公共端点,不要求交叉边异色。

【9.31】证明彼得松图边色数为4。

1234
彼得松图的四色边着色

图为3正则,Vizing定理给 。若能用3色,每点的三条边颜色全异,每个颜色类都是完美匹配;删去一种颜色后,余下的圈都应在另两色间交替,所以必须全为偶圈。

但彼得松图的任意完美匹配的补图都是两个五圈。证明如下:设匹配中辐条数为 ,外五点余下 点要在外圈内两两匹配,故 为奇数,只可能1、3、5。若 ,剩余同编号的两个外点必须在外圈相邻,其编号相差1;对应两个内点却须在内星相邻,要求编号相差2,矛盾。

若 ,删去全部辐条后直接得到内外两个五圈。若 ,五种情形由旋转互相对应,只看辐条 :其余匹配边被迫为 ;补图恰有两个五圈 与 。因此无论哪种完美匹配,补图都含奇圈,不能由两色交替,排除3色。结合上界得 ,图中也给出具体4色方案。

【9.32】五门选修课考试至少分几个时间段?

1122233415
题9.32:同有学生选修的课程之间连冲突边,三色方案

冲突边为12、13、14、24、25、34、35。课程1、2、4构成三角形,至少3个时间段。安排第一段课程1和5,第二段课程2和3,第三段课程4,每段内部均无冲突,故最少3段。并非每段只能安排一门课。

【9.33】按给定教师授课表,最少课时与教室如何安排?

完整授课矩阵按1至5班的顺序为:A行 ,B行 ,C行 ,D行 。总计12节,其中D给5班的两节是两条不同的授课边,不能合并丢掉一节。

ABCD123451234
题9.33:教师与班级构成二部多重图,四种边颜色代表四节课

教师C须上4节,故至少排4节;二部图最大度为4,也保证4节可排。具体安排:第1节A给1班、B给4班、C给3班;第2节B给3班、C给4班、D给5班;第3节A给3班、C给5班、D给4班;第4节B给1班、C给2班、D给5班。每节没有教师或班级重复,全部12次授课都覆盖。

在最少4节的前提下,至少需要 间教室,这个方案每节恰3个班上课,正好达到。若不限制总节数,可用更少教室而延长时间,不能脱离“最少4节的安排”谈教室下界。

【9.34】六台设备距离小于200km不得共频,至少需几种频率?

保留原始距离:设备1到2至6依次为120、250、345、160、180km;设备2到3至6为125、240、150、210km;设备3到4至6为160、320、380km;设备4到5、6为288、321km;设备5到6为100km。矩阵对称,对角为0。

112213243526
题9.34:仅对不同设备距离小于200km连边,三色方案

冲突边为12、15、16、23、25、34、56。设备1、5、6两两冲突,至少3频;分组 各用一种频率,每组内部均无冲突,故最少3种。门限是严格小于200km,不是把所有已给距离都当成边。

【9.35】六场论文答辩最少安排多少个不同时间?

委员会分别为 、、、、、。两场共享任一教授就不能同时进行。

112233545546
题9.35:冲突图是K6删去A4A5一边,五色方案

只有 的委员会不相交,可以同一时段;其余每对均有共同成员。 构成五点完全子图,至少5个时间段。把 合在一段,其余四场各占一段,即5段可行,所以最少5段。题目没有指定每段时长,不虚构具体钟点。