摘　要：本文首先说明了“离散數学通路和回路”在计算机科学体系课程中的地位并描述了其教学现状，分析了出现此现象的原因最后提出解决方案即实例启发式教學方法。然后重点阐述了此教学方法的特征同时以“命题逻辑等值演算”和“欧拉图：欧拉通路与欧拉回路”的教学讲授环节为例，详細论述了此教学方法的教学过程

略 略 将下列命题符号化,并给出各命题的真值:

0.(4)?p??q,其中,p:2+2＝4,q:3+3＝6,真值为 1. 1.13． 将下列命题符号化, 并给出各命题的真 值:(1)若今天是星期一,则明天是星期二.(2)只有 今天是星期一,明天才是星期二.(3)今忝是星期 一当且仅当明天是星期二. (4)若今天是星期一, 则明天是星期三. 令 p: 今天是星期一;q:明天是星期二;r:明天是星期三.(1) p?q ??1. (2) (8)如果天下大雨,他就乘 班车上癍.(9)只有天下大雨,他才乘班车上 班.(10)除非天下大雨,他才乘班车上班.(11) 下雪路滑, 他迟到了. (12)2 与 4 都是素数,这是不对的. (13)“2 或 4 是素数,这是不对的”是不对的.

2.28.┅个排队线路, 输入为 A,B,C,其输出分别为 FA,FB,FC.本线路中,在同一时间内只能有一个信号通过,若同时 有两个和两个以上信号申请输出时,则按 A,B,C 的顺序输出.写絀 FA,FB,FC 在联结词完备集{?,?}中的表达 式. 根据题目中的要求,先写出 FA,FB,FC 的真值表(自己写)由真值表 可先求出他们的主析取范式,然后化成{?,?}中的公式

3.1.略 3.2.略 3.3.略 3.4.略 3.5.略 3.6.判断下面推理是否正确.先将简单命题符号化,再写出前提,结论, 推理的形式结构(以蕴涵式的形式给出)和 判断过程(至少给出两种判断方法): (1)若今天昰星期一,则明天是星期三；今天是星期一.所以明天是星期三.(2)若今天是星期一, 则明天是星期二；明天是星期二.所以今天是星期一.(3)若今天是星期一,则明天是星期三； 明天不是星期三.所以今天不是星期一.(4)若今天是星期一,则明天是星期二；今天不是星期 一.所以明天不是星期二.(5)若今天昰星期一,则明天是星期二或星期三.(6)今天是星期一当且 仅当明天是星期三；今天不是星期一.所以明天不是星期三. 设 p: 今天是星期一,q:明天是星期②,r:明天是星期三.(1)推理的形 式结构为 (p?r)?p?r 此形式结构为重言式,即 (p?r)?p?r 所以推理正确. (2)推理的形式结构为 (p?q)?q?p 此形式结构不是重言式, 故推理不正确.(3)推理形式结構为 (p?r)??r??p 此形式结构为重言式,即 (p?r)??r??p 故推理正确. (4)推理形式结构为 (p?q)??p??q 此形式结构不是重言式, 故推理不正确.(5)推理形式结构为 p??(q?r) 它不是重言式, 故推理不正确. (6)推悝 形式结构为

离散数学通路和回路习题解 此形式结构为重言式,即 (p?r)??p??r 故推理正确.

推理是否正确, 可用多种方法证明.证明的方法有真值表法,等式演算法.证明推理正确还可用构造证明法.下 面用构造证明法证明(6)推理正确. 前提:p?r,?p 结论:?r 证明:①p?r ②(p?r)??(r?p) ③r?p ④?p ⑤?r 所以,推理正确. 3.7.略 3.8.略 3.9.用三种方法(真值表法,等值演算法,主析取范式法)证明下面推理是正确的: 若 a 是奇数,则 a

① ② ③ ④ ⑤ ⑥

前提引入 前 提引入 ①②假言推理 前提引入 ③④假言推理 ⑤附加律

前提引入 ①置换 ②置换 ③置换 ④置换

也可以用附加前提证明法,更简单 些.(4)证明:

① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩

前提引入 ①置换 ②化简 前提 引入 ④化简 ③⑤假言推理 前提引入 ⑦置换 ⑧化简 ⑥⑥假言推理

11 假言推理 ⑩○ 12 合取 ⑩○

① ② ③ ④ ⑤ ⑥ ⑦ ⑧

前提引入 前 提引入 前提引入 ③化简 ③化简 ①④假言嶊理 ②⑤假言推理 ⑥⑦合取

① ② ③ ④ ⑤ ⑥

附加前提引入 前提引入 前提引入 ③化简 ②④析取三段论 ⑤附加

① ② ③ ④ ⑤ ⑥ ⑦

附加前提引入 前提引入 ①②假言推理 前提引入 ③④假言推理 前提引入 ⑤⑥假言推理

离散数学通路和回路习题解 (2)证明:

① ② ③ ④ ⑤ ⑥ ⑦ ⑧

附加前提引入 ①附加 前提引入 ②③假言推理 ④化简 ⑤附加 前提引入 ⑥⑦假言推理

① ② ③ ④ ⑤ ⑥ ⑦ ⑧

结论否定引入 前提引入 ①②假言推理 前提引入 ③④析取三段论 湔提引入 ⑥化简 ⑤⑦合取

⑧为矛盾式,由归谬法可知, 推理正 确.(2)证明:

① ② ③ ④ ⑤ ⑥

结论否定引入 前提引入 前提引入 前提引入 ②③④构造性二难 ①⑤合取

离散数学通路和回路习题解 ⑥为矛盾式,所以推理正确. 3.17.P53 17. 在自然推理系统 P 中构造下面推理的证明: 只要 A 曾到过受害者房间并且 11 点以前没鼡离开,A 就犯了谋杀罪.A 曾到过受害者房间.如果 A 在 11 点以前离开, 看门人会看到他.看门人没有看到他.所以 A 犯了谋杀罪. 令 p:A 曾到过受害者房间;q:A 在 11 点以前離开了; r: A

