电大计算机本科【计算机数学基础(1)】形成性考核册答案（附完整题目）.doc

电大【计算机数学基础(1)】形成性考核册答案【计算机数学基础(1)】形考作业一：第1章命题逻辑一、单项选择题1. 下列语句是真命题为( )A. 我正在说谎 B.如果1+2=3，则雪是黑的C. 如果1+2=5，则雪是黑的 D. 你上网了吗？答案：C解答：A. 我正在说谎，这是勃论“我正在说”的真值应是1，但是说的是错话，真值为0故是勃论B.这是蕴涵式令P：1+2=3，真值为1；Q：雪是黑的，真值为0，于是100“如果1+2=3，则雪是黑的”是假命题C. 令P：1+2=5，真值为0；Q：雪是黑的，真值为0，于是001于是“如果1+2=5，则雪是黑的”是真命题选项C正确D. 这是疑问句，不是命题2. 命题公式P(QP)为( )A. 重言式B.可满足式C.矛盾式D.等值式答案：A解答：P(QP)P(QP)(PP)Q1故选择A二、填空题1. P,Q为两个命题，当且仅当 时，PQ的真值为1，当且仅当时，PQ的真值为0答案：P1Q1 (或P的真值为1且Q的真值为1)；P0Q0解答：见教材关于合取与析取的真值表2. 给定两个命题公式A，B，若，则称A和B时等值的，记作AB答案：AB1解答：见教材“等值”的定义3. 任意两个不同极小项的合取为，全体极小项的析取式为式答案：永假式；永真解答：见教材第22页的两条性质三、计算题1. 将下列命题符号化；(1) 李强不是不聪明，而是不用功(2) 如果天不下雨，我们就去郊游(3) 只有天不下雨，我们才去郊游解答：(1) 令P：李强聪明，Q：李强用功原命题符号化为“(P)Q”(2) 令P：天下雨；Q：我们去郊游原命题符号化为“PQ”(3) 令P：天下雨；Q：我们去郊游原命题符号化为“QP”2. 给出下列公式的真值表；(1) (PQR)PQR； (2) (PQ)(QR)(PR)解(1) 命题公式(PQR)PQR 的真值表PQRPQPQRRPQR(PQR)PQR0000110000101000010011000110100010001100101010001101011111111000(2) 命题公式(PQ)(QR)(PR)的真值表PQRPQQR PR(PR)(PQ)(QR)(PR)00011011 00111011011001101111011100011011010101 111010101111110113. 给P和Q指派真值1，给R和S指派真值0，试给出下列命题的真值：(1)P(QR).解P(QR)1(10)1014. 判断下列命题公式的类型：(1)P(PQR)解P(PQR)PPQR16. 通过求命题公式(PQ)R的主合取范式，求其真值为0的真值指派解方法1等值演算法(PQ)R(PQ)R(PQ)R(PR)(QR)(P(QQ)R)(PP)QR)M4M6M2命题公式(PQ)R的成假赋值为：(1，0，0)，(1，1，0)，(0，1，0)注：由此马上可以得到命题公式(PQ)R的主析取范式为(PQ)Rm0m1m3m5m7 (PQR)(PQR) (PQR) (PQR) (PQR)方法2列真值表法命题公式(PQ)R的真值表PQRPQPQR0000100101010100111110010101111101011111取命题公式(PQ)R为0的析取项的合取为所求主合取范式(表中末列的第3,5,7行)：(PQ)R取命题公式(PQ)R为1的合取项的析取为所求主析取范式(表中末列的第1,2,4,6,8行)：(PQ)R(PQR)(PQR) (PQR) (PQR) (PQR)7. 试求命题公式化PQR的主析取范式和主合取范式解先求主析取范式PQR(PQ(RR)(PP)(QQ)R)(PQR) (PQR)(PQR) (PQR) (PQR) (PQR)(PQR) (PQR) (PQR) (PQR) (PQR)m7m6m3m5m1再求主合取范式PQR(PQ)R(PR)(QR) (P(QQ)R)(PP)QR)(PQR) (PQR) (PQR) (PQR)(PQR) (PQR) (PQR)M0M2M4四、证明题1. 用等值演算法证明P(PQ)Q为重言式证明P(PQ)QP(PQ)Q(PP)(PQ)Q(PQ)QP(QQ)13. 构造下面推理的证明：(1)前提：RQ，RS，SQ，PQ结论：P证明方法1用归谬法(反证法) (P) 否定结论引入P T E1 PQ 前提引入Q T,I11假言推理 Q T,E1 RQ 前提引入 R T，I12拒取式 RS 前提引入 S T,，I10析取三段论 SQ 前提引入11 Q T,，I11假言推理12 QQ T,11，矛盾方法2直接证明 RQ 前提引入RQ T E16 SQ 前提引入SQ T,E16 (RQ)(SQ) T ,，I9合取引入1 (RS)Q T， RS 前提引入 Q T,，I10析取三段论 PQ 前提引入 P T,，I12拒取式注：还有其它方法，如证明(RQ)(RS)(SQ)(PQ)P是永真式(即真值为1)请同学自己练习第2章谓词逻辑一、单项选择题1. 设L(x)：x是演员，J(x)：x是教师，A(x,y)：x佩服y命题“所有演员都佩服某些教师”可符号化为( )A BC D答案：B解答：选项A显然不对，公式中y是什么都没有交待选项B中，公式翻译出来为“任给x，如果x是演员，就存在y(有一些y)，若y是教师，都有演员佩服教师”，也即“所有演员都佩服某些教师”此命题中，L(x)和J(x)都是特性谓词，对全称量词，特性谓词后用，对存在量词$，特性谓词后用，见教材第41页1415行故选项B正确选项C中，公式翻译出来为“任给x，x是什么没交待，紧跟其后存在y，y是什么，没交待，关系乱故选项C不正确选项D中，公式翻译出来为“任给x，x是什么没交待，紧跟其后存在y，y是什么，没交待，关系乱，且没有蕴涵联结词故选项D不正确2. 与是( )A. 等价式B.蕴含式C.重言蕴含式答案：A解答：选项A，对任意解释I，有DI，xA(x)要么是1,要么是0，但是B是命题，它的真值是确定的先看xA(x)B的真值若B1，有；若B0，有再看xA(x)(x)B的真值因为B与x无关，xB的真值与B的真值相同有若B1，则xB，有；若B0，则xB1，有可见，故选项A正确从上面的解释可知，但是要注意：与不等值而是二、填空题2. 公式中的自由变元为，约束变元为答案：x，y；x，z解答：在中x是约束变元，y是自由变元在中约束变元是z，自由变元是y在S(x)中只有自由变元x总之，在公式中约束变元是x，z；自由变元是x，y三、计算题1. 在谓词逻辑中，将下列命题符号化：(1) 有些人喜欢所有的花；(2) 尽管有人聪明，但未必每个人都聪明解(1) 设M(x)：x是人，F(x)：x是花，L(x,y)：x喜欢y命题“有些人喜欢所有的花”符号化为：(2) 设M(x)：x是人，H(x)：x是聪明命题“尽管有人聪明，但未必每个人都聪明”符号化为：或2. 对下面每个公式指出约束变元和自由变元：(1) $xy(P(x)Q(y)xR(x)； (2) $x$y(P(x,y)Q(z) 解(1) $xy(P(x)Q(y)xR(x)中的约束变元是：x，y；无自由变元 (2) $x$y(P(x,y)Q(z)中的约束变元是：x，y；自由变元是：z3. 设个体域D=a,b,c，试将下列各式化为不含量词的形式：(1) xF(x)$xG(x)； (2) x(P(x)Q(x)解(1) xF(x)$xG(x)F(a)F(b)F(c)(G(a)G(b)G(c)； (2) x(P(x)Q(x)(P(a)Q(a)(P(b)Q(b)(P(c)Q(c)4. (1) 已知解释I如下：个体域DI=2,3,6；DI中的特殊元素e=6，P:32，Q(x)：x3，R(x)：x5求x(PQ(x)R(e)的真值(2) 已知解释N如下：个体域DN=2；P(x)：x3，Q(x)：x=3求$x(P(x)Q(x)解(1) x(PQ(x)R(e)(PQ(2)(PQ(3)(PQ(6)R(6)(11)(11)(10) 11101011(2) $x(P(x)Q(x)P(2)Q(2)0015. 求谓词公式xP(x)zQ(x,z)zR(x,y,z)的前束范式解xP(x)zQ(x,z)zR(x,y,z) $xP(x)zQ(x,z)zR(x,y,z) (化去)$uP(u)vQ(x,v)zR(x,y,z)(约束变元换名)$uvz(P(u)Q(x,v)R(x,y,z)(扩大量词的辖域)$uvz(P(u)Q(x,v)R(x,y,z)注：最后两个都是前束范式6. 求谓词公式$x($yP(x,y)($zQ(z)R(x)的前束范式解$x($yP(x,y)($zQ(z)R(x)$x(yP(x,y)(zQ(z)R(x)(化去)$xyz(P(x,y)(Q(z)R(x)(扩大量词辖域) $xyz(P(x,y)( Q(z)R(x)四、证明题1. 试证明xA(x)xB(x)x(A(x)B(x)证明xA(x)xB(x)x(A(x)B(x)，只须证明xA(x)xB(x)x(A(x)B(x)1方法1若xA(x)xB(x)0，则必有xA(x)xB(x)x(A(x)B(x)1；若xA(x)xB(x)1，即对任意解释I,有DI，xA(x)1或xB(x)1，即xDI，有A(x)1或xDI，有B(x)1，也就是xDI，有A(x)1或B(x)1，有x(A(x)B(x)1即x(A(x)B(x)为真总之有xA(x)xB(x)x(A(x)B(x)1，所以xA(x)xB(x)x(A(x)B(x)方法2构造证明 xA(x)xB(x) 前提引入 A(y)xB(x) T,US A(y)B(y) T,US y(A(y)B(y) T,UG x(A(x)B(x)2. 构造下面推理证明：前提：$xP(x)xQ(x)结论：x(P(x)Q(x)证明方法1，归谬发(反证法) x(P(x)Q(x) 否定前提引入 x(P(x)Q(x) T,E16 $x(P(x)Q(x) T,否定移入 P(c)Q(c) T，ES P(c) T，化简 Q(c)T，化简 $xP(x) T,EG $xP(x)xQ(x) 前提引入 xQ(x) T,，I11,假言推理 Q(c) T,US Q(c)Q(c) T,，I9合取引入方法2 $xP(x)xQ(x) 前提引入 xP(x)xQ(x) T，消去 x(P(x)Q(x) T，教材第48页3.(14)（） x(P(x)Q(x) T，E16电大天堂【计算机数学基础(1)】形考作业二：第3章集合及其运算一、单项选择题1. 设集合A=1,a，则P(A)=( )A. 1,a B. ,1,a C. ,1,a,1,a D. 1,a,1,a答案：C解答：依据幂集合的定义，P(A)是由A的所有子集构成的集合，集合A的子集有：，1,a和1,a故选项A正确2. 设A,B,C为任意三个集合，下列命题正确的是( )A. 若AB=AC，则B=C B. 若AB=AC，则B=C C. 若AB=E且AB，则A=B D. 若AB，则A=B答案：C解答：若A=1,2,3，B=1,2，C=1,则AB=AC，但BC故选项A不正确若A=a,b，B=a，C=a,c有AB=AC，但BC故选项B不正确因为AB，故AB=，又AB=E，故A=B，所以A=B故选项C正确若AB，则有AB故AB，得不到A=B故选项D不正确3. 设A,B,C,D为任意四个集合，下列命题正确是( ).A. (BC)A=BACAB. (AB)CA(BC)C. (BC)A=(BA)(CA)D.AC且BD，则ACBD答案：A解答：选项A.正确证明如下，(BC)Ab(BC)aA(bBbC)aA(bBaA)(bCaA)BACA( BACA)所以，(BC)A=BACA选项B.中笛卡尔积(AB)C的有序对是,c的形式，而A(BC)的有序对是a,的形式，它们不相等选项C.不正确，举例说明如A=a,B=1,2,C=2,3,于是(BC)A而BACA,=,所以(BC)A(BA)(CA)若将右端的改为，即有(BC)A=(BA)(CA)证明类似选项A.请读者练习选项D作为一般结论不成立，正确结论请见教材第83页定理6若A=B=时，结论成立二、填空题1 . 填写下列集合之间的关系：(1) 1,3,7 3,7；(2) 5,75,8；(3) 1,3；(4) 2,3 2,3答案：(1) 或；(2) 或； (3) 或； (4) =解答：(1) 显然3,7是1,3,7的子集，且是真子集，故填写“”一般地，子集用“”也可以(2) 这两个集合不存在互为集合，填写“或”都不错更确切讲应说“5,7与5,8是相交集合”(3) 空集合是任何集合的子集，故填写“或”都可以(4) 它们是一个集合，相等2. 由集合的吸收律，(AB)B= ，A(AB)= 答案：B；A解答：按照教材第72页：8.吸收律为A(AB)=A由于交和并的运算都有交换律，故(AB)B=B(BA)=BA(AB)=A3. 有序对=的充分必要条件是答案：a=x,b=y解答：见教材第3章3.3节有序对的定义10三、计算题1. 用列举法或描述法表示下列集合：(1) 不超过29的全体素数组成的集合；(2) 不等式的解集解(1) S=2,3,5,7,11,13,17,19,23,29(列举法)(2) A=xx10x=xx1x(描述法)2. 设A=x3x4，x求(1) AB； (2) AB；(3) AB解(1) AB=x(3x4)x=x3xx(2) ABx3x4，xx3x4x(3) AB(AB)(AB)= x3xxx4x5x=xx3x4x.5x3. 设全集为自然数集合，其子集A=xx为小于8的素数，B=xx30且x能被3整除，C=2x1x5，D=x21x3求下列集合：(1)B(AC)；(2) (AB)D解A=2,3,5,7，B=0,3,6,9,12,15,18,21,24,27,30，C=2,4,8,16,32，D=1,4,9.(1)AC=2,3,4,5,7,8,16,32 B(AC)= 0,3,6,9,12,15,18,21,24,27,302,3,4,5,7,8,16,320,6,9,12,15,18,21,24,27,30(2) (AB)=(0,1,4,6,8,9,10,29,30,31,32,)0,3,6,9,12,15,18,21,24,27,301,4,9 =0,6,9,12,15,18,21,24,27,301,4,9=0,1,4,6,9,12,15,18,21,24,27,304. 化简下列集合表示式：(1) (AB)B)(AB)；(2) (ABC)(BC)A解(1) (AB)B)(AB)B(AB)=BAB=(吸收律)(2) (ABC)(BC)A=(A(BC)(BC)A=(A(BC)A=A(吸收律)5. 设集合A=a,b，B=1,2,3，C=3,4求A(BC)，(AB)(AC)，并验证A(BC)(AB)(AC)解A(BC)a,b1,2,33,4=a,b3=,；(AB)(AC)(a,b1,2,3)a,b3,4=,=,所以A(BC)(AB)(AC)一般地，证明A(BC)(AB)(AC)，如下， A(BC)aAb(BC)(aAaA)(bBbC)(aAaB)(aAbC) (AB)(AC) (AB)AC)所以A(BC)(AB)(AC)四、证明题1. 设A,B,C为三个任意集合，试证A(BC)=(AB)C证明方法1 A(BC)=A(BC)=A(BC)=(AB)C(AB)C方法2x x(A(BC)xAx(BC)xA(xBxC)(xAxB)xCx(AB)xCx(AB)C2. 对于任意三个集合A，B和C，试证：(1) 若AABB,则A=B；(2)若ABAC且A，则B=C证明(1) x xAxAxAAABBxBxBxB所以A=B(2) x，因为A，存在aA，aAxBABACaAxC，所以B=C3. 设A，B为三个任意集合，证明：P(A)P(B)P(AB)证明xxP(A)P(B)xP(A)xP(B)xAxBx(AB)xP(AB)所以P(A)P(B)P(AB)第4章二元关系与函数一、单项选择题1. 设集合A=1,2,3,4，A上的二元关系R=,，S=,则关系( )=,A. RS B. RS C. RSD.SR答案：B解答：显然选项A不对，RS不可能是,选项B. RS=,故选选项B2. 设集合A=a,b上的二元关系R=,，则R( )A. 是等价关系但不是偏序关系B是偏序关系但不是等价关系C. 既是是等价关系又是偏序关系 D. 既不是等价关系又不是偏序关系答案：C解答；R=,实为恒等关系IA依据定义，R是自反的、对称的、反对称的和传递的，故R既是等价关系又是偏序关系，所以选项C正确4. 设函数f：RR，f(a)=2a+1；g：RR，g(a)=a2，则( )有反函数A. gf B. fg C.f D. g答案：C解答：只有双射函数才有反函数在这四个备择选项中，可以证明只有f(x)是双射函数故选项C正确二、填空题2. 设集合A=a,b,c,d，A上的二元关系R=,，S=,则RS=，R2=答案：,；,解答：按照关系的复合，若R：AB，S：BC，那么RS：ACRS=$bB，使得RS本例R，S都是A上关系，即A=B=C按照复合定义计算得到RS,；R2=RR=,1 42 3 图41 关系图3. 设集合A=1,2,3,4，A上的二元关系R=,，则逆关系R1的关系矩阵=R1的关系图为答案：；关系图如41.4. 设集合A=a,b,c上的二元关系R的关系矩阵MR=，则R具有的性质是 且MS(R)= 答案：反对称性；解答：写出关系R=,易验证R具有反对称性再写出对称闭包s(R)=,，它的矩阵为MS(R)=5. 设集合A=a,b，B=1,2，则从A到B的所有函数是，其中双射的是答案：函数为f1=, f2=, f3=, 41=,； 双射有f2=, f3=,三、计算题1. 设R是从A到B的二元关系，写出下列各式中关系R的关系矩阵，并画出关系图(1) A=a,b,c,d，B=1,2,3，R=,； a 1b 2c 3d图42(2) A=1,2,3,4,5，B=1,2,3，R=aA,bB且2a+b4解(1)关系矩阵为MR= 关系图如图42(2) 写出关系表达式R=,关系矩阵为 1 12 23 345图43MR=，关系图如433. 设集合A=1,2,3,4上的二元关系R=,，判断R具有哪几种性质?解不难验证，任给xA,则R，故R自反性；任给x,yA，若R,则R，故R具有对称性a b c d图44R的关系图4. 设集合A=a,b,c,d上二元关系R的关系矩阵为MR=，求r(R)，s(R)，t(R)及其关系矩阵，并画出R，r(R)，s(R)，t(R)的关系图解由MR写出R的集合表达式，R=,R的关系图如图44在R中添加最少的元素，使得R具有自反性，有r(R)= ,a b c d图45r(R)的关系图Mr(R)=；r(R)的关系图如图45在R中添加最少的元素，使得R具有对称性，有s(R)= ,，,a b c d图46s(R)的关系图Ms(R)=；r(R)的关系图如图46在R中添加最少的元素，使得R具有传递性，有t(R)=RR2R3R4= , , , ,a b c d图47t (R)的关系图= ,Mt(R)=；t(R)的关系图如图47注：在关系闭包中，下画线的元素是后加的元素因为RRR，由传递性的充分必要条件，R具有传递性故t(R)=R5. 设集合A=0,1,2,3,4,5，上的二元关系R=,试用关系图验证R是A上的等价关系，并求出R在A上的等价类0 15 4 3图48R的关系图2解做R的关系图，如图48由图可知，R是A上的等价关系R的等价类：0=0 1=1,2,3 4=4,5a,b,c,d,ea,b,c,da,b,ca,ba b图4-9的哈斯图7. 设集合A=a,b,a,b.a,b,c,a,b,c,d,a,b,c,d,e，A在包含关系“”下构成一个偏序关系列举的集合表达式，并画出的哈斯图解先写出集合表达式,的哈斯图如图498. 下列函数中，哪些是满射的？哪些是单射的？哪些是双映射？(1) f1：，f1(a)=a3+1； (2) f2：，f2(a)=a除以3的余数；(3) f3：，f3(a)=a22a15解(1) 显然f1(a)=a3+1是的映射，且f1(a)是双射函数，证明如下任给x1,x2且x1x2，则有f1(x1)=，故f1(a)是单射的任给y,则存在x=，有f1(x)=(x)3+1=，故f1(a)是满射的所以，f1(a)是双射函数(2) f2(a)将映射到0,1,2，易见f2是的映射，但是不是满射；又f2(9)=f3(3)=0，故也不是单射(3) 易见，f3(a)=a22a15是的函数因为f3(a)=a22a15是二次函数，它的值域是16,+）可见f3(a)不是满射又如f3(5)=f3(3)=0，可见f3(a)不是单射9. 设是实数集，对任意a，上的函数分别为：f(a)=a22，g(a)=a+4，h(a)=a31(1) fg，gf(2) 问fg和gf是否是满射、单射、双射？(3) f，g，h中哪些函数有反函数，若是，求出该反函数解(1) 任给x,fg(x)=g(f(x)=g(x22)+4=x22+4=x2+2，gf(x)=f(g(x)=g2(x)2=(x+4)22=x2+8x+14；(2) 由(1)可知，fg和gf都是二次函数，因此都既不是满射也不是单射(3) 因为g(a)=a+4和h(a)=a31是双射函数，故它们有反函数g(a)=a+4的反函数为g1(a)=a4，h(a)=a31的反函数为h1(a)=四、证明题2. 若R四集合A上的等价关系，则R1也是A上的等价关系证明等价关系，要具备自反性、对称性和传递性下面逐一证明xA，因为R是自反的，故R，由逆关系的定义，则R1，所以R是自反的；x,yA，如果R1，则R(R对称)RR1故R1是对称的x,y,zA，如果,R1，则,R(R对称且传递)RR1，故R1是传递的总之，R1是等价关系4. 设f：XY，A,B是Y的任意子集，证明f1(AB)=f1(A)f1(B)证明x，所以，x，所以，总之，电大天堂【计算机数学基础(1)】形考作业三： 第5章 图的基本概念一、填空题: 2*4=81图G有21条边,3个4度结点,其余均为3度结点,则G有_个结点答案：13 图51图G解答：设图G有x个结点，由握手定理43+3(x3)=221=42，解上式得x=132已知图51,它的点连通度(G)为_,边连通度(G)为_答案：1；1解答：因为图G存在割点和割边，依据教材第5章定义12和13，知K(G)=1，l(G)=13、略4设有向图D= , ,为G的邻接矩阵,则D中结点的出度之和为 ,结点vj的入度之和为 ，所有结点的度数之和为 答案：矩阵中第i行元素之和；矩阵中第j列元素之和；2解答：邻接矩阵的定义是aij是结点vi邻接到vj的边的条数，所以aij，ai2,ain代表了从vi出发到结点v1,v2,vn所有边的数目，故D中结点的出度之和为矩阵中第i行元素之和类似地，a1j，a2j,anj代表了从结点v1,v2,vn出发到vj所有边的数目，故D中结点vj的入度之和为矩阵中第j列元素之和根据握手定理，所有结点度数之和为边的两倍二、计算题：3*8+8=321已知无向图G=,V=E=v1 v6v2 v5v3 v4图57图G(1)画出G的图形;(2)求出G中各结点的度数 解 (1)图G如图57(2)计算各结点的度数：=5，1,=4=4,=2,=02画出下列各图的图形,并指出哪个是有向图,无向图,混合图,多重图,简单图:(1)G=，V=a,b,c,d,e,，E=(a,b), (a,c),(d,e),(d,d),(b,c),(a,d),(b,a)ab e c d图59 (2)G=，V=a,b,c,d,e,，E =, ,ab e c d图58 解 (1)图如图58，是无向图， 因为有环和平行线，故是多重图(2)图如59，是有向图3、略4给定图G= 如图52 所示求：(1)从A到F的所有简单通路；(2)从A到F的所有初级通路；(3)G中两条简单回路和初级回路解 (1)简单通路(边不重复的通路)有：ABCF；ABEF；ADEF；ADEBCF(2)初级通路(结点不重复的通路)有：ABCF；ABEF；ADEF；ADEBCF 图52A B CD E F(3)简单回路(边不重复的回路)有：ABEDA；ABCFEDA初级回路(结点不重复的回路(始点与终点除外)有：ABEDDA;ABCFEDA5试找出图53 的所有边割集和点割集解 图53中图(a)的边割集有 a,b,a,c,b,c,d,e(a) (b)图53B b C Ea e f c gA d DA D a b d e B c C点割集有C(割点)图53中图(b)的边割集有 a,b,e,a,d,f,b,c,f,c,d,e,a,e,f,c,befd,g(g是奇奥桥)点割集有：D，(D是割点)，6D= 如图5-4所示,试求D的关联矩阵和邻接矩阵解 无环有向图的关联矩阵定义为M(D)=mijnm，其中所以，有向图的邻接矩阵定义为图54e1v1v2e2e6e5e3e4e7e8e9v4v3v5A(D)=aijn，其中aij表示从vi邻接到vj的边的条数所以，7无向图G有12条边,G中有6个3度结点,其余结点度数均小于3,问G中至少有多少个结点?为什么?a be8e1 e2 e3 e4 ce5e e6 de9图55e7解 设图G有x个结点除6个3度结点外，其余都小于3度，则小于或等于2度，由握手定理，有21236+2(x6)解得x9图G至少有9个结点8在图5-5中, (1) 给出3条边和4条边的边割集;(2)求出一个最小的点割集;(3)求和e1v1 v4e2 e3 e5 e6 e7 v2 e4 v3图56e8 解 3条边的边割集：e4,e7,e8,e5,e8,e9；4条边的边割集：e1,e2,e2,e7,e1,e2,e6,e9,e3,e4,e5,e6,e3,e6,e7,e9,e1,e2,e2,e7；5条边的边割集：e1,e2,e3,e3,e8；6条边的边割集：e1,e2,e3,e4,e5,e9最小的点割集：a,c,d，b,d,e39求图56中图D的邻接矩阵A(D)，计算A2(D), A3(D),A4(D)，并找出从v1到v4长度为2,3,4的所有通路解图D的邻接矩阵为A(