离散数学最全课后答案(屈婉玲版)

离散数学习题解PAGE4离散数学习题解PAGE4习题一1.1．略1.2．略1.3．略1.4．略1.5．略1.6．略1.7．略1.8．略1.9．略1.10． 略1.11． 略1.12． 将下列命题符号化,真值:当且仅当3+3＝6.的充要条件是与互为充要条件.(4)若则其中,真值为其中,p:q:真值为(3)p:真值为(4)p:1.1.13． 将下列命题符号化,(1)若今天是星期一,(2)只有今天是星期一,(3)今天是星期一当且仅当明天是星期二.(4)若今天是星期一,令p:q:(1)pq(2)qp(3)(4)pr当p0时为真;p1时为假.1.14．将下列命题符号化.(1)(2)老王是山东人或河北人.(3)因为天气冷,所以我穿了羽绒服.(4)王欢与李乐组成一个小组.(5)李辛与李末是兄弟.(6)王强与刘威都学过法语.(7)他一面吃饭,一面听音乐.(8)如果天下大雨,(9)只有天下大雨,(10)除非天下大雨,(11)下雪路滑,他迟到了.(12)2与4都是素数,或4是素数,(1)pq,其中,p:刘晓月跑得快,q:(2)pq,其中,p:老王是山东人,q:(3)pq,天气冷,q:(4)p,p:(5)p,p:(6)pq,其中,p:王强学过法语,q:(7)pq,其中,p:他吃饭,q:(8)pq,天下大雨,q:他乘班车上班.(9)pq,他乘班车上班,q:(10)pq,p:他乘班车上班,q:天下大雨.(11)pq,p:下雪路滑,q:他迟到了.12)其中,p:2是素数,4是素数.(13)pq,p:2是素数,4是素数.1.15． 设p:q:求下列复合命题的真值:rp(3)pq)0.0.0.注意:p,qr1.16． 略1.17． 略1.18． 略1.19． 用真值表判断下列公式的类型:(1)p(3)r(4)(pq)((6)((pq)(7)(pq)(qp))(pq)(pq)(qq)(pq)(pq)(4)(pp)(pq)2.5.求下列公式的主析取范式,(1)(pq)(qp)(2)(pq)(1)(pq)(pq)pqqppqqpq(0,成真赋值为00,10,(2)主析取范式为0,为重言式.2.6.求下列公式的主合取范式,(1)(2)(pq)(3)(p(pq))(1)p(qp)pqppq00这是矛盾式.00,(2)M4,100.(3)主合取范式为1,为重言式.2.7.求下列公式的主析取范式,r2.8.略2.9.用真值表求下面公式的主析取范式.(2)(pq)pq(p→q)→↔q)001001011110100111111000(2)从真值表可见成真赋值为01,于是(pq)q)2.10.略2.11.略2.12.略2.13.略2.14.略2.15.用主析取范式判断下列公式是否等值:(1)(pq)r与q(2)(pq)r(pq)r(pq)rpqr(pp)pqr==而qqpr=两个公式的主吸取范式不同,所以(pq)q2.16.用主析取范式判断下列公式是否等值:r与q(2)(pq)与(pq)(1) (pq)q所以(pq)œq(2)(pq)(pq)所以(pq)œ(pq)2.17.用主合取范式判断下列公式是否等值:(pq)rr(1)p(pq)所以p(pq)r(2)p(pq)所以pœ(pq)r2.18.略2.19.略2.20.将下列公式化成与之等值且仅含}(3)注意到(pq(rpq)((pq)(r(((pq)(r(pq)))2.21.证明:(1)(pq)(qp)(pq)(qp)2.22.略2.23.略2.24.略2.25.设A,C(1)若举例说明不一定成立.(2)已知举例说明不一定成立.(1)取A=p,B=q,C=1有AC但Aœ(2)取A=p,B=q,C=0有AC但Aœ好的例子是简单,(3)一定.2.26.略2.27.某电路中有一个灯泡和三个开关A,B,C.(1)C的扳键向上,(2)A的扳键向上,B,C(3)B,C的扳键向上,A(4)A,B的扳键向上,C设F为1表示灯亮,的扳键向上.(a)求F的主析取范式.(b)在联结词完备集{,F.F.FF(b)先化简公式F(qq)((c)F2.28.一个排队线路,输入为其输出分别为若同时有两个和两个以上信号申请输出时,则按A,B,C写出}中的表达式.根据题目中的要求,先写出由真值表可先求出他们的主析取范式,2.29.略2.30.略习题三3.1.略3.2.略3.3.略3.4.略3.5.略3.6.判断下面推理是否正确.结论,出)和判断过程(至少给出两种判断方法):(1)若今天是星期一,(2)若今天是星期一,(3)若今天是星期一,(4)若今天是星期一,(5)若今天是星期一,(6)今天是星期一当且仅当明天是星期三；今天不是星期一.设p:今天是星期一,q:(1)推理的形式结构为pr即pr所以推理正确.(2)推理的形式结构为(pq)qp此形式结构不是重言式,(3)推理形式结构为此形式结构为重言式,即故推理正确.(4)推理形式结构为此形式结构不是重言式,(5)推理形式结构为p它不是重言式,故推理不正确.(6)推理形式结构为此形式结构为重言式,即故推理正确.推理是否正确,可用多种方法证明.等式演算法.下面用构造证明法证明(6)推理正确.前提:p结论:r证明:①pr ②③④p 前提引入 ⑤r 所以,3.7.略3.8.略3.9.用三种方法(真值表法,若a则a不能被2若a则a能被2如果a是偶数,则a令p:a是奇数;q:a能被2a是偶数.前提:pq,rq.结论:rp.形式结构:(pq)(rq)……P中构造下面推理的证明:(1)前提:pp,q结论:(2)前提:pq,r结论:p(3)前提:pq结论:p(4)前提:qp,tr结论:(5)前提:pq结论:(6)前提:结论:t(1)证明:①②p前提引入前提引入③④qrq①②假言推理前提引入⑤r③④假言推理⑥⑤附加律 ①②③qrr前提引入①置换前提引入④⑤⑥qpqp②③析取三段论前提引入④⑤拒取式①pq前提引入②pq①置换③(pq)②置换④p③置换⑤p④置换①②③④⑤tstrt前提引入①置换②化简前提引入④化简⑥s③⑤假言推理⑦⑧⑨⑩qsq前提引入⑦置换⑧化简⑥⑥假言推理11qp前提引入1213ppq⑩11假言推理⑩12合取①②prqs前提引入前提引入③④pqp前提引入③化简⑤q③化简⑥r①④假言推理⑦s②⑤假言推理⑧⑥⑦合取①②tpr附加前提引入前提引入③④pqp前提引入③化简⑤r②④析取三段论⑥⑤附加说明:证明中,附加提前t,没用上.P中用附加前提法证明下面各推理:(1)前提:pq结论:(2)前提:u结论:pu(1)证明:①②s附加前提引入前提引入③p①②假言推理④⑤⑥pqrq前提引入③④假言推理前提引入⑦r⑤⑥假言推理①②Ppq附加前提引入①附加③(pq)前提引入④⑤S②③假言推理④化简⑥⑦⑧uu⑤附加前提引入⑥⑦假言推理P中用归谬法证明下面推理:(1)前提:结论:p(2)前提:qs结论:(1)证明:①②P结论否定引入前提引入③④⑤⑥⑦qrr①②假言推理前提引入③④析取三段论前提引入⑥化简⑧⑤⑦合取由归谬法可知,推理正确.①结论否定引入②pq前提引入③pr前提引入④qs前提引入⑤②③④构造性二难⑥①⑤合取所以推理正确.17.P只要A11点以前没用离开,AA如果A在11点以前离开,看门人会看到他.所以A犯了谋杀罪.令p:Aq:A在11点以前离开了;A前提:pqq结论:前提:pqq结论:证明:①s 前提引入②qs 前提引入 ③q ①②拒取④p 前提引入⑤pq ③④合取⑥pqr 前提引入⑦r ⑤⑥假言推理P中构造下面推理的证明.(1)如果今天是星期六,今天是星期六.颐和园游人太多.(2)如果小王是理科学生,绩不好.(3)明天是晴天,或是雨天；若明天是晴天,如果我看书,则明天是雨天.(1)令p:q:我们要到圆明园玩;前提:psq,p,结论:①②③④①②③④⑤⑥⑦pp→q∨rq∨rss→qqr①②假言推理前提引入前提引入

p qr

s sqqr④⑤假言推理

(1)的证明树③⑥析取三段论(2)令p:q:前提:r结论:q证明:①pr前提引入②①pr前提引入②r前提引入③p①②拒取式④qp前提引入⑤q③④拒取式p rp(2)

的证明树r(3)令p:明天是晴天,q:前提: 结论:证明:①②s附加前提引入前提引入③r①②拒取式④前提引入⑤p③④拒取式⑥pq前提引入⑦q⑤⑥析取三段论习题四4.1.将下面命题用0元谓词符号化:(1)小王学过英语和法语.(2)除非李建是东北人,(1)令xx学过法语;a:符号化为或进一步细分,令xy;a:小王;英语;b2:法语.则符号化为(2)令xx怕冷;a:李建.符号化为或或进一步细分,令x是y地方人;x怕冷;a:小王;b:东北.或4.2.在一阶逻辑中将下面命题符号化,(1)凡有理数都能被2整除.(2)有的有理数能被2整除.x能被2整除,真值为0.其中,x真值为0.x能被2整除,真值为1.x为有理数,真值为1.4.3.在一阶逻辑中将下面命题符号化,(1)对于任意的x,均有2)(x2).(2)存在x,使得(1)(a)中,2)(x2)),1.22)))),x1.(2)(a)中,真值为x真值为1.4.4.在一阶逻辑中将下列命题符号化:(1)没有不能表示成分数的有理数.(2)在北京卖菜的人不全是外地人.(3)乌鸦都是黑色的.(4)有的人天天锻炼身体.没指定个体域,因而使用全总个体域.(1)x为有理数,x(2)其中,xx(3)其中,x是乌鸦,x是黑色的.(4)x是人,x4.5.在一阶逻辑中将下列命题符号化:(1)火车都比轮船快.(2)有的火车比有的汽车快.(3)不存在比所有火车都快的汽车.因为没指明个体域,(1)其中,xy比y快.(2)其中,xy比y快.(3)其中,x是汽车,y是火车,比y快.(4)x是汽车,y是火车,比y慢.4.6.略4.7.将下列各公式翻译成自然语言,®,(1)y=(2)=(1)可选的翻译:①“任意两个整数的差是整数.”②③x和使得xy=选③,以下翻译意思相同,都是错的:它是任意两个整数的差.”使得对于任意整数x和xy=这3个句子都可以符号化为y=0量词顺序不可随意调换.(2)可选的翻译:①“每个整数都有一个倒数.”②③x,y,使得=选③,4.8.指出下列公式中的指导变元,量词的辖域,y)y,z)前件x,y,是后件中,x, 整个公式中,x约束出现两次,y自由出现一次;z4.9.给定解释I如下:(a)个体域为实数集合\.=0.说明下列公式在I下的含义,并指出各公式的真值:(1)(2)(3)(4)(1)真值为(2)0.(3)1.(4)0.I如下:(a)个体域(b)D(c)D(d)D说明下列公式在I下的含义,并指出各公式的真值:(1)(2)(3)(4)(1)真值为0.(2)真值为0.(3)1.(4)1.(1)y)y)(3)(5)y)(1)p(qp)的代换实例,(3)在某些解释下为真(举例),(5)同(3).12.设I在解释I(1)y)y).(2)y)y)).(3)y)(4)y).(2),(3)(1)(2)(1)解释x为有理数,y在下:解释y整除在下:(2)(2)(3)(1)(2)(3)y)x)).习题五5.1.略5.2.设个体域(1)(2)(3)(4)(1)(F(a)(2)(F(a)(3)(F(a)(4)5.3.设个体域和使得下面公式在下都是真命题,而在下都是假命题.(1)(2)(F(1)则而x(F(x)(2)留给读者自己做.5.4.略5.5.给定解释I如下:(a)个体域试求下列公式在I下的真值:(3)(3)5.6.略5.7.略5.8.在一阶逻辑中将下列命题符号化,(1)(2)(1)令xx是正数.(2)令xy):x和y是相等的,x与y符合化为:F(y)y)F(y)y)y))y)5.9.略(1)(3)y)y);(5)x2)x2)).前束范式不是唯一的.(1)y)y))(3)y)y)y)y))y)y)y))y)y))y)y))y)y))y)y))(1)(2)(3)(4)(1)令xyy):x比yy)y))y)(2)令xyy):x比yy)y)))y)0错误的答案:y)(3)令xyy):x比yy)y)y)y)) (不是前束范式)y)(4)令xyy):x比yy)y)))y)xyy)y))y)F中构造下面推理的证明:(1)前提:结论:(2)前提:结论:(3)前提:结论:(4)前提:结论:(1)证明:①前提引入②前提引入③①②假言推理④(F(c)R(c)⑤F(c)①EI⑥F(c)⑤附加⑦⑧R(c)④⑥假言推理⑦EG(2)证明:① 前提引入② F(c)

①EI③ x(F(x)前提引入④ F(c)

⑤ ②④假言推理⑥ R(c) ⑤化简⑦ F(c)②⑥合取⑧

⑥EG(3)证明:① 前提引入② ①置换③

④ x(F(x)前提引入⑤ F(c)

⑥ F(c) ③⑤析取三段论⑦

⑥EG(4)证明:① x(F(x)前提引入② F(y)

前提引入④

⑤ xR(x) 前提引入⑥ R(y)

⑦ ④⑥析取三段论⑧ F(y) ②⑦析取三段论⑥ xF(x) F中,(1)因此有的实数是整数.(2)有理数,虚数不是实数,因此虚数既不是有理数,(3)因此有理数都不是无理数.(1)设F(x):x前提: x(F(x)结论: 证明:① 前提引入② F(c)

①EI③ F(c) ②化简④ ②化简⑤ x(F(x)前提引入⑥ F(c)

⑦ R(c) ③⑥假言推理⑧ R(c)④⑦合取⑥

⑧EG(2)设:前提: 结论: 证明:① R(x)) 前提引入② F(y)

③ 前提引入④

⑤ R(y)②置换⑥ ④⑤假言三段论⑦ ⑥置换⑧

(3)设:为无理数, 前提: 结论: 证明:① 前提引入②

③ 前提引入④

⑤ F(y)④置换⑥ ②⑤假言三段论⑦

F每个喜欢步行的人都不喜欢骑自行车.所以有的人不喜欢步行.令xxx前提:结论:①前提引入②③前提引入④⑤②④析取三段⑥前提引入⑦F(c)⑧F(c) ⑤⑦拒取⑨⑧EG习题六6.1.选择适当的谓词表示下列集合:(1)小于5的非负整数(2)奇整数集合(3)10的整倍数的集合}6.2.用列元素法表示下列集合:是十进制的数字}(1)(2)(3)(4)(5)1,1,6.3.略6.4.设F表示一年级大学生的集合,SMR专业学生的集合,T表示听离散数学课学生的集合,GH星期一晚上很迟才睡觉的学生的集合.请从备选的答案中挑出来.(1)所有计算机专业二年级的学生在学离散数学课.(2)这些且只有这些学离散数学课的学生或者星期一晚上去听音乐会的学生在星期一晚上很迟才睡觉.(3)听离散数学课的学生都没参加星期一晚上的音乐会.(4)这个音乐会只有大学一,(5)除去数学专业和计算机专业以外的二年级学生都去参加了音乐会.备选答案:⑥F∪SG(R∪M)G答案:(3)(5)⑧SG6.5.确定下列命题是否为真:(1)(2)(3)(4)(5){a,c,c}}(6){a,b}}(7){a,{{a,b}}}(8){a,b}}}(1)真(4)真(5)真(6)真(7)假6.6.略6.7.略6.8.略6.9.略习题七7.1.已知7.2.对于任意集合若BC不一定,7.3.设A,D(1)(2)对于不成立的举一反例.(1)