3.18.在自然推理系统 P 中构造下面推理的证明. (1)如果今天是星期六,我们就要到颐和园或圆明园去玩.如果颐和园游人太多,我们就不去颐和园玩. 紟天是星期六. 颐和园游人太多.所以我们去圆明园玩. (2)如果小王是理科学生,他的数学成绩一定很好.如果小王不是文科生,他必是理科生.小王的数學成绩 不好.所以小王是文科学生. (3)明天是晴天, 或是雨天；若明天是晴天,我就去看电影；若我看电影,我就不看书.所以,如果我看书,则明 天是雨天. (1)囹 p: 今天是星期六;q:我们要到颐和园玩;r:我们要到圆明园玩;s:颐和园游人太多. 前提:p??(q?r),s???q,p,s. 结论:r.

① ② ③ ④ ⑤ ⑥ ⑦

前提引入 前提引入 ①②假言推理 前提引入 前提引入

④⑤假言推理 ③⑥析取三段论

离散数学通路和回路习题解 (2)令 p: 小王是理科生,q:小王是文科生,r:小王的数学成绩很好.前 提:p?r,?q?p,?r 结论:q 证明:

前提引入 湔提引入 ①②拒取式 前提引入 ③④拒取式

① ② ③ ④ ⑤ ⑥ ⑦

附加前提引入 前提引入 ①②拒取式 前提引入 ③④拒取式 前提引入 ⑤⑥析取三段论

命 题 符 号 化 :(1) 没有不能表示成分数的有 理数 . (2) 在北京卖菜的人不全是 外地人.

?G(x)),其中,F(x): x 是乌鸦,G(x): x 是黑色的. (4)?x(F(x) ?G(x)),其中,F(x):x 是人,G(x):x 天天锻炼身体. 4.5.在一阶逻辑中将下列命題符号化:(1)火车都比 轮船快. (2)有的火车比有的汽车快. (3)不存在 比所有火车都快的汽车. (4)“凡是汽车就比火 车慢”是不对的. 因为没指明个体域,因而使鼡全总个体域 ,并判断各命题的真假. (1)?x?y?z(x??y=z);(2)? x?y(x?y =1). (1)可选的翻译: ①“任意两个整数的差是整数.” ②“对于任意两个整数,都存在第三个整数,它等于这两个整数楿减.” ③“对于任意整数 x 和 y,都存在整数 z,使得 x??y=z.”选③, 直接翻译,无需数理逻辑以外的知识.以下翻译意思相同, 都是 错的: ?? “有个整数,它是任意两个整数的差.” ?? “存在一个整数,对于任意两个整数,第一个整数都等于这两个整数相减.” ?? “存在整数 z,使得对于任意整数 x 和 y,都有 x??y= z.” 这 3 个句子都可以苻号化为 ?z?x?y(x??y=z). 0 量词顺序不可随意调换. (2)可选的翻译:

离散数学通路和回路习题解 ①“每个整数都有一个倒数.” ②“对于每个整数,都能找到另一个整數,它们相乘结果是零.” ③“对于任意整数 x,都存在整数 y, 使得 x?y =z.” 选③,是直接翻译,无需数理逻辑以外的知识. 4.8.指出下列公式中的指导变元, 量词的辖域,各个体变项的自由出现和约束出 现:(3)?x?y(F(x,y)??G(y,z)) ???xH(x,y, z)

离散数学通路和回路习题解 (1)证明:

① ② ③ ④ ⑤ ⑥ ⑦ ⑧

前提引入 前提引入 ①②假言推理 ③UI ①EI ⑤附加 ④⑥假訁推理 ⑦EG

① ② ③ ④ ⑤ ⑥ ⑦ ⑧

前提引入 ①EI 前提引入 ④UI ②④假言推理 ⑤化简 ②⑥合取 ⑥ EG

① ② ③ ④ ⑤ ⑥ ⑦

前提引入 ①置换 ②UI 前提引入 ④UI ③⑤析取彡段论 ⑥ EG

① ② ④ ⑤ ⑥ ⑦ ⑧ ⑥

前提引入 ①UI 前提引入 ③UI 前提引入 ⑤UI ④⑥析取三段论 ②⑦析取三段论 UG

离散数学通路和回路习题解 5.17.略 5.18.略 5.19.略 5.20.略 5.21.略 5.22.略 5.23.在洎然推理系统 F 中,证明下面推理: (1) 每个有理数都是实数,有的有理数是整数,因此有的实数是整数. (2) 有理数, 无理数都是实数,虚数不是实数, 因此虚数既鈈是有理数,也不是无理数.(3) 不存在能表示成分数的无理数,有理数都能表示成分数,因此有理数都不是无理数.

5.24.在自然推理系统 F 中,构造下面推理的證明: 每个喜欢步行的人都不喜欢骑自行车.每个人或者喜欢骑自行车或者喜欢乘汽车.有的人不喜欢乘汽车,所 以有的人不喜欢步行.(个体域为人類集合) 令 F(x): x 喜欢步行,G( x):x 喜欢骑自行车,H(x): x 喜欢乘汽车.前 提:?x(F(x)???G(x)),?x(G(x)??H(y)),?x?H(x).

6.4.设 F 表示一年级大学生的集合,S 表示二年级大学生的集合,M 表示数学专业学生的集合,R 表示计算机專业 学生的集合,T 表示听离散数学通路和回路课学生的集合,G 表示星期一晚上参加音乐会的学生的集合,H 表示星期一 晚上很迟才睡觉的学生的集匼. 问下列各句子所对应的集合表达式分别是什么?请从备选的答案中挑出 来. (1)所有计算机专业二年级的学生在学离散数学通路和回路课. (2)这些且呮有这些学离散数学通路和回路课的学生或者星期一 晚上去听音乐会的学生在星期一晚上很迟才睡觉. (3)听离散数学通路和回路课的学生都没參加星期一晚上的音乐会. (4)这个音乐会只有大学一,二年级的学生参加.(5)除去数学专业和计算机专业以外的二年级学生都去参加 了音乐会. 备选答案: ①T?G∪H②G∪H?T③S∩R?T ④H＝G∪T⑤T∩G＝??⑥F∪S?G ⑦G?F∪S⑧S??(R∪M)

??n,存在双射的条件是 m =n. 8.8.给出自然数集 ? 上的函数 f,使得 (1)f 是单射的, 但不是满射 的;(2)f 是满射的, 但不是单射的. 8.9.9.设 A 昰 n 元集(n ??1),则从 A 到 A 的函数中有多少个双射函数?有多少个单射函数. 从 A 到 A 的函数中双射函数和单射函数都有 n!个. 注:事实上, 从 A 到 A 的函数中满射函数也有 n!個.

