计算机数学基础（第三版）习题参考答案第9-10章习题参考答案习题9.11．对，对，对，对，对，错，对，错，对，对，错，错2．{,{},{{}},{},{,{}},{{},},{,},}a b c a b b c a c A φ3．{1,2,3,4,5},{2,3},{1,4},{5},{,{5}}φ4．B A -5.{,,,,,,,}a b a b ααββ<><><><>;{,,,,,,,}a b a b ααββ<><><><>;{,,,,,,,}αααββαββ<><><><>;{,,,,,,,}a a a b b a b b <><><><>;φ6.88. {2,3,3,4,5,4,7,4}<><><><>9.自反、对称、传递，是，{1,3},{2,4}10．不是；是，A ；是，{}a （对于所有a A ∈）11．{1,1,0,0,3,3,0,3,3,0,1,1,2,2,1,2,2,1}R =<--><><><><><><><><>习题 9.21．（1）是，0；（2）是，1；（3）不是；（4）不是；（5）是，未知；（6）不是；（7）不是；（8）是，未知.2．（1）P:张是计算机系学生；Q:张住在1号公寓305室；R: 张住在1号公寓306室；()P Q R ∧∨（2）P:张三和李四是好朋友；P（3）P:老李出差；Q:小王出差；()()P Q Q R ∧⌝∨⌝∧（4）P:生命息；Q:战斗止；P Q ⌝↔⌝（5）P:人知，Q:己为； P Q ⌝↔⌝（6）P:天气好，Q:比赛进行； P Q ⌝→⌝3．C4．（1）1；（2）0；（3）1；（4）1；（5）1；（6）15．（1）永真；（2）可满足；（3）永假；（4）可满足习题 9.31．（1）Q；（2）1；（3）1；（4）Q习题9.41．（1）()()()P a P b P c∧∧；（2）()()()∨∨；P a P b P c（3）(()())(()())(()())→∧→∧→；P a Q a P b Q b P c Q c（4）(()()())(()()())⌝∧⌝∧⌝∨∧∧P a P b P c P a P b P c2．将下列命题符号化：（1）a:小王；b:小李；()P x：x是大学生：()()∧P a P b（2）()H x：x是楼；a：这个：()()()∧∧F xG xH xF x：x建成了；()Q x：x是大的；()（3）(,)x M x P x a P a x∀∧∧M x：x是人；a：我：(()(,)(,))P x y：x为y；()（4）(,)M x：x是人：P x y：x犯y；a：我；()∀∧⌝→⌝∧∃∧→x M x P x a P a x x M x P x a P a x(()((,)(,)))(()((,)(,)))（5）(,)Q x y：x 是y国人；a：中国：M x：x是人；(,)P x y：x 在y工作；()⌝∀∧→(()((,)(,)))x M x P x a Q x a（6）()Q x y：x 是Q x y：x 是y的父亲；(,) P x：x是人；(,)Q x y：x 是y的外祖父；(,)y的母亲；(()()()(,)(,)(,))∀∀∀∧∧∧∧→x y z P x P y P z Q x y M z y F x z（7）()s x y：x=y：R x：x是素的；(,)P x：x是数；()Q x：x是偶的；()∃∧∧∧∃∧∧→(()()()((()()()(,))))x P x Q x R x y P y Q y R y s x y3．（1）1；（2）04．（1）0；（2）1复习题91．0 1 1 1 0 1 0 1 1 02．(1) ∅，{a}，{{b}}，{c}，{a，{b}}，{{b},{c}}，{a, c}，{a，{b}，c}=A(2) ∅，{∅}(3) ∅3．{,,,,{},,{},,{},,{},,{,},,{,},}a b a a a b b a b b a b a a b b φφ<><><><><><><><> 4．{1,2,3,4,5};{2,3};{1,4};{5}5．A6．D7．(1) 是等价关系；(2) 等价类分别为{2,3,6}, (1,4), {5}8．(1) 是，1；(2) 是， 0；(3) 不是；(4) 不是；(5) 不是；(6) 是，未知9．(1,0,0,),(1,0,1),(1,1,1)10．永真11．B ∧C12．(1) F(x)：x 是偶数，Q(x)：x 是素数，a ：2，F(a)∧Q(a)(2) G(x,y)：x 比y 高，a ：张华，b ：黎明，c ：王宏，G(a,b)∧G(b,c)→G(a,c)(3)；个体域是所有母亲的集合，M(x)：x 表示爱自己的孩子，∀xM(x)(4)；M(x)：x 是人，H(x)：x 表示要呼吸，∀x(M(x)→H(x))(5) R(x)：x 表示实数，Q(x)：x 表示有理数，∃x(R(x)∧Q(x))13．A14．0 1 1 0习题 10.11．（1）deg 3,deg 2,deg 1,deg 2,deg 2u v w x y =====；（2）deg 1,deg 2,deg 3,deg 2,deg 2u v w x y =====2．（1）（4）能；（2）（3）不能3．C5. C A7．（b ）与（e ）同构；（c ）与（g ）同构；（d ）（f ）（h ）同构习题 10.21．（1）(,,)a b c 长度2；(,,,)a c b e 长度3；(,,,,)a c d b e 长度4；(,,,,,)a b c d b e 长度5；(,,,,,)a b d c b e 长度5（2）(,,)a b c 长度2； (,,,,)a c d b e 长度4；(,,,)a c b e 长度3（2）(,,)a b c ；(,,,)a b d c ；(,,)c b d4．5个5．（1）割点b ；桥(,)b e ；割集{(,)},{(,),(,)},{(,),(,)},{(,),(,),(,)},{(,),(,),(,)}b c a b a c c d d b a c b c c d a b b c b d（2）()2,()3k G G λ==习题 10.31．（1）,,,,a b c d e 的入度和出度分别为1,1,3,2,0;2,2,0,1,0（2）(,),(,,,),(,,,)a c a b a c a b d c（2）弱连通3．强连通，只是单侧连通，只是强连通4．（1）2311123nn n n P P P n +++（2）012222n n n n P P P ----+++（3）0122222()n n n n P P P ----+++习题 10.41．0100100010111110,0101001101100101A M ==2．1345113411451(,,,,),(,,,),(,,,)v v v v v v v v v v v v v习题 10.51．（1）可达性矩阵上元素全为12．（2）弱连通；（3）2,3,3,33．001001100010101001000011010101,,000010101110101010000010011101100001000110101A M P --===--- 231a =代表有一边以2v 为起点，3v 为终点；231b =-代表2v 为3l 的终点；231c =代表2v 至3v 可达习题 10.61．C2．（c ）为欧拉图，（c ）（d ）可一笔画3．（a ）有欧拉闭迹（b ）有欧拉迹4．n K 当n 为奇数时为欧拉图，n K 为哈密顿图5．（c ）（d ）为哈密顿图，其余全不是，除（b ）外均有哈密顿路6．不是欧拉图，但有欧拉迹，是哈密顿图习题 10.72．95．弦：(1,2),(1,5),(4,5),(3,4),(1,3),(2,5)；基本回路(1,2,4,1),(1,4,2,3,5,1),(4,5,3,2,4),(3,4,2,3),(1,3,2,4,1),(2,5,3,2) 8．22,1,1n n n ---9．C 10. G 连通；m+1－n复习题101．(2) 结点v 1, v 2, v 4是与v 3邻接，v 3关联的边为e 1, e 2, e 3。

(3) 边e 2, e 3, e 4均与边e 3邻接；与边e 1关联的结点为v 2, v 3。

(4) 结点v 6是孤立点；e 5是孤立边。

(5) deg(v 1)=3，deg(v 2)=2，deg(v 3)=3，deg(v 4)=2，deg(v 5)=2，deg(v 6)=0，deg(v 7)=1，deg(v 8)=1，(6)不是2．(1) 17；(2) 83．A4．（1）强连通（2）6，9，13，20（3）0 1 0 00 1 0 0 0 01 0 1 0 1 0 0 1 0 0,1 0 0 10 0 1 0 1 00 0 1 00 0 0 0 0A M==1 1 1 11 1 1 1,1 1 1 11 1 1 1 1P=5．（1）b是，a c d不是（2）a b c是，d不是6．(1)(2)2n n--。