(x∈Ax∈B)(2)都不成立,7.4.略7.5.设A,B证明若则x,

A=B7.6.列出从集合A={1,R1=7.7.列出集合A={2,3,整除关系7.8.列出集合7.9.设A={1,R:(1)(2)(3)(4)为素数}是X上的二元关系,对于定义集合显然Ri(x)如果0,1,2,3,且令求R1(0),R2(0),R2(0)={R3(3)=A={0,R是A且0,0,3,2,0,2,1,2,3,2}给出R的关系矩阵和关系图.A=2,2,4,3,B=3,2,4,4,求A∪B,1,3,2,4,3,3,4,2}

求R○R,R10,3,1,3}0,2,0,3,1,2,1,3}

求R1,R2为A其中2 3求R1○R2,,R2.1R12R22 3试给出A上两个不同的关系R1和R2,使得R1=R1,R2=R2.7.4的(1),(1)F○任取x,y,x,y∈F○所以有F○(2)任取x,y,○F(4)任取x,y,○F7.5的(2),(2)任取y,所以有(3)F†x,y∈F†所以有F†R1和R2为A上的关系,证明:(1)(R1∪R2)

∪R21 11 1

1 1(1)(R1∪R2)1=R1

∪R2x,y∈(R1∪R2)11 1

1 1