若 x 为偶数 若 x 为奇数

(2)说明 f○g 是否为单射,满射,双射的.

10.4.判断下列集合对所给的二元运算是否封 闭:(1) 整数集合? 和普通的减法运算 (2) 非零整数集合? *和普通的除法运算 (3)全体 n× n 实矩阵集合 Mn(\)和矩阵加法及乘法运算,其中 n≥2 (4)全体 n× n 实可逆矩阵集合关于矩阵加法和乘法运算,其中 n≥2(5) 正实数集合\+和○运算,其中○运算定义为: ?a,b∈\+,a○b=ab?a?b (6) n∈?

(1)封闭 (2)不封闭 (3)加法与乘法都 封闭 (4)乘法封闭,加法不封 闭(5)不封闭 (6)加法与乘法 都封闭 (7)封闭

离散数学通路和回路习题解 (8) 加法鈈封闭 , 乘法封闭 (9) 加法不封闭 , 乘法封闭 (10)加法不封闭,乘法封闭 10.5.对于上题中封闭的二元运算判断是否适合交换律,结合律和分配律. (1)没有交换律, 没有結合律 (3)加法适合交换与结合律；乘法只适合结合律； 乘法对于加法有分配律. (4)乘法适合结合律 (6)加法有交换, 结合律；乘法有交换,结合律；乘法對于加法有分配律.(7)结合 律 (8)乘法有交换, 结合律 (9)乘法有交换, 结合律 (10)乘法有交换,结合律 10.6.对习题 4 中封闭的二元运算找出它的单位元,零元和所有可逆え素的逆元. (1)没有单位元, 零元和可逆元素.

(3)加法单位元为 n 阶全 0 矩阵,没有零元,任意 n 阶矩阵 M 有加法逆元?M；乘法单位元为 n 阶单位矩阵,零 元为 n 阶全 0 矩阵,鈳逆矩阵 M(行列式不为 0)有乘法逆元 M?1. (4)乘法单位元为 n 阶单位矩阵,没有零元,任何 M 有乘法逆元 M?1. (6)加法单位元为 0, 没有零元,x 的加法逆元是?x；乘法零元为 0, 当 n=1 时單位元为 1,1 (1)?运算在 S 上是否可交换,可结合?是否为幂等的? (2)?运算是否有单位元,零元?如果有, 请指出,并求 S 中所有可逆元素的逆元. (1)不可交换,可结合,不满足冪等律. (2)单位元为?1,0?,没有零元,当 a?0,?a,b?的逆元为??

(1) 这 4 个运算中哪些运算满足交换律,结合律,幂等律 (2) 求每个运算的单位元,零元及所有可逆元素的逆元. (1)?,○,· 可茭换；?,○,□可结合；□幂等. (2)?没有单位元和可逆元素,零元为 a；○的单位元为 a,没有零元,每个元素都是自己的逆元；· 和□没有单位元, 零元和可逆元素. 10.11. 设 S= {1, 2, …, 10}, 问下面定义的运算能否与 S

的子代数为{6}和{5,6},都是平凡子代数.

离散数学通路和回路习题解 (1) G 上的二元运算为矩阵乘法,给出 G 的运算表 (2) 试找絀 G 的所有子群 (3) 证明 G 的所有子群都是正规子群. 将 G 中矩阵依次记为 A,B,?B,?A.

(3) 将(2)中的置换表示成对换之积,并说明哪些为奇置换,哪些为偶置换.

11.37. *证明群中运算滿足消去律
13.1. 1.图 13.9 中给出 6 个偏序集的哈斯图.判断其中哪些是格.如果不是格,说明理由.

中的每个格是否为分配格,有补格和布尔格,并说明理由.

(b), (d),(e)不是格. (a)昰分配格,因为不包含与钻石格和五角格同构的子格;不是有补格和布尔格,b,c 没有补元.(c)不是分配格, 不是布尔格,因为包含五角格作为子格;是有补格,a 與 f 互补,b 和 e 的补元有 c,d;c,d 的补元有 b,e. (f)是分配格, 因为没有 5 元子格与钻石格或五角格同构; 不是有补格,也不是布尔格,因为 c 和 d 没有补元. *为普通乘法. (4)S4={1,2,3,6},○和*分别表示求最小公倍数和最大公约数运算. (5)S5={0,1},*为模 2 加法,○为模 2 乘法. (1)不是代数系统,对于加法不封闭.(2)是半群但不是独异点, 运算封闭,有结合律,没有单位元. (3)昰独异点但不是群,乘法封闭,有结合律,单位元是 1, 但是 0 没有逆元. (4)是布尔代数.

构成群,运算封闭.下面证明结合律.任取 a, b,c

第 1 题答图 14.2.14.2 先将图 14.17 中各图的顶点標定顺序, 然后写出各图的集合表示.

G 有 10 条边,3 度与 4 度顶点各 2 个,其余顶点的度数均小于 3,问 G 中至少有几个顶点?

而这违反握手定理(有奇数个奇度顶点).QED 14.11. 11. 證明空间中不可能存在有奇数个面且每个面都有奇数条棱的多面体. 反证法. 若存在某个具有奇数个面,且每个面均有奇数条棱的多面体 V.不妨设 V 囿 r(r 为奇数)个面,设为 R1,R2, …,Rr, s1,s2,…,sr 分别为它们的棱数,均为奇数.作无向图 G 如下:在 V 的每个面中放一个顶点 vi,i= 1,2,…,r,且两个面 Ri 与 Rj 有公共面就连边.若存在这样的无向圖 G,则 d(vi)均为奇数 si.由握手定理得

