离散数学答案屈婉玲版第二版高等教育出版社课后答案

1离散数学答案屈婉玲版第二版 高等教育出版社课后答案第一章部分课后习题参考答案16设p、q的真值为0； r、s的真值为1,求下列各命题公式的真值。(1) pV (q A r)二 0V (0 A 1) = 0(2) (p? r )A (qV s)二(0? 1)A (1 V 1)二 0A 1= 0.(3) ( 一 pA 一 qA r) ? (p A qAr)二 (1 A 1 A 1)? (0 A 0A 0)=0(4) (一 r A s) (p A q) =(0A 1) (1 A 0) = 00= 1 17 .判断下面一段论述是否为真：“二是无理数。并且，如果3是无理数，则 2也是无 理数。另外6能被2整除，6才能被4整除。”答：p:二是无理数 1q: 3是无理数 0r:2是无理数 1s: 6能被2整除1t: 6能被4整除 0命题符号化为：pA (qr) A (t s)的真值为1,所以这一段的论述为真19.用真值表判断下列公式的类型:(4) (pq) (_q_ p)(5) (p A r)(一pA 一q)(6) (pq) A (q r) (pr)答:(4)_pq_q111010 0 11 1 1 0所以公式类型为永真式p11 0 0q_p1101(pq)(一 q一 p)1111(5) 公式类型为可满足式(方法如上例)(6) 公式类型为永真式(方法如上例)第二章部分课后习题参考答案3. 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出 成真赋值 一(pAq-q)(2) (p-(p V q)V (p-r)(3) (pV q)-(pA r)答：(2) (p(p V q)V (p-r)二(一 pV (p V q) V (一 pV r)二 _ p V p V qV r：= 1 所以公式类型为永真式PqrpV qp A r(pV q) (pA r)000001001001010100011100100100101111110100111111所以公式类型为可满足式4. 用等值演算法证明下面等值式：(p q) A (p r)二(p (q A r)(p A - q) V (-pA q)= (p V q) A - (p A q)证明(2) (p q) A (p r)(_pV q) A ( 一 pV r)二 _pV (q A r)二 p (q A r)(4) (p A - q) V (一 pA q) = (p V (一 pA q) A(_ qV ( 一 pA q)二(p V _ p) A (p V q) A (一 qV_ p) A(_ qV q)=1 A (p V q) A _ (p A q) A 1-(p V q) A _ (p A q)5. 求下列公式的主析取范式与主合取范式，并求成真赋值(1) ( p q) LqVp)(2) _(p q) A qA r(3) (p V (q A r) (p V qV r)解：(1) 主析取范式(-p- q) - (-q p)=- (p q) ( - q p)=(一 P _q) ( 一 q p)二(_p_q)(一q p)(一q_p) (p q) (p _q)-(_p_q)(p_q)(p q)=m0m2m3=刀(0,2,3)主合取范式：(_pq) (一q p)-_(p q) (一 q p)u ( - p -q) ( q p)=(-p ( -q p)( -q (-q p)=1 (p q)二(p _q)二 Mi=n (i)(2) 主合取范式为：(p q) q r = 一( 一 p q) q r=(p _ q) q r = 0所以该式为矛盾式主合取范式为n (0,123,4,5,6,7)矛盾式的主析取范式为0(3) 主合取范式为：(p (q r) (p q r)=(p (q r) (p q r)=(一 p ( 一 q - r) (p q r)=(一 p (p q r)( 一 q - r) (p q r)二 1 i所以该式为永真式永真式的主合取范式为1主析取范式为刀（0,123,4,5,6,7）第三章部分课后习题参考答案14.在自然推理系统P中构造下面推理的证明前提：p； q, （q r）,r结论：_ p(4)前提：q“ p,qs,s i t,t r结论：p q证明：（2）(q r)前提引入q r置换 q r蕴含等值式r前提引入一 q拒取式p q前提引入p (3)拒取式证明（4）:t r前提引入t化简律qi s前提引入Si t前提引入q t等价三段论(q t)(t q) 置换炉（q T）化简q假言推理 q； p前提引入p假言推理(11)pq合取15在自然推理系统P中用附加前提法证明下面各推理(1)前提：p； (q r),s p,q结论：s-； r证明s附加前提引入p前提引入p假言推理 p (q - r)前提引入 q； r假言推理q前提引入r假言推理16在自然推理系统P中用归谬法证明下面各推理：(1)前提：p q,q,r - s结论：- p证明：p结论的否定引入 p；q前提引入厂q假言推理r q前提引入r化简律r s前提引入r化简律r r合取由于最后一步r r是矛盾式,所以推理正确.第四章部分课后习题参考答案3.在一阶逻辑中将下面将下面命题符号化，并分别讨论个体域限制为(a),(b)条件时命题的真值:(1) 对于任意X,均有声-2=(X+)(x T.(2) 存在X,使得x+5=9.其中(a)个体域为自然数集合.(b) 个体域为实数集合.解：F(x): F=2=(x+遢)(x ：區).G(x): x+5=9.(1) 在两个个体域中都解释为-xF(x)，在(a)中为假命题，在(b)中为真命题。 在两个个体域中都解释为xG(x)，在(a)(b)中均为真命题。4. 在一阶逻辑中将下列命题符号化：(1) 没有不能表示成分数的有理数(2) 在北京卖菜的人不全是外地人.解：(1) F(x): x能表示成分数H(x): x是有理数命题符号化为：-x(-F(x) H(x)(2) F(x): x是北京卖菜的人H(x): x是外地人命题符号化为：一-x(F(x) H(x)5. 在一阶逻辑将下列命题符号化：火车都比轮船快(3) 不存在比所有火车都快的汽车解：(1) F(x): x 是火车；G(x): x 是轮船；H(x,y): X 比 y 快命题符号化为：-x-y(F(x)G(y)； H(x,y)(1)F(x): X 是火车;G(x): x 是汽车;H(x,y): X 比y快命题符号化为:-y(G(y) -x(F(x)- H(x, y)9. 给定解释I如下：(a) 个体域D为实数集合R.(b) D中特定元素一 =0.(c) 特定函数(x,y)=x y,x,y D .(d) 特定谓词 W(x,y):x=y,(x,y):x G(x, y)答:(1)对于任意两个实数x,y,如果xy,那么x = y.真值1.(2) 对于任意两个实数x,y,如果x-y=0,那么x F(f (x), f(y)解:-xTyF(x, y)= x(F(x,3) F (x,4)=(F(3,3)F(3,4)(F(4,3)F(4,4)=(0 1) (1 0)= 1(2) x-y(F(x,y) F(f(x), f(y)=-x(F(x,3) F(f (x), f (3) (F(x,4) F(f(x), f (4)二-x(F(x,3) F(f (x),4)(F(x,4) F(f (x),3)二(F(3,3) F(f(3),4)(F(3,4) F(f(3),3)(F(4,3) F(f (4),4)(F(4,4) F(f(4),3)=(0 F(4,4)(F(3,4) F(4,3)(1 F (3,4)(0 F(3,3)=(0 0) (1 1) (1 1) (0 0) = 112. 求下列各式的前束范式。(1) -xF(x)-yG(x, y)(5) X1F(xX2) (H(xJ、- X2G(xX2)(本题课本上有错误)解:(1)-xF(x)_.、yG(x,y)二 -xF(x) , yG(t, y)二 x-y(F(x)r G(t, y)x1 F(x1,x2(H(xJ x2G(x1, x2)二 X1 F (X1 , X2 ) (H(X3)X2_G(X3,X2)X1F(X1,X4)X2(H(X3)一G(X3,X2)=-X (H(X3)G(X3,X2)15.在自然数推理系统F中,构造下面推理的证明：(1) 前提：xF(x)-y(F(y)G(y) R(y), xF(x)结论：T xR(x)(2) 前提：-x(F(x) -(G(a) A R(x), xF(x)结论：x(F(x) A R(x)证明(1) xF (x)前提引入 F(c)El xF(x) -y(F(y) G(y) R(y)前提引入一y(F(y)G(y) R(y)假言推理12#(F(c) V G(c) -R(c) F(c) V G(c) R(c) xR(x)UI附加假言推理EG13xF(x)前提引入F(c)EI- x(F(x) -(G(a) A R(x)前提引入 F(c) - (G(a) A R(c)UI G(a) A R(c)假言推理 R(c)化简 F(c) A R(c)合取引入 x(F(x) A R(x)EG第六章部分课后习题参考答案(1) a,b,c P(A)=-,a,b,c,a,b,a,c,b,c,a,b,c(2) 1, 2, 3P(A)=-，2,3, 1,2 , 3 (1)0匸0直/、(2)0乏0假(3)一 - 直/、(4)二三-直/、(5)a,b a,b,c, a,b,c 直/、(6)a,b a,b,c, a,b 直/、(7)a,b a,b, a,b 直/、(8)a,b -a,b, a,b 假.设:a,b,c 各不相同，判断下述等式中1哪个等式为真(1)a,b ,c, - = a,b ,c 假(2)a ,b,a =a,b 直/、(3)a, b) = a,b 假(4)G , -, a,b = 0 ,- ,a,b 假5.确定下列命题是否为真:8 求下列集合的幕集:614#P(A)=#(4) 、，、P(A)=-，1，2,3, 1,2 , 3 #14 化简下列集合表达式：(1) (A B) B ) - (A B)(2) (A B C) - (B C)A解:(AB)B ) - (AB) = (AB)B )(A B)=(A B)(A B) ) B=_ B=.(2) (A B C) - (B C)A= (A B C)(B C)A =(bUc) u(bUc)n (bUc) u a=（bU。）U0 Ua= （A“（ bU。）U A=A 18 某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5 人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数网球解：阿A=会打篮球的人，B=会打排球的人，C=会打 的人|A|=14, |B|=12, |AB|=6,|AC|=5 ,| A B C|=2,|C|=6,C A B如图所示25-(5+4+2+3)-5-1=25-14-5-仁5不会打球的人共5人21. 设集合A=1 , 2，2，3，1，3, 一 ,计算下列表达式:(1) A(2) A(3) A(4) A解：(1)A=1，22，31，3 - =1，2，3, 一 (2) A=1，22，31，3 - =-(3) 厂A=C 2口 3口 0 =0(4) A=-27、设A,B,C是任意集合，证明(1)(A-B)-C=A- B C(A-B)-C=(A-C)-(B-C)证明(1) (A-B)-C=(AB) C= A (B C)= A (B _.C) =A- B _ C(A-C)-(B-C)=(AC) (B C)= (A C) (B C)=(A C B) (A C C)= (AC B) -=A (B C) =A- B C 由(1)得证。第七章部分课后习题参考答案7列出集合A=2,3,4上的恒等关系I a,全域关系Ea,小于或等于关系La,整除关系Da. 解:Ia =,E a=, La=,DA=13. 设 A=,B=,求 A - B,A B, domA, domB, dom(A - B), ranA, ranB, ran(A B ), fld(A-B). 解：A - B=,A B=domA=1,2,3domB=1,2,4dom(A V B)=1,2,3,4ran A=2,3,4ran B=2,3,4ran(A B)=4A-B=, , fld(A-B)=1,2,314. 设 R=,求 R R, R-, R 0,1,R1,2解: R R=,-1R，二,R 0,1=,R1,2=ra n( R|1,2)=2,316设A=a,b,c,d , R R?为A上的关系，其中Ra,a , a,b r b,d ；： /R2la,d,b,c , b,d；, c,b解:Ri R=,R 2R=2R 二R R=,R =R R=,32R =R QR =,36.设A=1, 2, 3, 4，在A A上定义二元关系 R,一 , A A , u,v R 二 u + y = x + v.(1)证明R是A A上的等价关系.确定由R引起的对A A的划分.(1)证明:/ R 二 u+y=x-y R 二 u-v=x-y- A A/ u-v=u-v R R是自反的任意的 , AX A 如果 R ，那么 u-v=x-y x-y=u-v RR是对称的任意的 , AX A若 R,vx,yRva,b贝U u-v=x-y,x-y=a-b u-v=a-b R R是传递的 R是AX A上的等价关系 n =, , , v1,2, , 41.设 A=1 , 2, 3, 4 , R 为 AxA 上的二元关系,V a, b, c, dAxA ,a, b Rc, d= a + b = c + d(1) 证明R为等价关系.(2) 求R导出的划分.证明：- a, b A Aa+b=a+b R R是自反的任意的 , AX A设R，贝U a+b=c+d c+d=a+b RR是对称的任意的 ,vx,y AX A若 R,R贝U a+b=c+d,c+d=x+y a+b=x+y R R是传递的 R是AXA上的等价关系 n =,v2,4, , 43.对于下列集合与整除关系画出哈斯图(1) 1,2,3,4,6,8,12,24(2) 1,2,3,4,5,6,7,8,9,10,11,12解：20#45. 下图是两个偏序集A,R- 的哈斯图.分别写出集合A和偏序关系R的集合表达式e#(a)(b)解：(a)A=a,b,c,d,e,f,gR. =va,b,va,d,va,e,va,f,va,g,vb,d,vb,e,vc,f,vc,g(b) A=a,b,c,d,e,f,gR . =,I A46. 分别画出下列各偏序集的哈斯图，并找出A的极大元 极小元 最大元和 最小元.(1) A=a,b,c,d,eR =,- I A(2) A=a,b,c,d,e, R= - IA.解：#a(1)项目(1)极大元：e极小元：a最大元：e最小元：a1* eab1ca,b,d,ea,b,c,e无无d第八章部分课后习题参考答案1.设 f :N N,且，若x为奇数f(X)=-若X为偶数2,求 f (0), f (0), f (1), f (),f (0,2,4,6,) , f (4,6,8), f-1(3,5,7). 解：f (0)=0, f (0)=0, f (1)=1, f (1)=1,f (0,2,4,6，)=N , f (4,6,8)=2,3,4, f 1 (3,5,7)=6,10,14.4. 判断下列函数中哪些是满射的？哪些是单射的？哪些是双射的？2(1) f:N N, f(x)=x +2不是满射，不是单射f:N N,f(x)=(x)mod 3,x除以3的余数不是满射，不是单射f:N N,f(x)= 1卄为奇数不是满射，不是单射o若X为偶数 f:N 0,1,f(x)=0,若x为奇数1,若x为偶数是满射，不是单射 f:N-0 R,f(x)=lgx不是满射，是单射f:R R,f(x)=x2-2x-15不是满射，不是单射215. 设 X=a,b,c,d,Y=1,2,3,f=,vc,3,判断以下命题的真假(1) f是从X到丫的二元关系，但不是从X到丫的函数； 对(2) f是从X到丫的函数,但不是满射，也不是单射的；错(3) f是从X到丫的满射,但不是单射；错f是从X到丫的双射.错第十章部分课后习题参考答案4.判断下列集合对所给的二元运算是否封闭：(1) 整数集合Z和普通的减法运算。封闭，不满足交换律和结合律，无零元和单位元(2) 非零整数集合札普通的除法运算。不封闭(3) 全体n n实矩阵集合關(R)和矩阵加法及乘法运算，其中n2。封闭 均满足交换律，结合律，乘法对加法满足分配律；加法单位元是零矩阵，无零元；乘法单位元是单位矩阵，零元是零矩阵；(4) 全体n n实可逆矩阵集合关于矩阵加法及乘法运算，其中n_2。不封闭(5) 正实数集合杖；和R运算，其中R运算定义为：beRX aDb = ab-a-b不封闭 因为1 1 =1 1 -1 -1二-V R(6) n圧絶璃：际買|狀瞎必我关于普通的加法和乘法运算。封闭，均满足交换律，结合律，乘法对加法满足分配律加法单位元是0,无零元；乘法无单位元(n 1)，零元是0； n=1单位元是1(7) A = aa2,，a.芯一运算定义如下：Vat b E A, aDb = b封闭 不满足交换律，满足结合律，(8) S =- ,!|x匕z :关于普通的加法和乘法运算。封闭 均满足交换律，结合律，乘法对加法满足分配律(9) S = 0,1,S是关于普通的加法和乘法运算。加法不封闭，乘法封闭；乘法满足交换律，结合律(10) S = I小泸；f和,S关于普通的加法和乘法运算。加法不封闭，乘法封闭，乘法满足交换律，结合律5对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。 见上题7 设*为Z 上的二元运算-x,y Z，X * Y = min ( x ，y ),即x和y之中较小的数.求 4 * 6，7 * 3。4,3(2) *在Z 上是否适合交换律，结合律，和幕等律？满足交换律，结合律，和幕等律(3) 求*运算的单位元，零元及Z 中所有可逆元素的逆元。单位元无，零元1,所有元素无逆元8. S二Q Q Q为有理数集，*为S上的二元运算，, - S有* = (1) *运算在S上是否可交换，可结合？是否为幕等的？不可交换：*va,b = = *可结合：(*vx,y)*vc,d=vax， ay + b*vc,d=vaxc，axd +(ay+b) *(vx,y*vc,d)=va, b*vxc,xd+y=vaxc，a(xd +y)+b (va,b *vx,y)*vc,d=va,b *(vx,y*vc,d)不是幕等的(2) *运算是否有单位元，零元？如果有请指出，并求S中所有可逆元素的逆元设va,b是单位元，j：vx,y (;：S ， va,b *vx,y= vx,y*va,b =vx,y贝Uvax,ay+b=vxa,xb+y=vx,y，解的 va,b=vl,0，即为单位。设va,b是零元，vx,y S ，va,b *vx,y= vx,y*va,b =va,b贝 U vax,ay+b=vxa,xb+y=va,b，无解。即无零元。_vx,y S，设va,b是它的逆元 va,b *vx,y= vx,y*va,b =vl,0 vax,ay+b=vxa,xb+y=vl,0 a=1/x,b=-y/x所以当 x = 0 时，：:x,y 1，-yx x/10令S=a, b, S上有四个运算：*，:.工口分别有表10.8确定*ababab口abaaaaababaaabbaabbabaabab(a)(b)(c)(d)(1) 这4个运算中哪些运算满足交换律，结合律，幕等律？(a) 交换律，结合律，幕等律都满足，零元为a,没有单位元；(b) 满足交换律和结合律，不满足幕等律，单位元为a,没有零元a 二二 a, b A = b(c) 满足交换律，不满足幕等律，不满足结合律a (b b) = a a=b, (a b) b = a b = aa (b b) = (a b) b没有单位元，没有零元(d) 不满足交换律，满足结合律和幕等律没有单位元，没有零元(2) 求每个运算的单位元，零元以及每一个可逆元素的逆元。见上16设V= N，+ , |其中+, |分别代表普通加法与乘法，对下面给定的每个集合 确定它是否构成V的子代数，为什么？(1) $=脚|二供嵇是(2) gmimv不是加法不封闭(3) S3 = -1 ， 0， 1不是，加法不封闭第十一章部分课后习题参考答案8.设S=0，1, 2, 3，人为模4乘法，即-x,y S, x 二 y=(xy)mod 4问S,人是否构成群？为什么？解：-x,y S, x二y=(xy)mod 4 S,二是S上的代数运算(2) - x,y,z S,设 xy=4k+r0_r_3(x i y) z =(xy)mod 4), -b z=r ； z=(rz)mod 4=(4kz+rz)mod 4=(4k+r)z)mod 4 =(xyz)mod 4同理 x (y； z) =(xyz)mod 4所以，(x . .y) . . z = x (y . . z)，结合律成立。-x S, (x 1)=(1 二 x)=x,，所以 1 是单位元。11 =1, 3=3, 0和2没有逆元所以，S,二不构成群9. 设Z为整数集合，在Z上定义二元运算。如下：-x,y Z,xoy= x+y-2问Z关于o运算能否构成群？为什么？解：(1)- x,y 乙xoy= x+y-2- Z ,o是Z上的代数运算。- x,y,z 乙(xoy) oz =(x+y_2)oz=(x+y_2)+z_2=x+y+z_4同理(xoy)oz= xo(yoz)，结合律成立。 设e是单位元，-X 乙 xo e= eox=x,即 x+e-2= e +x-2=x, e=2(4) - x Z ,设 x 的逆元是 y, xoy= yox= e,即 x+y-2=y+x-2=2,所以，x二y=4_x所以乙o构成群(1 0、1 0 ) (-1 0、(-1 0 11.设G=，证明G关于矩阵乘法构成一个群.丸1丿0 -1丿01丿0-1丿J解：(1)-x,y G,易知xy G,乘法是Z上的代数运算。(2)矩阵乘法满足结合律、1 0、设是单位兀，0 1丿(4) 每个矩阵的逆元都是自己。 所以G关于矩阵乘法构成一个群.14.设G为群，且存在a G,使得G=ak I k Z证明：G是交换群。证明：- x,y G,设 x 二 ak, y 二 a1，贝Uxy = aka1 = ak 1 = a1k = a1 ak = yx所以，G是交换群17. 设G为群，证明e为G中唯一的幕等元。证明：设e G也是幕等元，则eo eo，即 =ee，由消去律知e =e18. 设G为群，a,b,c G,证明I abc I = I bca I = I cab I证明： 先证设(abc)k =e：=(bca)k =e设(abc)k =e,贝U (abc)(abc)(abc) (abc)二 e，即 a(b c)(a)c)(i)c)a (b c)a4 =e左边同乘a 4，右边同乘a得k_1(bca)(bca)(bca) (bca) = (bac) =a ea = e反过来，设(bac)k =e,则(abc)k =e.由元素阶的定义知，I abc I = I bca I，同理I bca I = I cab I19. 证明：偶数阶群G必含2阶元。证明：设群G不含2阶元，-a，G，当a = e时，a是一阶元，当a = e时，a至少是3 阶元,因为群G时有限阶的，所以a是有限阶的，设a是k阶的,则a-1也是k阶的，所以 高于3阶的元成对出现的，G不含2阶元，G含唯一的1阶元e,这与群G是偶数阶的矛 盾。所以，偶数阶群G必含2阶元20. 设G为非Abel群，证明G中存在非单位元a和b,a工b,且ab=ba.证明：先证明G含至少含3阶元。若G只含1阶元，则G=e,G为Abel群矛盾；若G除了 1阶元e外，其余元a均为2阶元，则a2 =e , a=ata, b ：-G,a = a,b =b,(ab) =ab,所以 ab = a b = (ba) = ba ，与G为Abel群矛盾；所以，G含至少含一个3阶元，设为a，则a = a2，且a2a = aa2。令b = a2的证。21. 设G是M(R)上的加法群，n2,判断下述子集是否构成子群。(1) 全体对称矩阵是子群(2) 全体对角矩阵是子群(3) 全体行列式大于等于0的矩阵.不是子群(4) 全体上(下)三角矩阵。是子群22. 设G为群，a是G中给定元素，a的正规化子N( a)表示G中与a可交换的元素构成 的集合，即N(a) =x I x GA xa=ax证明N (a)构成G的子群。证明：ea=ae, e N (a)=x,y N (a), 贝 V ax=xa,ay = yaa(xy) = (ax)y = (xa)y = x(ay) = x(ya) = (xy)a ,所以 xy N (a)由 ax 二 xa，得 x axx二 x 4xax ,xae 二 eax，即 xa 二 ax，所以 x， N(a) 所以N (a)构成G的子群31.设 1是群G到G2的同态， 2是G到G3的同态，证明1 是G到G3的同态。 证明：有已知 1是G到G的函数， 2是 G到G的函数，贝U 2是G到G的函数。Pb G1, ( I ；)(ab)八2(】(ab)2( 1(a) (b)=(2( 1(a)( 2( i(b)( ；：2)(a)( V：2)(b)所以：申1 申2是G到G的同态。33.证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。证明：设G是循环群,令G=,-xy G ,令ak,al,那么二yx ,G是阿贝尔群x =aka ak+ = a1 + = alak克莱因四元群,G =e,a,b,c0eabceeabcaaecbbbceaccbae是交换群，但不是循环群，因为e日 疋阶兀，a,b,c是二阶元。36.设er 是5兀置换，且2345、p 23 4 5、CJ =,弋21453丿3 45 12 y(1)计算；二，匚，:匚卢v ；(3)将(2)中的置换表示成对换之积,弋=(14)(12)(15)奇置换,(2)将w, 二坊丄迈表成不交的轮换之积。2345、广12345、1广12345、TCJ =CJT =T =45321丿45123丿23451Z12345)CT TO =3)阶无向树T的最大度丄：至少为几？最多为几？解：2, n-16、若n(n 3)阶无向树T的最大度丄： =2，问T中最长的路径长度为几？解：n-17、证明：n(n2)阶无向树不是欧拉图证明：无向树没有回路，因而不是欧拉图。8、证明：n(n2)阶无向树不是哈密顿图.证明：无向树没有回路，因而不是哈密顿图。9、证明：任何无向树 T都是二部图.证明：无向树没有回路，因而不存在技术长度的圈，是二部图。10、什么样的无向树 T既是欧拉图，又是哈密顿图 ？解：一阶无向树14、 设e为无向连通图G中的一条边，e在G的任何生成树中，问e应有什么性质？ 解：e是桥15、 设e为无向连通图G中的一条边，e不在G的任何生成树中，问e应有什么性质？解：e是环23、已知n阶m条的无向图G是k(k 2)棵树组成的森林，证明：m = n-k.；证明：数学归纳法。k=1时,m = n-1，结论成立；设k=t-1(t-1 _ 1)时，结论成立，当 k=t时，无向图G是t棵树组成的森林，任取两棵树，每棵树 任取一个顶点，这两个顶点连线。则所得新图有t-1棵树，所以m = n- (k-1).所以原图中m = n-k得证。24、在图16.6所示2图中，实边所示的生成子图 T是该图的生成树.(1)指出T的弦，及每条弦对应的基本回路和对应T的基本回路系统(2)指出T的所有树枝,及每条树枝对应的基本割集和对应图 16.16T的基本割集系统(b)解: (a)T 的弦：c,d,g,hT 的基本回路系统:S=a,c,b,a,b,f,d,e,a,b,h,e,a,b,f,gT的所有树枝:e,a,b,fT 的基本割集系统:S=e,g,h,a,c,d,g,h,b,c,d,g,h,f,d,g(b)有关问题仿照给出35解:25、求图16.17所示带权图中的最小生成树536#答案不唯一。#37、画一棵权为3，4，5， 6， 7， 8，9的最优2叉树,并计算出它的权