R21 1所以(R1∪R2)

∪R21=R1

1 111 1

1 1

R2所以(R1∪R2)

1 1习题八8.1.1设f:且⎨xf(x)⎨x⎪⎩2

求f(0),f({0,2,5,7})==={0},=== f({0,===f({4,8})=f(8)}=f({1,7})={1,1}=8.2.2.设A={1,2},求f3,f7,f8,f9}f1=a,2,f2=a,2,f3=2,f4=b,2,f5=b,2,f6=2,f7=c,2,f8=c,2,f9=c,2,8.3.3.给定函数f和集合A,B如下:(1)f:(2)f:2}(3)f:x,3}(4)f:3}(5)f:B={1}(6)f:SS,(7)f:B={1/2}(8)f:对以上每一组f和A,(a)ff求f(b)求A在f下的像f(A)和B在f下的完全原像8.4.(1)f:=x2+2(2)f:=x3的余数.(3)f:f(x)⎨⎩0⎧0

(4)f:f(x)⎨(5)f:(6)f:

(1)单射,∵f(x)=x2+2∵=x2+2(3)不是单射的,∵f(0)=f(2)=不是满射的,∵

⎧0f(x)⎨

2.(5)是单射的,∵∵8.5.设X=c,d},Y=f=1,b,c,(1)f是从X到Y的二元关系,X到Y的函数;(2)f是从X到Y(3)f是从X到Y(4)f是从X到Y8.6.对于给定的A,B和f,判断fA到B的函数f:AB.f是否为单射,(1)A=®,B=f=x2+(2)A=B=_,f=1x.(3)A=B=fy)=x(4)A=B={p,q,f=q,2,3,(5)A=B=f=(6)A=B=fy)=y+x+1.(7)A=B=®,fy)=+(8)A=B=f(x)=1