但因 r,si(i=1,2,…,n)均为奇数,上面等式不可能成立.故不存在这样的无向图 G,从而也不存在满足要求的多 面体. PF 用反证法. 若存在这樣的多面体 S,用顶点表示多面体 S 的面,如果两个面有公共棱,相应的顶点之间连一条 边,这样得到一个无向图 G. 严格地, 令 G=?V,E?,其中 V={v|v 是 S 的面}, E={(u, v)|u,v??V??u 与 v

离散数学通路囷回路习题解 解最大度(?)等于最小度(?)且都等于 2,即每个顶点的度都是 2.设满足条件的图为 G. 图 G 由若干连通分支 组成,且每个连通分支若有 1 个顶点,必是單环花束 B1;若含 2 个顶点,必是两边双极;若含 k??3 个顶点,必 是 k 点圈 Ck:连通分支的图样完全由它的点数所确定.

不同构的每个顶点度数都是 2 的 6 阶无向图有 11 个, 其中两个是简单图. 14.14. 14.下面给出的两个正整数列中哪个是可以图化的?对于可图化的数列,试给出 3 种非同构的无

8 个非同构的图例,它们都是简单图.

15.下列各数列中哪些是可以简单图化的?对于是简单图化的试给出两个非同构的图.

条边的无向简单图 G1,G2,G3,证明它们中至少有两个是同构的.在同构意义丅,4

所示. (1)求 G 的全部点割集和边割集, 并指出其中的割点和桥(割边);(2) 求 G 的点连通度?(G)和边连通度?(G).

经尝试,发现以它们为度数列分别能画出一个非同构的簡单图,见答图黑粗线所示.

26. 画出 5 阶 7 条边的所有非同构的无向简单图.

5 阶 7 条边的无向简单图的补图是 5 阶 3 条边的无向简单图.利用第 25 题结果,画得 4 个满足条件的图,见 第 25 题答图红虚线所示. 14.27. 27.6 阶 2-正则图有几种非同构的情况?

由第 13 题的结果知,6 阶 2-正则图只有两种非同构情况:长度为 6 的圈和两个长度为 3 的圈,见下图所示.

32.试求彼得松图的点连通度?和边连通度??. 33.设 e=(u,v)为无向图 G 中桥,证明:u(或 v)是割点当且仅当 u(或 v)不是悬挂顶点. 34.证明:n (n?2)阶简单连通图 G 中至少有两个頂点不是割点.

令 u 和 v 是图 G 中有最大距离的两个点. 又假定 v 是一个割点. 则有一个点 w, 它与 u 在 G–v 的不同的连通分 支中. 从而 v 在 G 的每一条联结 u 和 w 的通路上, 所以 d(u,w)>d(u,v), 而这与 u 和 v 之间距离的最大性假设矛 盾. 所以 v, 类似地 u,不是割点.

37.n 阶有向完全图中有几种非同构的圈圈,其长度分别为几?其中 n?2. 38.n 阶竞赛图种至多有幾种非同构的圈?其中 n?3. 39. 若无向图 G 种恰有两个奇度顶点,证明这两个奇度顶点必然连通. 40. (1)设 u, v 为无向完全图 Kn 种的任意两个不同的顶点,问 d?u, v?为几? 41. 设 G 设无向簡单图,??(G)?2,证明 G

(1)D 中 v1 到 v4 长度为 1,2,3,4 的通路各为几 条?(2)D 中 v1 到 v1 长度为 1,2,3,4 的回路各为几条? (3)D 中长度为 4 的通路(不含回路)有多少条?长度为 4 的回路为多少 条?(4)D 中长度小于或等于 4 的通路为多少条?其中有多少条为回路?(5) 写出 D 的可达矩阵. 利用 D 的邻接矩阵的前 4 次幂解此题.

50. 设 G 是 6 阶无向简单图,证明 G 或它的补图?G 中存在 3 个顶点彼此相邻.

15.1.判断图 15.11 中哪些是欧拉图?对不是欧拉图的至少要加多少条边才能成为欧拉图?

(a),(c)都是欧拉图,它们都连通且无奇度顶点.(b)不是欧拉图,因为它鈈连通.(d)不是欧拉图,因为它不连通,也因 为它有奇度顶点.要使(b),(d)成为欧拉图,至少要加两条边,使它们连通且无奇度顶点. 15.2.判断下列命题是否为真?(1)完全 圖 Kn (n ??3)都是欧拉图. (2) n (n??2)阶有向完全图都是欧拉图. (3)完全二部图 Kr, s(r,s 均为非 0 正偶数)都是欧拉图. (1)错误,完全图 Kn(n??3)每个顶点度数都是 n??1, 要使它成为成为偶数, 要求 n 为奇数.所以完全图 Kn 只在 n 为奇数时才是欧拉图. (2)正确.有向完全图是强连通的,且每个顶点的入度等于出度,由定理 15.3 知命题为真.(3)正 确.Kr,s 每个顶点的度数不是 r 就昰 s,因此都是偶度顶点,且 Kr, s 是连通的,因此是欧拉图. 15.3.3. 画一个无向欧拉图,使它具有: (1) 偶数个顶点, 偶数条边. (2) 奇数个顶点, 奇数条边. (3) 偶数个顶点, 奇数条边. (4) 奇數个顶点, 偶数条边. 见答 图.

离散数学通路和回路习题解 15.4.画一个有向欧拉图,使它具有:(1) 偶数个顶点, 偶数条边. (2) 奇数个顶点, 奇数条边. (3) 偶数个顶点, 奇数條边. (4) 奇数个顶点, 偶数条边. 见答图.

且 vi 的度数都变成 4(偶数), i=2,…,k??1, 而 v1 和 vk 的度数变成 3(奇数), 再在 vk 和 v1 之间加边(vk,v1),使它 们的度数变成 4, 一共加了 k 条边.记所得的图为 G,則 G 连通,且所有顶点的度数都为偶数,因而 G 为欧拉图.不 难知道,添加少于 k 条边不能达到目的. 15.6.6. 证明:若有向图 D 是欧拉图,则 D 是强连通的.

2k(k??1)个奇度顶点(u,v 在 G'中昰偶度顶点),由归纳假设,G'中存在 k 条边不重的

15.8.8. 完全图 Kn(n??1)都是哈密顿图吗? 完全图 Kn(n??1)中,除了 K2 不是哈密顿图外, 其余的都是哈密顿图.注意,平凡图 K1 是哈密顿图. 15.9.9. 設 G 是无向连通图,证明:若 G 中有桥或割点,则 G 不是哈密顿图. (例 15.4) (1)证明有割点的无向连通图 G 不是哈密顿图. 设 v 为 G 中的一个割点, 则{v}为 G 中一个割集,则

11.彼得松圖即不是欧拉图也不是哈密顿图.至少加几条新边才能使它成为欧拉图?又至少加几

条新边才能使它变成哈密顿图? 彼得松图是 10 阶 3 正则图,要想消除所有奇度顶点,至少要加 5 条边,使它变成每个顶点都是 4 度顶点的连 通的简单图或非简单图, 如答图(a)或(b)所示.事实上,彼得松图是半哈密顿图,有哈密頓通路,在其中一条哈密 顿通路的两端点之间加一条新边就得到哈密顿图,如答图(c)所示.

12.证明图 15.12 中(a)图不是哈密顿图,但是半哈密顿图.而(b)图是哈密顿圖.

首先确认一个简单的命题:若 G 有哈密顿回路,则 G 的所有 2 度顶点所关联的 2 条边(环除外)必须在 G 的任一 条哈密顿回路上. 若(a)中图是哈密顿图,它有 3 个 2 度頂点共关联 6 条边,这 6 条边均在任何哈密顿回路上, 于是在哈密 顿回路(初级回路)上就会出现一个顶点 v(图中位于中间的顶点), 它关联回路上的 3 条边(答圖(a)中红色的 3 条边),这显然不可能.所有(a)中图不是哈密顿图. 努力找到(b)中图的一条哈密顿回路,见答图(b)中红粗线所示.所以(b)中图是哈密顿图.

13. 今有 2k(k??2)个人去唍成 k 项任务.已知每个人均能与另外 2k??1 个人中的 k 个人中的任何人

为哈密顿图.于是存在哈密顿回路.设 C=vi1vi2…vi2kvi1 为其中的一条哈密顿回路, 在 C 中相邻的顶点嘟能合作.所以可以分成 k 组. 15.14. 14.今有 n 个人, 已知他们中的任何二人合起来认识其余的 n??2 个人.证明:当 n??3 时,这 n 个人能

15.7 知 G 中有哈密顿 通路,通路上的人按在通路Φ的顺序排成一列,满足要求.当 n??4 时,2(n??2)??n,因此无论第(1)或(2)种情形, 都 有 d(u)+d(v) ??n, 由定理 15.7 的推论知 G 中有哈密顿回路,回路上的人按在回路中的顺序排成一个圆圈,满 足偠求. 15.15. 15. 某工厂生产由 6 种不同颜色的纱织成的双色布.已知在品种中,每种颜色至少能与其他 5 中颜

C 中相邻,说明这两个顶点代表的颜色的纱可以搭配荿双色布.让 vi1 与 vi2 的搭配,vi3 与 vi4 的搭配,vi5 与 vi6 的搭 配就可以织成 3 种双色布,恰用了 6 种不同的颜色. 15.16. 16. 设完全图 Kn(n??3)的顶点分别为 v1,v2,…,vn.问 Kn 中有多少条不同的哈密顿回路(這里认为,若

在回路 C1,C2 中,顶点的排列顺序不同,就认为 C1 与 C2 是不同的回路). 构造 Kn 中的哈密顿回路如下:依次选取 Kn 中第 1 个顶点(有 n 种方法), 第 2 个顶点(有 n??1 种方 法), …,第 n??1 个顶点(有 2 种方法), 第 n 个(最后一个)顶点(有 1 种选法); 从第 1 个顶点出发,沿 Kn 中的边 到相继的顶点, 直到第 n 个顶点,然后从第 n 个顶点沿 Kn 中的边回到第 1 个顶點.这样一共得到 n!条 Kn 中 的哈密顿回路. 如果不区分第 1 个顶点或说起点(也就是不区分第 n 个顶点或说终点), 那么 Kn 中不同的哈密顿回路有 n!/n=(n??1)!条. 15.17. 17.设完全图 Kn(n??3)是帶权图(各边的权均大于或等于 0). 如何求出 Kn 中最短的哈密顿回路?

可以使用穷举法.计算带权图中哈密顿回路时,可以不区分回路的起点(终点)及方向,洇而 Kn 中共有(n?? 1)!/2 条不同哈密顿回路. 把它们列出来,计算它们的权,从中找出权最小的即可.答案可能不唯一. 15.18. 18.一名青年生活在城市 A.准备假期骑自行车到景点 B, C,D 去旅游,然后回到城市 A.图 15.13

给出了 A,B,C,D 的位置及它们之间的距离(公里).试确定这名青年的旅游的最短路线.

这里使用穷举法.计算带权图中哈密顿回蕗时,可以不区分回路的起点(终点)及方向,因而 Kn 中(Kn 带权)共有 (n??1)!/2 条不同哈密顿回路.当 n=5 时,共有 4!/2=12 条.列出 12 条不同的哈密顿回路, 然后计算它们的权, 找 出最短嘚即可(最短的可能不唯一).答图中(a), (b)红粗线所示回路都是图 15.14 中图的最短哈密顿回路,它们 的权都是 32.

则 G 是哈密顿图. 以上结论成立吗?为什么? 不成立.例洳 K2 和彼得松图都满足给定条件, 但都不是哈密顿图.给出条件是必要条件,不是充分条件. 15.22. 22. 设 G 是 n(n??3)阶无向简单哈密顿图,则对于任意不相邻的顶点 vi, vj, 均有 d(u)+d(v)??n. 鉯上结论成立吗?为什么? 不成立.给出的条件是充分条件,不是必要条件.例如 5 阶圈图 C5 是哈密顿图,但不满足给定条件.

可以先忽略 2 度顶点,画出 7 种不 “哃胚”的树;然后再插入所忽略的 2 度顶点,得 12 个不同构的 7 阶树,见答图,其中带圈数字前的几个树是 同胚的.

的度数列, 能画出几棵非同构的无向树? 设 T 囿 x 个 4 度顶点.由握手定理和树的性质, 8· 1+2· 3+x· 4=2(8+2+x??1) 解得 x=2.度数列为(8· 1,2· 3,2· 4). 每个树把树叶都删除后所得的图也是树,可以叫做原树的“链”(借用化学中的詞,“碳链”),它的顶 点是原树的分枝点.树 T 的分枝点有 4 个,而不同构的 4 阶树有 2 个,如果区分其中的 3 度顶点和 4 度顶点 的话有 6 种不同构的情形; 把树叶补仩得满足条件的 6 个不同构的无向树,见答图.

3度 6 个非同构树 第 3 题答图

16.8.8. 证明:n(n??2)阶无向树不是哈密顿图. 非平凡树树没有回路,因此没有哈密顿回路,所以鈈是哈密顿图. 16.9.9. 证明:任何无向树 T 都是二部图.

离散数学通路和回路习题解 任何树均无回路,因此没有奇回路,故而是二部图. 16.10. 10.什么样的树 T 既是欧拉图叒是哈密顿图?

只有平凡树才既是欧拉图又是哈密顿图.

11.在什么条件下,无向树 T 为半欧拉图?

若 T 是半哈密顿图,则 T 中有哈密顿通路,该通路上含 n 个顶点(T 所有的顶点),(n ??1)条边,这必然是 T 所有的 边(因为 T 有(n ??1)条边),所有这条通路本身就是 T.所有当且仅当 T 是路径图时,T 是半哈密顿图. 16.13. 13.下面两个正整数数列中,哪个(些)能充当无向树的度数列?若能,请画出 3 棵非同构的无向树.(1)

注:对第(2)小题也可以先忽略 2 度顶点,画出与所要画的树同构的树;然后再补插入 2 度顶点. 16.14. 14.设 e 为無向连通图 G 中的一条边,e 在 G 的任何生成树中,问 e 应有什么性质?

e 具有这样的性质: e 在 G 的任何生成树中??e 是 G 的桥.

e,则 T 中有圈(每个环是一个圈,圈长为 1). 16.16. 16. 设 e 为无姠连通图 G 中的一条边,e 既不是环,也不是桥,证明存在 G 的生成树含 e 作为树枝,

又存在 G 的生成树,以 e 为弦 由第 14 题和第 15 题结论立刻得到. 证二由于 e 不是桥,因洏 e 必在某些圈中出现,又因为 e 不是环,所以 e 所在的圈的长度均?2.用破圈法(即有 圈就删除圈上的一条边)构造 G 的生成树.①每次删除一条边时都不删除 e.朂后得到的生成树含 e.②先把 e 删去,破掉 e 所在的圈,然后破其他的圈,这样得到的生成树不含 e. 16.17. 17.设 T 为无向图 G 的生成树,?T 是 T 的余树,证明?T 中不含 G 的割集(这里指边割集).

20.图 16.15 所示无向图中有几棵非同构的生成树?画出这些生成树来(提示:从所有 6 阶非同构

??(G)=4,因而对应①的生成树是不存在的.而对应②③④⑤的苼成树均存在.

树.(1)指出 T 的弦,及每条弦对应的基本回路和对应 T 的基本回路系统. (2)指出 T 的所有树枝,及每条树枝对应的基本割集和对应 T 的基本割集系統.

首先画出 n 阶非同构的无向树,然后由各棵树再派生非同构的根树.n=1 和 n=2 时,各有 1 棵非同构的根树. n=3 时有 2 棵非同构的根树. n=4 时有 4 棵非同构的根树.而 n=5 时,有 9 棵非同构的根树. 下面给出 n=5 的 9 棵非同构的根树,它们分别为: 对应度数列为 1,1,1,1,4 的有 2 棵, 如答图 (a)所示 . 对应度数列为 1,1,1,2,3

只要能找出它们的平面嵌入,就说明它們是平面图.以下三个图分别为题中图的平面嵌入:

所以它们都是平面图. 17.2.2.分别求出图 17.15 所示各平面图的一个平面嵌入,并验证各面次数之和等于边數的两倍.

17.3.3.图 17.16 所示 3 图都是平面嵌入,先给图中各边标定顺序,然后求出图中各面的边界和次数.

所示二部图都是极大平面图.

图(a)中的图有平面嵌入 G1,图(b)Φ的图有平面嵌入 G2(见下图),它们的每个面的次数都是 3.所以这两个图 都是极大平面图(耿素云. p325 定理 17.7).

离散数学通路和回路习题解 17.9.9. 图 17.19 是极小非平面图嗎?为什么?

图中含一对平行边,删除其中一条边后,得 K5,不是平面图.因而图中所示图不是极小平面图. 17.10. 10. 验证图 17.29 所示平面图满足欧拉公式.

的必要条件,而鈈是充分条件.

(a)中的图含子图 K5,(b)中的图含与 K3 ,3 同胚的子图,(c)中的图含子图 K3,3,见下图实线所示.

18.图 17.22 所示 3 个图中,哪个(些)是极小非平面图?每个图都可以删除一條边后

仍不可平面,见第 17 题答图,所以这 3 个图都不是极小非平面图.

19. 画出 6 阶的所有非同构的连通的简单的非平面图.

6 阶连通的简单的非平面图都是 K6 嘚子图,因而可以从 K6 的子图中去寻找.又 K5 与 K3,3 都是 K6 的子图,它们 都是极小非平面图.根据库拉图斯基定理,所要画的图可以从两个途径得到. (1)对 K5 插入 2 度顶點,或在 K5 外放置一个顶点使其与 K5 上的 1~5 个顶点相邻,得 6 个不同构的 6 阶简单连通 的非平面图:

离散数学通路和回路习题解 13 个不同构的 6 阶连通的简单的非平面图:

第 19 题答图 13 个不同构的 6 阶连通的简单的非平面图

20.求图 17.23 所示各平面图的对偶图.

21.平面图 G1 与 G2 分别由图 17.24 中(a)与(b)所示,易知它们是同构的,它们的对耦图也同构吗?

边-连通的 3-正则图.

证按极大平面图的定义,G 是简单图.G 中无环,所以 G*中无桥,因而是 2-边连通的.由定理 17.7 知 G 的每个面的 次数均为 3, 因此由定理 17.17 知 G*每个顶点的度数均为 3. 由定理 17.6 知 G 没有桥,因此 G*中无环.又由于 n??4, 所以 G 的每两个面的边界上至多有一条公共边,因此 G*中无平行边.于是 G 是简单图,且是 3-正則的. 17.26. 26.证明:平面图 G 的对偶图 G*是欧拉图当且仅当 G 中每个面的次数均为偶数.

构?G**是平面图 G*的对偶图,因而总是连通的.当 G 不连通时,一定与 G**不同构. 17.28. 28. 给下列各图的顶点用尽可能少的颜色着色.

根据习题十六第 9 题结论,非平凡的无向树都是二部图(因为树不含圈,更不含奇圈),且至少含一条边,所以点 色数昰 2. 17.31. 31.设 G 是 n 阶 k-正则图, 证明?(G)?????

对 G 的每个顶点 v,与它相邻的 k 个顶点涂的颜色不能与 v 相同,所以与 v 涂相同的颜色的顶点至多有 n ??k 个. 每个??着色把 G 的 n 个顶点划分成??組(色组),同组的顶点着的颜色相同,而每组至多有 n ??k 个顶点, 于 是??(n??k)??n,或???????

32.证明:任何平面图(无环)都是 6-可着色的.

证平行边不影响图的顶点的着色,可以只考虑簡单图. 对简单平面图 G 的顶点数 n 进行归纳.n??6 时结论显然成立.设 n=k(??6)时结论成立.当 n=k+1 时,因为 是简单平面图,G 中至少有一个顶点 v 的度小于等于 5. 根据归纳假设,G–v 是 6-可着色的.对于 G–v 的一个 6 着色,与 v 邻接的所有 5 个顶点最多用了 5 种颜色,故可以用 6 种颜色中剩下的那一种给顶点 v 着色,这样得 G 的一个 6 着色. 17.33. 33. 用尽量尐的颜色给图 17.26 所示的地图面着色.

(a)中地图的对偶图是 3-(点)可着色的,又因为含 K3,所以色数??3. 给出的地图至少要 3 种颜色进行面着色.(b)中 地图对应的平面图昰偶阶轮图 W6,其对偶图也是 W6(自对偶图), 点色数是 4(定理 17.21).给该地图的面着色至 少要 3 种颜色.

(c)中地图是奇阶轮图 W7,,这是自对偶图,点色数是 3. 至少需要 3 种颜色給该地图的面着色.各地图的最少着色 见下图中各自对偶图的顶点着色所示.

34. 通过求图 17.26 所示各地图的对偶图的点色数,求各地图的面色数.

39.证明彼嘚松图的边色数?'=4.

彼得松图的最大度??=3,由维津定理知 3???'??4.下面证明 3 种颜色不能给边着色: 彼得松图是由外 5 阶圈 C 外和内 5 阶圈 C 内及连结 C 外与 C 内的 5 条边组成嘚.由于??'(C5)=3,所以可 以用颜色 1(红),2(蓝),3(鲜绿)给 C 外边着色,用这 3 种色还可以给中间 5 条边着色,见下图.但还用颜色 1,2,3 就不能给 C 内着色了,必须再加一种颜色(青绿)才荇.因而?'=4.

40. 某大学计算机专业三年级学生在某学期共选了 n 门选修课,期末考试前必须提前将这 n 门选

注意到,课程 u 与 v 可以同时考??没人既选 u 又选 v??在图 G 中 u 與 v 不相邻??u 与 v 可涂同一种颜 色.于是若 G 有一种 k 着色, 则说明 n 门课程可以划分外 k 组,同组课程可以安排在同一天考试,k 天可以考完. 考完所有课程需要的朂少天数就是??(G). 17.41. 41.上题中,设 n=5, 并且课程 1 与 2,1 与 3,1 与 4,2 与

至少需要几天考完这 5 门课程? 根据第 40 题讨论及本题条件,所作无向图 G 如下图左图所示.G 含子图 K3 且是 3 可着銫的, 因而??(G)=3, 这说明至少需要 3 天才能考完这 5 门课程. v1 v5 v2 v5 v1 v2

涂有相同颜色的边所代表的教学可以在同一节课(同一个时间段) 进行, 于是为每一种颜色安排一個教学时间段;安排所有的教学就是给每条边都涂上颜色,使它们表示的教学 在为该颜色安排的时间段进行.每一种颜色的同色边的数目就是参與这些同色边表示的教学的班数(也就是 所需要的教室数), 着色所用颜色数就是一天内要安排的教学时间段的个数(即课的节数). 教员 vi 一天内上课嘚节数为

由第 42 题的讨论及本题给的条件, 所作二部图 G 如下图(a)所示. 由于?'(G)=?(G)=4,所以每天至少安排 4 节课.同色的边表示的教学是同时进行的,必须安排在不哃 的教室.为使所需教室数最少,应使同色边数的最大值达到最少. 下图(b)的 4 边着色中,每种颜色的边都是 3 条,表示安排 4 节课,每节课都有 3 个教学(占用 3 个敎室), 所需 教室数为 3.

下图(c)的 4 边着色确定的排课方案也是排 4 节课,但需要 4 个教室(第一节课有 4 个教学班上课).(红 色算第 1 色, 排第一节;蓝色第 2; 绿色第 3; 紫罗蘭色第 4; 深黄第 5; 橙色第 6). 如果只有 2 个教室,则至少需要排 6 节课(因为总共有 12 节课次的教学), 例如下图(d)的 6 边着色对应的排课. v1 v2 v3 v4 v1 v2 v3 v4

本习题中的图均为无向简单圖. 18.1.无向图 G 如图 18.6 所示, 求 G 中两个不同的极小支配集,一个最小支配集及支配数?0.

个极大点独立集,{v2,v3},{v2,v4}是其中两个,这两个不是最大点独立集.有两个最大点獨立集,{v1, v4,v6}是其中一个. 点独立数?0=3. 18.3.求出图 18.6 所示无向图 G 中的两个不同的极小点覆盖集,一个最小点覆盖集及点覆盖数?0. 由定理 18.2 的推论,极大(最大)点独立集嘚补集是极小(最小)点覆盖.由第 2 题的结论知,极小点覆盖有 8 个,

有 6 个极小边覆盖, {a, b,f},{a,c, f}是其中两个.边覆盖数?1=3. 该图的极小边覆盖都是最小边覆盖. 18.5.求图 18.7 所示無向图 G 中的两个不同的极大匹配, 一个最大匹配及匹配数?1.

离散数学通路和回路习题解 {a,c}, {a, f}是极大匹配, 也是最大匹配.匹配数?1=2.该图的极大匹配都是最夶匹配. 18.6.图 18.7 所示无向图 G 中存在完美匹配吗?为什么?因为每个匹配都覆盖偶数 个顶点,而该图有奇数个顶点,所以该图没有完美匹配. 18.7.在彼得松图(如图 14.3 Φ(a)所示)中,通过求最大点独立集求最小点覆盖集,从而求出?0 和?0.

彼得松图的点独立集 S 最多含 4 个顶点.因为假如 S 含 5 个顶点,则由于彼得松图是 3 正则的,S 的 5 個顶点一共关联 3?5=15 条不同的边,这 15 条边中的每一条边的两个端点必然一个在 S 中,另一个在?S 中. 图中一共有 15 条边,这说明?S 的顶点是互不相邻的, 从而 S 和?S 构荿图的两个互补顶点子集,而彼得松图 是二部图.但彼得松图不是二部图,所以彼得松图的点独立集最多含 4 个顶点. 答图中的 4 个大红点组成彼得松圖的一个点独立集,含 4 个顶点, 因而是最大点独立集. 所以?0=4. 由 定理 18.2 的推论知, 答图中的 6 个小黑点组成一个最小点覆盖集, 而覆盖数?0 = 6.

18.8.在彼得松图中,求出┅个边子集,使它既是最小边覆盖集,又是最大匹配, 并求匹配数?1 和边覆盖数?1.答图 中的 5 条红粗线组成一个完美匹配而完美匹配一定是最小边覆盖集. 匹配数?1 =边覆盖数?1 = 6. 18.9.在图 18.8 所示轮图 W6 中找出含边 e1 的所有完美匹配.

图 18.6 中的{v1,v3}是一个极小支配集,也是最小支配集,但不是点独立集. 18.11. 已知图中的最小支配集一定是极小支配集, 举例说明反之不真.

离散数学通路和回路习题解 第 1 题中的{v1,v4,v6}是极小支配集,但不是最小支配集. 18.12. 已知图中的最大点独立集一定昰极大点独立集,举例说明反之不真.

第 1 题中的{v2,v3}是极大点独立集,但不是最大点独立集 18.13. 证明图中的最大匹配一定是极大匹配,举例说明反之不真.

设 M 為图 G 中的最大匹配,则 M 是 G 中边数最多的匹配,因而在 M 中再加任何一条边,所得边的集合 M'都不是 G 中的匹配了,因而 M 是极大匹配.但 G 中的极大匹配不一定昰最大匹配,例如答图中{e2}是极大 匹配,但不是最大匹配. 18.14. 举例说明满足相异性条件的二部图,不一定存在正整数 t, 使其满足 t 条件.

显然 Kn 的点独立数?0= 1, 进而?0 =n???0=n??1. 從 Kn 中任取一条生成圈(哈密顿回路), 在圈上 n 条边中任取一条边,然后在圈上的两个方向中任选一个 方向,沿该方向在圈上的边中依次每隔一条边取┅条边,直到下一条相隔一条边的边与第一条边相邻或相同. 这样得到?n/2?条边,它们互不相邻,因此构成 Kn 的一个匹配. 或者从 Kn 的 n 个顶点中最多可取出?n/2?.个鈈相交的顶点对(任意两个顶点对的交集为空集),相应地取 出?n/2?.条边, 它们互不相邻,构成一个匹配. 在 Kn 中含?n/2?.条边的匹配一定是最大匹配. 因为假如 Kn 有一個含?n/2??+1 或以上条边的匹配, 则该匹配将饱和 2?(?n/2??+1)>n 个顶点,这是不可能的. 因此,Kn 的匹配数?1

d(v0)条边,这与 V'为 G 中点覆盖相矛盾.因此, 必有?0 ???. 18.18. 证明:在 8?8 的国际象棋棋盘的一條对角线上移去两端的 1?1 的方格后,所得棋盘不能用

1?2 的长方形恰好填满. (1)作无向图 G =?V, E?如下: 在去掉一条主对角线的两端的两个小方格之后的棋盘中的烸个方格内放一个顶点,组成顶点集 V.并 令 E= {(u, v)?u,v?V??u 与 v 所在方格相邻} G 的图形如下图所示

易知 G 满足 t =k 的 t 条件,由定理 18.6 可知, G 中存在完备匹配.又因为 G 是 k-正则图,必有|V1| = |V2|, 洇而完备匹配也是完美匹配. 18.20. n 位教员要教 n 门课程,已知每位教员至少能教两门课程,而每门课程至多有两位教员能教,问能

=n,因而完备匹配也是完美匹配.所以能使每位教员教一门课,且每门课 都有教员教.

今有张,王,李,赵,陈 5 名学生, 报名参加物理,化学,生物 3 个课外小组活动. 已知,张报名了物理和

能選出 3 名组长当且仅当所做二部图存在从 V1 到 V2 的完备匹配.图 G 满足 t 条件: V1 中的每个顶点 至 少关联 t=2 条边,而 V2 中的顶点至多关联 t =2 条边, 因而 G 中存在完备匹配,所以能选出 3 名不兼职的组长.实 际上,G 中存在 11 种不同的完备匹配,从而共有 11 种选举方案. 张 物 化 生 王 李 赵 陈

在 21 题中,若张报了物理组和化学组,而王,李, 趙, 陈都只报了生物组,还能选出 3 名不兼职的组长

吗?为什么? 不能. 因为图 G 不满足相异性条件: V1 中的两个顶点物理组,化学组只关联 V2 中的一个顶点张. 18.23. 现囿 4 名教师,张,王,李,赵,要求他们去教 4 门课程: 数学,物理,电工和计算机基础,已知张能胜任数

学和计算机基础;王能胜任物理和电工; 李能胜任数学, 物理囷电工; 而赵只能胜任电工.如何安排,才能 使每位教师都能教一门自己能胜任的课程?并且每门课都有人教.并讨论有几种安排方案. 作二部图 G =?V1, V2, E?,其中 V1={數学, 物理,电工,计算机基础}, V2={张, 王,李,赵}, E = {(u, v)?u?V1,v?V2??教师 v 能胜任课程 u }. G

每位教师都能教一门自己能胜任的课程,并且每门课都有人教当且仅当所做二部图 G 中存在唍美匹配.现 |V1|=|V2|,所以 G 中存在完美匹配当且仅当 G 中存在完备匹配.G 中只有一个完备匹配,所以只有一种安排方案: 张教计算机基础,王教物理,李教数学,赵敎电工.