x1.(9)A=B=fy,z)=x+y8.7.7.设A=b,B=(1)给出一个函数f:AB,f不是单射的也不是满射的;(2)给出一个函数f:AB,f不是单射的但是满射的;(3)能够给出一个函数f:AB,使得f==n,双射函数f:AB的条件.(1)答案不唯一.f=0,b,0,c,0,d,(2)答案不唯一.f=0,b,1,c,2,d,(3)不能.A到B不存在单射,=4>=(4)存在单射的条件是mn,存在满射的条件是mn,m=n.8.8.f,(1)f是单射的,但不是满射的;(2)f是满射的,但不是单射的.8.9.9.设A是n元集(n则从A到A从A到A的函数中双射函数和单射函数都有n!个.注:事实上,从A到A的函数中满射函数也有n!个.设f:fy)=x+y+1(1)说明f是否为单射,双射的;(2)令A=fy)=求A;(3)令B={f2,x=求B.(1)f不是单射的,∵f1)=f1)=f∵fy)>从而f(2)要使fy)=x+y+1=3,=1,1,0,2,2,0.故A=1,0,2,2,(3)B={fff=f是否为从X到Y并对f:XY(1)X=Y=f(x)=x2–x;(2)X=Y=f1(3)X=Y=f= ;x(4)X=Y=xx>f(x)=x+⎧x x1(5)X=Y=®,f=⎨⎩x1

.x1f:证明(1)ff∩f其中A,BS.(2)举出反例说明等式f(A∩B)=f(A)∩f(3)说明对于什么函数,A为非空集合,R为Ag:AA/R(1)设R为整数集合上的模n相等关系,求(2)说明g的性质(单射,双射).(3)说明在什么条件下,gS为集合,A,B是S的子集,表示T的特征函数,=1,b,1,c,d,=0,b,1,c,0,d,A={1,2,2},A2={1},求A1,A3和AA={a,b,R为A且b,a}∪IA求自然映射g:f,g,且12求f○g,f○f,g○g,f,g,且有

⎧0 h(x)⎨

求f○f,f○g,h○g,h○g○ff:\f=x2g:\g(x)=x+h:\h(x)=x(1)求g○f,(2)问g○f和f○g是否为单射,(3)f,h如果有,f,g且⎧x1⎨f(x)⎪0⎨⎩⎪x,⎩(1)求f○g

x3x4x5

⎧xg(x)⎪2⎨3⎪⎨3⎩

(2)说明f○g是否为单射,双射的.(1)这里的复合运算是右复合:=g(f当x=45的偶数时,f当x=2以及大于5的奇数时,f所以⎧x1,

x3

x1⎪⎪2 ⎪2,⎪⎪

x3g(x)⎨⎪x

x4x2或的偶数⎨⎪x

x4x2或⎪

5 ⎪,

⎩ ⎩2并且f○g:Æ(2)f不是单射的,∵f(0)=f(2)=3.f∵ranf为大于5的偶数}={0,4,5,…}=f:Æf=x,x+1.(1)说明f是否为单射和满射,为什么(2)f的反函数是否存在,求出f(3)求ranf.(1)f是单射的,若x1则f(x1)=x1,x1+f(x2)=x2,x2+1.F不是满射的,ran使得f(x)=x,x+=0,0,(2)因为f=x,x+1|f1=x+x|是从f到f=Æ的双射函数.但f1因为domf1=f(3)rann+f:®®,f=n.R,y®,x,f(x)=f(1)计算f(®).(2)确定商集®/R.f1,f4且⎧f1(x)=⎨

x0,f2(x)=f3(x)=⎨

x0,⎩否则f4(x)=1.在\上定义二元关系f(x)=f则是\上的等价关系,称为fi导出的等价关系,求商集\/Ei,i=1,2,3,4.A和B,A到B的双射函数f:(1)A={1,2,3},b,c}2)B=Æf:证明f是双射的.f:AB且f○g:AC是双射.证明:(1)f:AB(2)g:BC如果f(n)与则表示为f(n)=x,logn,n3,nlog2n3+n,2n,(logn3+log(logn)logn=n.4logn=2logn=n;2=n1/logn;22lognn2n习题九9.1.1.设9.2.由定义证明[1,9.3.3.设证明9.4.4.证明定理.5.证明定理9.3的(1),9.6.设A,D且证明9.7.9.8.A,使得9.9.根据自然数的集合定义计算:(1)3∪6, 22.A,B证明(1)A∪B(2)A×B习题十1},1},是x的倒数,12x(2)有x和y○12341○1234112342223433334444441 1(1)2 121 22(1)(2)(3)全体n×n实矩阵集合其中(4)全体n×n实可逆矩阵集合关于矩阵加法和乘法运算,(5)其中○运算定义为:(6)(7)(8)(9)S关于普通的加法和乘法运算.(1)封闭(2)不封闭(3)加法与乘法都封闭(5)不封闭(6)加法与乘法都封闭(7)封闭(10)加法不封闭,乘法封闭(1)没有交换律,没有结合律(3)加法适合交换与结合律；乘法只适合结合律；乘法对于加法有分配律.(4)乘法适合结合律(6)加法有交换,结合律；乘法有交换,(7)结合律(8)乘法有交换,结合律(9)乘法有交换,结合律 (10)乘法有交换,结合律4中封闭的二元运算找出它的单位元,(1)没有单位元,零元和可逆元素.(3)加法单位元为n阶全0n阶矩阵Mn阶单位矩阵,零元为n阶全0矩阵,可逆矩阵M(行列式不为0)有乘法逆元(4)乘法单位元为nM有乘法逆元M1.(6)加法单位元为0,没有零元,x0,当n=1时单位元为1,1有乘法逆元,就是自身.(7)没有单位元,零元与可逆元素(8)单位元为1,没有零元,1的乘法逆元是1(9)单位元为1,零元是0,1的乘法逆元是1(10)没有单位元,S上的二元运算,有(1)S上是否可交换,(2)如果有,并求S中所有可逆元素的逆元.(1)不可交换,1没有零元,当a

b, af1,…(1)(2)(3)(2)f1,f3,f6可交换,f3,f5可结合,幂等；(3)f1的单位元为没有单位元,零元与可逆元素；f3的单位元为1,零元为0,x1(x0)的逆元为x

；f4,f5,f610.10. 令S={a,S上有4个二元运算:○,i和分别由表确定.表10.8ab

ab

i ab

abaaa aab aba aabbaa bba baa bab(1)这4个运算中哪些运算满足交换律,幂等律(2)(1)(2)a；○的单位元为元,10.11. 设S=…,S构成代数系统S,?如果能构成代数系统则说(1)x与y的最大公约数.(2)x与y的最小公倍数.(3)x和y的最小整数.(4)p的个数,其中(1)构成；满足交换律,1.(2)不构成.(3)构成；单位元为1,零元为10,只有1有逆元,就是1.(4)不构成.10.12. 略10.13. 略10.14. 略10.15. 的子代数:(1)16整除}(2)8互质}(3)40的因子}(4)30的倍数}.(1)构成.(2)不构成.(3)不构成.(4)构成.10.16. 设V的子代数,(1)(2)(3)(1)是,因为对于加法和乘法封闭.(2)不是,因为对于加法不封闭.(3)不是,因为对于加法不封闭.10.17. 设x○yx和y之中较大的数.表示取x和y之中较小的数.V1和V2的所有子代数.V1的子代数为数.习题十一其中运算表为○f2f3f4f2f3f4f2f3f4f4f3f2f4f4f4f4i2=G关于复数加法构成群.复数加法在G易见该运算封闭,任取整数○z==x○==结合律成立.单位元为X的逆元为11.10. 设A上定义六个函数如下:1, 1令F为这6个函数构成的集合,(1)(2)○f2f3f4f5f6f2f3f4f5f6f2f2f4f3f6f5(1)f3f3f5f6f2f4f4f4f6f2f5f3f5f5f3f6f4f2f6f6f4f5f2f3(2)易见封闭性满足,f1,1 1 1

1 1f1

=

11.11. 略11.12. 略11.13. 略11.14. 设G为群,且存在证明G是交换群.任取aiaj===ajai 11.15. 略11.16. 设G为群,若x∈G有G为交换群.任取G中元素a,b,由于a,b为二阶元,从而11.17. 设G为群,证明e为G中唯一的幂等元.设a为幂等元,那么aa=a,由消去律得a=e.11.18. 略11.19. *证明4阶群必含2阶元.设G为4阶群,若G中含有4阶元a,那么是2阶元；若G中不含4阶元,G阶只能是2或1,而G不是平凡群,2阶元.11.20. *设G是非阿贝尔群,证明G中存在元素a和ab=ba.先证G中必含3阶或3阶以上的元素.假设G中只有1阶或2阶元,那么G中任意元素a都有7题的结果,G为Abel群,与已知矛盾.设a为Gb=a1,则有11.21. 略11.22. 略11.23. 11.设H是群G证明xHx1是G的子群,称为H的共轭子群.e是xHx1中的元素,因此非空.任取因为H为子群,hk1属于x(hk1)x1xHx1.11.24. 略11.25. 证明定理6. *设G , , ,⎛10⎞⎛1 0⎞⎛10⎞⎛1G , , ,⎟⎜ ⎟⎜ ⎟⎜ ⎟⎬⎝01⎠⎝0

1⎠⎝0 1⎠⎝0

1⎠⎭(1)G上的二元运算为矩阵乘法,给出G的运算表(2)试找出G的所有子群(3)证明G的所有子群都是正规子群.将G中矩阵依次记为A,B, A B

BAA A BB B A

BAABBBAA

A A BB B AG是Abel群,11.27. 略11.28. 略11.29. 令411.30. 对以下各小题给定的群和以及f是否为群到的同态.Gkerf.(1)⎧1f:⎨⎩1

(2)f:(3)Af:2®.11.31. 略11.32. 到是到的同构.1为到的双射函数.任取中的元素中元素a,b(a)=x,(a)(b))=1((ab))=ab=1(x)1为同构.11.33. 略11.34. 设为循环群,是群到的同态,证明设G1=a,x,存在x==(a))i这证明了(a)为11.35. 设G=a是15阶循环群.(1)求出G的所有的生成元.(2)求出G的所有子群.(1)生成元:(2)子群:a,G11.36. 5⎛12345⎞ ⎛12345⎞⎜ ⎟,

⎜ ⎟⎝21453⎠ ⎝34512⎠(1)(2)(3)⎛12⎛12345⎞⎜⎝43125⎟,⎠⎛12345⎞⎜⎝45321⎟⎠⎛12345⎞⎜21534⎟⎛12345⎞⎜45123⎟(1)

⎝ ⎠⎝ ⎠⎜54132⎟⎛⎜54132⎟⎝ ⎠(2)(3)

141213141215131512141311.37. *证明群中运算满足消去律任取G中元素即同理可证右消去律的成立.11.38. *设G是有限群,K是G的子群,H是K由拉格朗日定理有代入得

再根据拉格朗日定理有比较两个等式,习题十二=A设R1,R2R1与R2的直积R1×R2也是环.(2)若R1和R2为交换环和含幺环,证明也是交换环和含幺环.(1)i2=(2)(3)阶整数矩阵的集合,(4)A12.1(3)习题十三13.1. 1.图13.9中给出6如果不是格,d f fd ec d c eb bb ca a a(b) gf ff d ed e d ec b cb c a b aa(d) (f)图13.9(a),(1)L=(2)L=(3)L={1,2,3,4,(4)L=n®+(1)不是格,(2)画出3元对称群S3的子群格.见答图.S33

26

4

0

(1)

(2)第3题答图L是格,求以下公式的对偶式:(1)aa(2)a™(3)b™(1)“a(2)a“(3)b“aS上可交换,若a,b是S证明算的幂等元.证ab=bc(ab)(ab)=((ab)a)b=(a(ab))b=((aa)b)b=(aa)(bb)=ab.L是格,a,且a™b™证明

ab=bcab=b;bc=b.13.4中的格和求出他们的所有子格.d d1 d1b cb2a a1 a2L1 L2 L3图13.10的子格:{a},{b},c,的子格:的子格:c2},{a2,c2,任取令证明S,™的子格.

S=|S非空.y有x™y™a,从而xy™x™a,xy™aa=a™a,于是xyS,xyS,即S对运算,是封闭的.因此是L,的子格.13.9中的每个格,(b),(a)a与d互补;c(c)a与f互补;b的补元为c,d;c的补元为b,d的补元为b,e的补元为d.(f)a与f互补;b的补元为e;c和d没有补元;e的补元为b.13.10. 10.说明图13.9中的每个格是否为分配格,并说明理由.(b),(a)是分配格,c(c)不是分配格,不是布尔格,a与fb和ec,d;d的补元有b,e.(f)是分配格,5元子格与钻石格或五角格同构;因为c和d没有补元.13.11. 11.证明定理13.12. 独异点,域,布尔代数),(1)S1=1,(2)S2=ai,ajS2,=n是给定的正整数,且(3)S3=1},(4)S4=2,(5)S5=1},*为模2加法,○为模2乘法.(1)不是代数系统,(2)是半群但不是独异点,没有单位元.(3)是独异点但不是群,单位元是1,0没有逆元.(4)是布尔代数.因为这两个运算满足交换,1,元是6),(5)是域.1}关于模3加构成交换群,3乘构成交换群,模3乘关于模3加有分配律.13.13. 13.设B是布尔代数,Bf是(ab)bc)(bc)(1)化简f.(2)求f的对偶式f*.(1)(ab)=(2)f*=13.14. 14.13.15. 15.对于n=n元格,并说明哪些是分配格,(b) (d) (f) (g) (h) (i) (j)第15题答图布尔格:(e)分配格:(c),(d),(h) 有补格:(e),(i),(j)13.16. ,,0,在ByB有=(xy)构成群,任取a,b,c(ab)c((ab)(ab))c((ab)(ab))c((a(ac(abc)(abc)((ab)(ac(abc)(abc)(ab)(ac(abc)(abc)(aac)(abc)ac)bc)(abc)(abc)0(abc)(abc)0(abc)ca)(cab)(abc)同理有

ac)c)aca)(cab)(abc)ca)易见结合律成立.由a0(a(a(a1)0a,知0为单位元.由aa(aa)(aa)000,知a为本身的逆元.13.17. 17.13.18. 18.习题十四P2881,2,3,4,5,11,16,17),36~47),49~50)给定下面的图(前两个为无向图,=V1,E1,V1=v2,v4,E1=v4),(v3,v3),v5)};=V2,E2,V2=E2={(v1,(v3,=V3,E3,V3=E3=v2,v2,v3,v2,v4,v5,v5,=V4,E4,V4=E4=v2,v2,v5,v2,v3,v4,v4,

第1题答图先将图14.17中各图的顶点标定顺序,

图14.17(a)图=V1,其中,V1=v2,v3,v4,=(v2,(v3,v4)};(b)图=V2,其中V2=V1,E2=v2),v5),v4)};(c)图=V3,其中V3=v2,v3,v4,v5,E3=v5,v2,v1,v2,v2,v3,v2,v4,v3,v4,v5,写出图14.17中各图的度数列,解的度数列d=(3,2,2,1).(b)图的度数列d=(3,2,1,2).(c)图的度数列d=(2,4,3,3,0);出度列d+=(1,2,2,入度列d=2,1,2,.(1)写出图v1的邻域(2)写出图14.18(b)中顶点中u1的先驱元集(u1),后继元集邻域u2

u1 u3u4 u5(b)图14.18(a)顶点v1的邻域N(v1)={v2,=(b)中顶点中u1的先驱元集(u1)={u3,={u2,邻域=(u1)∪={u2,u3,u4},=N(u1)∪{u1}={u1,u3,14.5. 14.5设无向图G有10条边,34度顶点各2个,3,问G写出G的度数列,解设有x个2度顶点.2m==2·3++解得x3.G至少有2+2+3=7个顶点,2,3,4,而=4,=4.6(1)设n阶图G中有m条边,证明:(2)n(1)设=nd)i又

(1)nd)n(2)i由(1),(2)设G=V,是n令V1是G的一个连通分支的顶点集,k=(1),V2=VV1.注意V2==nk1.V1的顶点与V2的顶点之间没有G的边(?),而G的边关联的顶点都是V1的顶点或者都是V2的顶点,即E=∪要使G的边数最大,有k(k1)/2条边和(nk)(nk1)/2条边,而G有|E|=k(k1)/2+(nk)(nk1)/2条边.下面证明当k=1(或n1)时,⎜22⎟|E|=+(nk)(nk1)/2=⎛kn⎞⎜22⎟⎝ ⎠

n22n4

,1kn1.k要离n/2尽可能远.当k=1或n1时,1)(n2)/2. 边数最多的n阶不连通的简单图由1和K1有(n1)(n2)/2条边. 边数最少的n阶不连通的简单图显然是n阶零图边数为0.QEI另解:nKn的边数最多,有n(n1)/2条边,要破坏的连通性,点的(n1)条边,所得图由1和一个孤立点(K1)构成,=1的边数=(n1)(n2)/2条边.n阶非连通的简单图的边数最多的情况.已知一有向图D的度数列为(2,3,2,求D的入度列,入度列d=dd+=3,3)(1,2,1)=1,1,==2,=2,最小出度=1,=2,=1.6条边,3度与5度顶点各一个,2度顶点,该图有4个顶点.2,1个.同构意义下,1个,如答图(a)所示;非简单图有5个,其中无环的1个(图(b)),13个(图(c),(d),31个(图(f)).

(b) (d) (f)第9题答图14.10. 10.设9阶图G中,5就是6,证明G中至少有5个6度顶点或至少有6个5度顶点.用反证法.5个6度顶点6个5度顶点”4个6度顶点至多有5个5度顶点”4个6度顶点有5个5度顶点”(否则顶点数9).14.11. 11.反证法.若存在某个具有奇数个面,V.V有r(r为奇数)个面,设为R2,Rr,分别为它们的棱数,作无向图G如下:在V的每个面中放一个顶点vi,i=2,Ri与Rj有公共面就连边.则d(vi)均为奇数由握手定理得r rd)d(vi)==为边数)i

i但因=故不存在这样的无向图从而也不存在满足要求的多面体.用反证法.若存在这样的多面体S,S的面,相应的顶点之间连一条边,严格地,令G=V,E,其中V=是S的面},E={(u,vVu与vuv}.又vV,d(v)为v的棱数,GG是不存在的,G的多面体S也是不存在的.14.12. 12.设G是n(n是它的补图.=k1,=k2,和中)的每个顶点v,有+(v)=n1,或(v)=(n1)=(n1)=(n1)而=(n1)=(n1)k1.14.13. 13.2的6解2,2.图G由若干连通分支组成,1个顶点,B1;若含2个顶点,若含k3个顶点,必是k点圈连通分支的图样完全由它的点数所确定.B1 图G分解为连通分支,元集)的划分.找出正整数6的划分:6少个满足条件的不同构的图种!顶点度数都是2的无向图由其阶数n的划分确定:1+1+1+1+1+1=1+1+1+1+2=1+1+1+3=1+1+2+2=1+1+4=1+2+3=1+5=2+2+2=2+4=3+3=6有11个划分.不同构的每个顶点度数都是2的6阶无向图有11个,其中两个是简单图.14.14. 14.3种非同构的无向图,(1)(2,3,4,4,5);(2)(2,2,3,3,4,(1)不可图化,个)奇度顶点.(2)可图化,d=2,2,3,4,4)2,1,2,0)2,1,1,0)0,1,0,答图中给出8个非同构的图例,第14题答图14.15. 15.(1)(2,3,5,6,6);(2)(1,2,3,3,5,5);(3)(2,2,3,3);14.16. 16.的所有非同构的子图,指出哪些是生成子图,14.17. 17.画出3阶有向完全图的所有非同构的子图,3阶竞赛图14.18. 18.现有3个4阶4条边的无向简单图在同构意义下,4阶4条边的无向简单图都是的生成子图,而的4度数列分别为1,3和2,2.由鸽巢原理可知,14.19. 19.设G是n阶自补图,证明n=4k或n=其中k设G是n阶m条边的自补图,则G为n阶m条边的简单图,且的边数=且=2m=于是=因而n=或=k为正整数.14.20. 20.已知n阶无向完全图G有m条边,的补图的边数.==n(n1)/214.21. 21.无向图G如图14.19所示.(1)求G的全部点割集和边割集,(2)求Gab d e c图14.19(1)点割集两个{a,{d},d7{e2,(2)因为既有割点又有桥,==14.22. 22.无向图G如图14.20所示,现将该图顶点和边标定.连通度和边连通度.图14.20

图14.21标定如答图.3个割点:d,f,h.3个桥:e9,==a e f i

b d hc g第22题答图14.23. 23.求图14.21所示图G=2,==14.24. 24.设与均为无向简单图,分别为与⎯G2的补图.G2当且仅当⎯G114.25. 25.画5阶3条边的所有非同构的无向简单图.所要画的是简单图,⎧d1d2d3d4d5⎨⎩ 0di正整数6分成5个小于4的非负整数的划分有:6=0+0+0+2+4=0+0+0+3+3=0+0+1+1+4=0+0+1+2+3=0+0+2+2+2=0+1+1+1+3=0+1+1+2+2=1+1+1+1+2得8个数列.其中,0,1,2,因为假如有以这些数列为度数列的简单图的话,从中删去2个或3个孤立点,得3阶或2阶的简单图,大度应不超过2或1,但这些数列的最大数是3或4.下面考察剩下的4个数列:①②(0,1,1,2,③经尝试,(a) (b) (c) (d)第25题答图14.26. 26.画出5阶7条边的所有非同构的无向简单图.5阶7条边的无向简单图的补图是5阶3条边的无向简单图.利用第25题结果,画得4个满足条件的图,见第25题答图红虚线所示.14.27. 27.6阶由第13题的结果知,6阶6的圈和两个长度为3的圈,两个6阶2-正则图或两个6阶2-正则图14.28. 28.设n阶无向图为3-正则图,且边数m与n满足=问这样的无向图有几种非同构的情由握手定理,3n=但2n3=解得n=m=9.设G是满足条件的图,是6阶2-正则图,不同构的有2个(第27题结果).而设均为无向简单图,2.只有两种非同构的情况,两个6阶3-正则图14.29. 29.设G是n阶n+1证明G中存在顶点v,用反证法.若G的最大度则按握手定理2m其中m是边数.从而mn,14.30. 30.设e=G中的一条边,证明:e为G中桥当且仅当e不在G的任何圈中.14.31. 31.设G的边数分别为和试确定G的阶数.14.32. 32..14.33. 33.设e=G中桥,证明:u(或u(或v)不是悬挂顶点.14.34. 34.证明:nG中至少有两个顶点不是割点.令u和v是图G中有最大距离的两个点.又假定v是一个割点.则有一个点w,它与u在G–v的不同的连通分支中.从而v在G的每一条联结u和w的通路上,所以w)>而这与u和v之间距离的最大性假设矛盾.所以v,类似地不是割点.u wv14.35. 35.设G是n阶无向简单图,n3且为奇数,G中奇度顶点的个数相等.==V(Kn)(v)+==n1为偶数(n为奇数)于是,若(v)为奇数,与G中奇度顶点个数相等.14.36. 36.无向完全图中有几种非同构的偶圈,其中14.37. 37.n其中14.38. 38.n14.39. 39.若无向图G种恰有两个奇度顶点,14.40. 40.u,v种的任意两个不同的顶点,问du,14.41. 41.设G设无向简单图,证明G种存在长度大于或等于(G)+1的圈.14.42. 42.设D=V,证明D中存在长度大于或等于+(G)}+1的圈.14.43. 43.有向图D如图14.22所示.(1)D(2)求a到d的短程线和距离d.(3)求d到a的短程线和距离a.(4)判断D是哪类连通图.(5)对D的基图讨论(1),14.44. 44.有向图D如图14.23所示.(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次幂解此题.0⎥⎢A201001⎥21⎢0⎥0⎥⎢A201001⎥21⎢0⎥A⎢0⎢1

10⎥, ⎥0⎥⎢ ⎥⎢0010⎥

1001⎣ ⎦ ⎣ ⎦2⎥⎢A4⎢222221⎥⎢443⎢12⎥⎢A4⎢222221⎥⎢443⎢1⎥

10⎥, ⎥2⎥⎢ ⎥ ⎢ ⎥210⎦ ⎣2221⎦(1)v1到v4长度为1,2,3,40条,0条,2条,2条;(2)v1到v11,2,3,41条,1条,3条,5条;(3)D中长度为4的通路(不含回路)共33条,长度为4的回路共11条;(4)D中长度小于或等于4的通路共88条,其中22条是回路;(5)因为D是强联通图,4阶全1阵.14.45. 45.有向图D如图14.24所示.求:(1)v2到v51,2,3,4(2)v5到v51,2,3,4(3)D中长度为4的通路数.(4)D中长度小于或等于4的回路数.(5)写出D的可达矩阵.14.46. 46.设4阶有向图,已知D的邻接矩阵为⎡0210⎤⎢0010⎥A⎢ ⎥⎢0001⎥⎣ ⎦⎢001⎣ ⎦试求D中各顶点的入度与出度.14.47. 47.无向图E,v3,e4,⎡21110⎤110001110001M(G)⎢ ⎥.⎣ ⎦⎢0 ⎣ ⎦试在同构意义下画出G的图形.

⎢00001⎥14.48. 48.s中,2rssss解r=1时,1的圈.当2rs时,有长度为4,6,…,2r的圈,它们都是偶圈,因而非同构的圈共有r1种.(2)至多有(3)至多有s}条边彼此不相邻.(4)==14.49. 49.设G设n阶m条边的无向连通图,证明mn50.设G是6阶无向简单图,G中存在3个顶点彼此相邻.习题十五P303 全部1~22题15.11(a) (b) (c) (d)图15.11也因为它有奇度顶点.(1)完全图Kn(n(2)n(n(3)完全二部图Kr,s均为非0正偶数)都是欧拉图.(1)错误,(n3)每个顶点度数都是n1,要使它成为成为偶数,要求n为奇数.所以完全图只在n为奇数时才是欧拉图.(2)正确.由定理15.3知命题为真.(3)正确.sr就是因此都是偶度顶点,且Kr,s(1)偶数个顶点,偶数条边.(2)奇数个顶点,奇数条边.(3)偶数个顶点,奇数条边.(4)奇数个顶点,偶数条边.见答图.(1) (2) (3) (4)第3题答图使它具有:(1)偶数个顶点,偶数条边.(2)奇数个顶点,奇数条边.(3)偶数个顶点,奇数条边.(4)奇数个顶点,偶数条边.见答图.(1) (2) (3) (4)第4题答图在k3的圈(全为无向的或全为有向的)之间至少加多少条新边(有向的加有至少加2k条边.设k个圈为…,在上取顶点,记为vi,i=k.在vi和之间加平行边(vi,i=则G连通,因而G为欧拉图.至少加k条边.把k个相互分离的连通图连成一个连通图至少要加k1条边.设k…,在记为vi,i=1,…,k.在vi和之间加边(vi,i=2,…,k1.这样加了k1条边后把k个相互分离的圈连成一个连通图,且vi4(偶数),i=2,…,k1,而v1和vk的度数变成3(奇数),再在vk和v1之使它们的度数变成4,k条边.则G连通,数,因而G为欧拉图.添加少于k条边不能达到目的.证明:D是欧拉图,则D是强连通的.因为D为欧拉图,设C为其中的一条欧拉回路.任取则vj均在C上.vi可达vj,并且vj可达vi,所以D是强连通的.设G是恰含2k(k证明G中存在k使k得=∪E(i).i对k进行归纳.k=1时,15.2知G由欧拉通路,是其中一条.边.=假设G有2k(k1)个奇度顶点时命题为真.当G有2(k+1)个奇度顶点时,设u,v是G的两个奇度顶点,令=G∪(u,v),则有2k(k1)个奇度顶点(u,v在k条边不重的k…,使得=∪E(i).(s=1,2,…,于是(u,v)得i到G中两条满足要求的的简单通路.将G中(k+…,则k=∪E(i).i完全图(n完全图(n1)中,除了K2不是哈密顿图外,其余的都是哈密顿图.平凡图是哈密顿图.证明:(例15.4)(1)证明有割点的无向连通图G不是哈密顿图.设v为G中的一个割点,G中一个割集,则2>=1由定理15.6可知,G(2)再证有桥的图不是哈密顿图.连通有桥图的最小阶数n=2,即而K2不是哈密顿图.n3的有桥图,中,证二若G是哈密顿图,则G中有哈密顿回路,设为C.v=Cv因此Gv是连通的.因此G没有割点.e若则Ge有连通的生成子图C,因此是连通的.若则Ge仍有连通的生成子图Ce,G没有桥.15.10. 10证明定理15.8.定理15.8设u,v为n阶无向图简单图G中两个不相邻的顶点,且d(u)+n,则G为哈密顿图G∪(u,():显然.():设C是=G∪(u,(1)若新边(u,C上,则C是G中的哈密顿回路.(2)若新边(u,C上,则=C(u,v)是G中的哈密顿通路.①若u,v在G中相邻,则∪(u,v)是Gv)).②若u,v在G中不相邻,则k=d(u)2(否则d(u)+d(v)1+2)<n).v2外有(k1)个点与u相邻:…,v1)个点左边相邻的点vi21,vik1(否则+d(v)k+[(n2)(k1)]n1).设vir1与v相邻,则是G中一条哈密顿回路.v1=u

vn=vivi=…15.11. 11.彼得松图是10阶3正则图,要想消除所有奇度顶点,5条边,使它变成每个顶点都是4度顶点的连通的简单图或非简单图,事实上,密顿通路的两端点之间加一条新边就得到哈密顿图,(b) (c)第11题答图15.12. 12.证明图中(a)图不是哈密顿图,(b)图15.12首先确认一个简单的命题:若G有哈密顿回路,则G的所有2度顶点所关联的2条边(环除外)必须在G的任一条哈密顿回路上.它有3个2度顶点共关联6条边,这6条边均在任何哈密顿回路上,于是在哈密顿回路(初级回路)上就会出现一个顶点v(图中位于中间的顶点),33条边),努力找到(b)中图的一条哈密顿回路,(a) (b)第12题答图15.13. 13.今有2k(kk项任务.2k1k个人中的任何人组成小组(每组2个人)去完成他们共同熟悉的任务,问这2k个人能否分成k组(每组2人),每组完成设V=E=uv且u,v能合作}得2k阶无向简单图由已知条件,vV,d(u)+d(v)由定理15.7的推论可知,G为哈密顿图.于是存在哈密顿回路.设C=回路,在C中相邻的顶点都能合作.k组.15.14. 14.今有n个人,n2个人.证明:当n3时,这n个人能排成一列,n4时,这n个人能排成一个圆圈,作n阶简单无向图G=V,V=这n个人的集合,E={(u,vVuvu与v认识}.u,v(1)若u,v相邻,则d(u)+d(v)2)+2=n.(2)若u,v则wV{u,w必与u和v都相邻.比如u和w不相邻,则v,w都不邻接u,于是u和w合起来至多与其余的n3个人认识,因而+d(v)2(n2).当n3时,2(n2)n1,因此无论第(1)或(2)种情形,都有+d(v)n1,由定理15.7知G中有哈密顿通路,当n4时,2(n2)n,因此无论第(1)或(2)种情形,都有d(u)+d(v)n,15.7的推论知G中有哈密顿回路,圆圈,15.15. 15.6种不同颜色的纱织成的双色布.5中颜色中的3种相搭配.3种双色布,他们恰由6种不同颜色的纱织成.作无向简单图G=V,E,V=为6种颜色的纱之一},=6,E={(u,vVuvu与v能搭配}.vV,有d(u)+d(v)3+3=6=由定理15.7的推论知,G设C=为其中的一条.任何两个顶点在C中相邻,让vi1与的搭配,与的搭配,与的搭配就可以织成3种双色布,恰用了6种不同的颜色.15.16. 16.设完全图(n3)的顶点分别为v1,v2,…,问Kn中有多少条不同的哈密顿回路(这里认为,若在回路中,与是不同的回路).构造Kn中的哈密顿回路如下:依次选取中第1个顶点(有n种方法),第2个顶点(有n1种方法),…,第n1个顶点(有2种方法),第n个(最后一个)顶点(有1种选法);从第1个顶点出发,沿中的边到相继的顶点,直到第n个顶点,然后从第n个顶点沿中的边回到第1个顶点.n!条中的哈密顿回路.如果不区分第1个顶点或说起点(也就是不区分第n个顶点或说终点),中不同的哈密顿回路有n!/n=(n1)!条.15.17. 17.设完全图(n3)是带权图(各边的权均大于或等于0).Kn可以使用穷举法.中共有(n1)!/2条不同哈密顿回路.15.18. 18.准备假期骑自行车到景点B,C,D去旅游,图15.13给出了D的位置及它们之间的距离(公里).B1113 7 16A C6D图15.13这是n=4的货郎担问题.有(n1)!/2=3权分别为32,46,其中,长度是32公里.15.19. 19.15.14所示,a5 63e b12 7 6 88 4d 9 c图15.14这里使用穷举法.中(Kn带权)共有(n1)!/2条不同哈密顿回路.当n=5时,共有4!/2=12条.列出12条不同的哈密顿回路,权,15.14中图的最短哈密顿回路,它们的权都是32.a a5 63e b e12 7 6 8 128 4

5 63b7 6 88 4d 9 c

d 9 c(b)第19题答图215.20. 20.设G为n阶无向简单图,m=1(n1)(n2)+2,证明G是哈密顿图.m2=12(n1)(n2)+1时,G=1首先证明G中任何两个不相邻的顶点的度数之和n.用反证法.否则存在u,且d(u)+d(v)n1.令V'={u,=G则1(n1)(n2)+2(n1),1(n2)(n3)+1.2)阶无向简单图的边数2 22最多为1(n2)(n3),矛盾.于是,d(u)+n.2由定理15.7的推论可知,G2在答图中,n=5,m=m1(51)(52)+1=2第20题答图15.21. 21.设G=V,V1V,且V1均有p(GV1)则G是哈密顿图.不成立.例如K2和彼得松图都满足给定条件,但都不是哈密顿图.15.22. 22.设G是n(n3)阶无向简单哈密顿图,vi,vj,d(u)+d(v)n.不成立.例如5阶圈图是哈密顿图,习题十六P319画出所有5阶和7阶非同构的无向树.顶点度数之和

d=2m=1dn1.i=1i i(1)5阶树:1+1+d3+d4+d5=8=2+6=①1+1+2+2+2=+1+1+2+3+1+1+1+4.上列每一种划分对应一个树.画得5阶非同构的无向树有3棵:① ② ③第1题答图(2)7阶树:1+1+d3+…+d7=12=(2+10)=①1+1+2+2+2+2+2=②1+1+1+2+2+2+3=③1+1+1+1+2+3+3=④1+1+1+1+2+2+4=⑤1+1+1+1+1+3+4=⑥1+1+1+1+1+2+5=⑦1+1+1+1+1+1+上列正整数12的7个划分的每一个对应着一个可能的7阶树的度数列.可以先忽略2度顶点,画出7种不“同胚”的树;然后再插入所忽略的2度顶点,得12个不同构的7阶树,见答图,是同胚的.①②③④⑤ ⑥ ⑦11棵7阶无向树,不同胚的有7种第2题答图一棵无向树T有5片树叶,3个2度分支点,3度顶点,问T利用树的性质及握手定理:m=2m=2n2=+32+(n8)3.得T的顶点数n=11.无向树T有8片树叶,2个3度分支点,4度顶点,问T有几个4根据T的度数列,设T有x个4度顶点.++=2(8+2+x1)解得x=2.每个树把树叶都删除后所得的图也是树,它的顶点是原树的分枝点.树T的分枝点有4个,而不同构的4阶树有2个,如果区分其中的3度顶点和4度顶点的话有6种不同构的情形;6个不同构的无向树,3度 4度6个非同构树 第3题答图一棵无向树T有(i=2,3,…,k)个i问Tk k k k阶数n=+t,t为树叶数.则m=+t2m=2+2=ini+解得ti2

i2

i2

i2k k=(i+2=(i+QEIi2

i3n(nTT的最大度不能是1,否则T的顶点都是树叶,而度数之和=n2m=2(n1).而n阶路径图Pn是树,其最大度是2.所以T的最大度至少是2.另一方面,因为是简单图,T的最大度不能超过n1;而n阶星形图=n1是树,n1.所以T的最大度最多为n1.n(nT的最大度(T)=问T=则T的度数列是1,1,2,…,T必然是路径图,其最长的路径长度为n1.证明:n(n因为n(n2)阶无向树T至少有两片树叶,所以T不是欧拉图.证明:n(n非平凡树树没有回路,所以不是哈密顿图.证明:T都是二部图.任何树均无回路,16.10. 10.什么样的树T只有平凡树才既是欧拉图又是哈密顿图.16.11. 11.无向树T非平凡树T至少有两片树叶,要成为半欧拉图,T必须恰含两片树叶(奇度顶点).设T的度数列是1,1,k k nd3,则di2=由握手定理,di+2=2(n得di2)=或(di=但i3

i3

i3di2=n),于是必然有di=2(i=n).因此T必然是路径图Pn.答:当且仅当T是路径图时T为半欧拉图.16.12. 12.无向树T若T是半哈密顿图,则T中有哈密顿通路,n个顶点(T所有的顶点),(n这必然是T所有的边(因为T有(n所有当且仅当T是路径图时,T是半哈密顿图.16.13. 若能,请画出3棵非同构的无向树.(1)1,1,1,1,2,3,4(2)1,1,1,1,2,2,3(1)不能.n=8,m=7.=16(2)能,见下图.(2)1,1,1,1,2,2,35个非同构树.

3度 2度第13题答图注:2度顶点,2度顶点.16.14. 14.设eG中的一条边,e在G的任何生成树中,问ee具有这样的性质:e在G的任何生成树中e是G的桥.()(反证法)假如e不是桥,则Ge因而有生成树而T也是G的生成树,e.()(反证法)若G的某棵生成树T不含e,则Ge有生成树而这与e16.15. 15.设eG中的一条边,e不在G的任何生成树中,问ee具有这样的性质:e不在G的任何生成树中e是G的环.()(反证法)G是连通的,设T是其中一棵.e不是环,则e关联两个不同的顶点.若T不含e,则T∪eC,圈长2且含e.删去该圈上某一边得G的生成树T∪e它含e.()(反证法)若G的某棵生成树T含e,则T中有圈(每个环是一个圈,1).16.16. 16.设eG中的一条边,e证明存在G的生成树含e作为树枝,又存在G的生成树,以e为弦由第14题和第15题结论立刻得到.证二由于e不是桥,因而e又因为e所以e用破圈法(即有圈就删除圈上的一条边)构造G的生成树.e.树含e.②先把e删去,破掉e所在的圈,e.16.17. 17.设T为无向图G的生成树,⎯T是T的