離散數(shù)學(xué)答案屈婉玲版第二版高等教育出版社課后答案第一章部分課后習(xí)題參考答案16設(shè)p、q的真值為0；r、s的真值為1，求下列各命題公式的真值。（1）p∨(q∧r)0∨(0∧1)0（2）（p?r）∧(﹁q∨s)（0?1）∧(1∨1)0∧10.（3）（p∧q∧r）?(p∧q∧﹁（1∧1∧1）?(0∧0∧0)0(4)（r∧s）→(p∧q)（0∧1）→(1∧0)0→0117．判斷下面一段論述是否為真：“是無(wú)理數(shù)。并且，如果3是無(wú)理數(shù)，則也是無(wú)理數(shù)。另外6能被2整除，6才能被4整除?！贝穑簆:是無(wú)理數(shù)q:13是無(wú)理數(shù)0r:是無(wú)理數(shù)1s:6能被2整除1t:640命題符號(hào)化為：p∧(q→r)∧(t→s)的真值為1，所以這一段的論述為真。19．用真值表判斷下列公式的類型：（4）(p→q)→(q→p)（5）(p∧r)(p∧q)（6）((p→q)∧(q→r))答： （4）p q p→qqpq→p q→p)0 0 1 1 1 110 1 1 0 1 111 0 0 1 0 011 1 1 0 0 11所以公式類型為永真式公式類型為可滿足式（方法如上例）公式類型為永真式（方法如上例第二章部分課后習(xí)題參考答案表法求出成真賦值.(1)(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)(p∨(p∨q))∨(p∨r)p∨p∨q∨r1所以公式類型為永真式(3)P q r p∨q p∧r （p∨q）→(p∧r)0 0 0 0 010 0 1 0 010 1 0 1 000 1 1 1 001 0 0 1 001 0 1 1 111 1 0 1 001 1 1 1 11所以公式類型為可滿足式用等值演算法證明下面等值式：(2)(p→q)∧(p→r)(p→(q∧r))(4)(p∧q)∨(p∧q)(p∨q)∧(p∧q)證明（2）(p→q)∧(p→r)(p∨q)∧(p∨r)p∨(q∧r))p→(q∧r)（4）(p∧q)∨(p∧q)(p∨(p∧q))q∨(p∧q)(p∨p)∧(p∨q)∧(q∨p)∧(q∨q)1∧(p∨q)∧(p∧q)∧1(p∨q)∧(p∧q)(1)(p→q)→(q∨p)(2)(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：（1）主析取范式(p→q)→(qp)(pq)(qp)(pq)(qp)(pq)(qp)(qp)(pq)(pq)(pq)(pq)(pq)∑(0,2,3)主合取范式：(p→q)→(qp)(pq)(qp)(pq)(qp)(p(qp))(q(qp))1(pq)(pq)M1∏(1)(2)主合取范式為：(p→q)qr(pq)qr(pq)qr0所以該式為矛盾式.主合取范式為∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式為0(3)主合取范式為：(p(qr))→(pqr)(p(qr))→(pqr)(p(qr))(pqr)(p(pqr))((qr))(pqr))111所以該式為永真式.永真式的主合取范式為1主析取范式為∑(0,1,2,3,4,5,6,7)第三章部分課后習(xí)題參考答案14.P(2)前提：pq,(qr),r結(jié)論：p(4)前提：qp,qs,st,tr結(jié)論：pq證明：（2）①(qr) 前提引入②qr ①置換③qr ②蘊(yùn)含等值式④r 前提引入⑤q ③④拒取式⑥p前提引入⑦￢p（3） 證明（4）：①t前提引入②t ①化簡(jiǎn)律③q前提引入④s前提引入⑤qt ③④等價(jià)三段論⑥（qt）(t⑤置換⑦（qt） ⑥化簡(jiǎn)⑧q ②⑥假言推理⑨q前提引入⑩p ⑧⑨假言推理(11)p⑧⑩合取P(1)前提：p(qr),sp,q結(jié)論：sr證明①s 附加前提引入②sp 前提引入③p ①②假言推理④p(q前提引入⑤qr ③④假言推理⑥q 前提引入⑦r ⑤⑥假言推理P(1)前提：pq,rq,rs結(jié)論：p證明：①p②p﹁q 前提引③﹁q④￢rq 前提引入⑤￢r⑥r(nóng)￢s

結(jié)論的否定引入①②假言推理④化簡(jiǎn)律⑦r ⑥化簡(jiǎn)律⑧r﹁r ⑤⑦合取由于最后一步r﹁r是矛盾式,所以推理正確.第四章部分課后習(xí)題參考答案在一階邏輯中將下面將下面命題符號(hào)化,并分別討論個(gè)體域限制為條件時(shí)命題的真值:x,均有2=(x+)(x).x,x+5=9.其中(a)個(gè)體域?yàn)樽匀粩?shù)集合.(b)個(gè)體域?yàn)閷?shí)數(shù)集合.解：F(x):2=(x+)(x).G(x):x+5=9.在兩個(gè)個(gè)體域中都解釋為，在（a）中為假命題，在(b)中為真命題。在兩個(gè)個(gè)體域中都解釋為，在（a）(b)中均為真命題。在一階邏輯中將下列命題符號(hào)化:沒(méi)有不能表示成分?jǐn)?shù)的有理數(shù).解:F(x):xH(x):x命題符號(hào)化為:F(x):xH(x):x命題符號(hào)化為:在一階邏輯將下列命題符號(hào)化:(1)火車都比輪船快.(3)不存在比所有火車都快的汽車.解:F(x):xG(x):xH(x,y):xy命題符號(hào)化為:(1)F(x):xG(x):xH(x,y):xy命題符號(hào)化為:IDR.D=0.特定函數(shù)(x,y)=xy,x,y.特定謂詞(x,y):x=y,(x,y):x<y,x,y.I(1)(2)答:(1)對(duì)于任意兩個(gè)實(shí)數(shù)x,y,如果x<y,那么xy. 1.(2)對(duì)于任意兩個(gè)實(shí)數(shù)x,y,如果x-y=0,那么x<y.真值0.ID=N(ND=2.D=x+y,(x,y)=xy.D(x,y):x=y.I(1)xF(g(x,a),x)(2)xy(F(f(x,a),y)→F(f(y,a),x)答:(1)對(duì)于任意自然數(shù)x,都有2x=x, 真值0.x,y,x+2=y,y+2=x.0.判斷下列各式的類型:(1)(3)yF(x,y).解:(1)因?yàn)闉橛勒媸?；所以為永真式；IF(x,y)：x+y=5xyx+y=5，xyx+y=5，此時(shí)為假命題IF(x,y)：:x+y=5xyx+y=5，前件假。此時(shí)為假命題。此公式為非永真式的可滿足式。13. (1)(F(x)(2)x(F(x)G(x)H(x))解:(1)個(gè)體域:本班同學(xué)F(x)：x會(huì)吃飯,G(x)：x會(huì)睡覺(jué).成真解釋F(x)：x,G(x)：x.（2）(2)個(gè)體域:泰ft學(xué)院的學(xué)生F(x)：xft東,G(x):x,H(x):xF(x)：x,G(x)：x,H(x)：x第五章部分課后習(xí)題參考答案5.給定解釋Ｉ如下:(a)(b)為(c).(1)(3)解:(1)(2)(1)(5)(本題課本上有錯(cuò)誤)解:(1)(5)15.在自然數(shù)推理系統(tǒng)F中,構(gòu)造下面推理的證明:前提:,結(jié)論:xR(x)前提:x(F(x)→(G(a)∧R(x))),xF(x)結(jié)論:x(F(x)∧R(x))證明(1)①前提引入②F(c) ①EI③前提引入④①③假言推理⑤(F(c)∨G(c))→R(c)) ④UI⑥F(c)∨G(c) ②附加⑦R(c) ⑤⑥假言推理⑧xR(x) ⑦EG(2)①xF(x) 前提引入②F(c) ①EI③x(F(x)→(G(a)∧R(x)))④F(c)→(G(a)∧R(c))前提引入③UI⑤G(a)∧R(c)⑥R(c)⑦F(c)∧R(c)⑧②④假言推理⑤化簡(jiǎn)②⑥合取引入x(F(x)∧R(x)) ⑦EG第六章部分課后習(xí)題參考答案5.確定下列命題是否為真：（1）真（2）假（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）｛｛a,b｝，c,｝ =｛｛a,b｝,c｝ 假（2）｛a,b,a｝=｛a,b｝ 真（3）｛｛a｝，｝=｛｛a,b｝｝ 假（4）｛，｛｝，a,b｝=｛｛,｛｝｝,a,b｝假8．求下列集合的冪集：（1）｛a,b,c｝ P(A)={,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}（2）｛1，｛2，3｝｝P(A)={,{1}, {{2,3}}, {1，{2，3}}}（3）｛｝ P(A)={,｛｝}（4）｛，｛｝｝ P(A)={,{1}, {{2,3}}, {1，{2，3}}}14．化簡(jiǎn)下列集合表達(dá)式：（1）（AB）BB）（2）（（ABC）-（BC））A解:(1)（AB）BB）=（AB）B）～（AB）=（AB）～（AB）)B=B=（2）（（ABC）-（BC））A=（（ABC）～（BC））A=（A～（BC））（（BC）～（BC））A=（A～（BC））A=（A～（BC））A=A18．2514，12，626會(huì)打籃球或排球。求不會(huì)打球的人數(shù)。解:阿A={會(huì)打籃球的人}，B={會(huì)打排球的人}，C={會(huì)打網(wǎng)球的人}|A|=14,|B|=12,|AB|=6,|AC|=5,|BC|=2,AB如圖所示。25-(5+4+2+3)-5-1=25-14-5-1=5不會(huì)打球的人共5人21.設(shè)集合A＝{{1，2}，{2，3}，{1，3},{}},計(jì)算下列表達(dá)式：（1）A（2）A（3）A（4）A解:（1）A={1，2}{2，3}{1，3}{}={1，2，3,}（2）A={1，2}{2，3}{1，3}{}=（3）A=123=（4）A=27、設(shè)A,B,C是任意集合，證明(1)(A-B)-C=A-BC(2)(A-B)-C=(A-C)-(B-C)證明(1)(A-B)-C=(A～B)～C=A(～B～C)=A～(BC)=A-BC(2)(A-C)-(B-C)=(A～C)～(B～C)=(A～C)(～BC)=(A～C～B)(A～CC)=～C～B)=A～(BC)=A-BC 由（1）得證。第七章部分課后習(xí)題參考答案7.A={2,3,4}IA,EA,LA,DA.解：IA={<2，2>,<3,3>,<4,4>}EA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>}LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}DA={<2,4>}13.設(shè)A={<1,2>,<2,4>,<3,3>}B={<1,3>,<2,4>,<4,2>}求AB,AB,domA,domB,dom(AB),ranA,ranB,ran(AB),fld(A-B).解：AB={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}AB={<2,4>}domA={1,2,3}domB={1,2,4}dom(A∨B)={1,2,3,4}ranA={2,3,4}ranB={2,3,4}ran(AB)={4}A-B={<1,2>,<3,3>}，fld(A-B)={1,2,3}14.設(shè)R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>}求RR, R-1, R{0,1,}, R[{1,2}]解：RR={<0,2>,<0,3>,<1,3>}R-1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}R{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>}R[{1,2}]=ran(R|{1,2})={2,3}16．設(shè)A={a,b,c,d}，，為A上的關(guān)系，其中=求。解:R1R2={<a,d>,<a,c>,<a,d>}R2R1={<c,d>}R12=R1R1={<a,a>,<a,b>,<a,d>}R22=R2R2={<b,b>,<c,c>,<c,d>}R23=R2R22={<b,c>,<c,b>,<b,d>}36．A={1，2，3，4}，AR，<u,v>,<x,y>AA，〈u,v>R<x,y>u+y=x+v.RARA（1）證明u+y=x-y∴<u,v>R<x,y>u-v=x-y<u,v>AA∵u-v=u-v∴<u,v>R<u,v>∴R是自反的任意的<u,v>,<x,y>∈A×A如果<u,v>R<x,y>，那么u-v=x-y∴x-y=u-v ∴<x,y>R<u,v>∴R是對(duì)稱的任意的<u,v>,<x,y>,<a,b>∈A×A若<u,v>R<x,y>,<x,y>R<a,b>則u-v=x-y,x-y=a-b∴u-v=a-b ∴<u,v>R<a,b>∴R是傳遞的∴RA×A(2)∏={{<1,1>,<2,2>,<3,3>,<4,4>}, {<2,1>,<3,2>,<4,3>}, {<3,1>,<4,2>},{<4,1>}, {<1,2>,<2,3>,<3,4>}, {<1,3>,<2,4>}, {<1,4>} }41.A={1，2，3，4}，RA〈a，b〉，〈c，d〉A(chǔ)A,〈a，b〉R〈c，d〉a+b=c+dRR(1)證明：<a，b〉A(chǔ)Aa+b=a+b∴<a,b>R<a,b>∴R是自反的任意的<a,b>,<c,d>∈A×A設(shè)<a,b>R<c,d>，則a+b=c+d∴c+d=a+b ∴<c,d>R<a,b>∴R是對(duì)稱的任意的<a,b>,<c,d>,<x,y>∈A×A若<a,b>R<c,d>,<c,d>R<x,y>則a+b=c+d,c+d=x+y∴a+b=x+y ∴<a,b>R<x,y>∴R是傳遞的∴R是A×A上的等價(jià)關(guān)系(2)∏={{<1,1>},{<1,2>,<2,1>},{<1,3>,<2,2>,<3,1>},{<1,4>,<4,1>,<2,3>,<3,2>},{<2,4>,<4,2>,<3,3>}, {<3,4>,<4,3>}, {<4,4>}}43.對(duì)于下列集合與整除關(guān)系畫出哈斯圖:(1){1,2,3,4,6,8,12,24}(2){1,2,3,4,5,6,7,8,9,10,11,12}解:(1)下圖是兩個(gè)偏序集<A,RA的集合表達(dá)式.(a)解:(a)A={a,b,c,d,e,f,g}

(2)(b)R={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<a,g>,<b,d>,<b,e>,<c,f>,<c,g>}(b)A={a,b,c,d,e,f,g}R={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<d,f>,<e,f>}分別畫出下列各偏序集<A,RA`極小元`(1)A={a,b,c,d,e}R={<a,d>,<a,c>,<a,b>,<a,e>,<b,e>,<c,e>,<d,e>}IA.(2)A={a,b,c,d,e}, R={<c,d>}IA.解:(1)(2)項(xiàng)目(1)(2)極大元:ea,b,d,e極小元:aa,b,c,e最大元:e無(wú)最小元:a無(wú)第八章部分課后習(xí)題參考答案1．設(shè)f:NN,且f(x)=求f(0),f({0}),f(1),f({1}),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.判斷下列函數(shù)中哪些是滿射的?哪些是單射的?哪些是雙射的?f:NN,f(x)=x2+2 不是滿射，不是單射f:NN,f(x)=(x)mod3,x除以3的余數(shù) 不是滿射，不是單射N,f(x)=不是滿射，不是單射f:N{0,1},f(x)=是滿射，不是單射(5)f:N-{0}R,f(x)=lgx 不是滿射，是單射(6)f:RR,f(x)=x2-2x-15 不是滿射，不是單射5.設(shè)X={a,b,c,d},Y={1,2,3},f={<a,1>,<b,2>,<c,3>,}判斷以下命題的真假:(1)f是從X到Y(jié)的二元關(guān)系,但不是從X到Y(jié)的函數(shù); 對(duì)(2)f是從X到Y(jié)的函數(shù),但不是滿射,也不是單射的; f是從X到Y(jié)的滿射,但不是單射; 錯(cuò)fXY射. 錯(cuò)第十章部分課后習(xí)題參考答案4．Z封閉,不滿足交換律和結(jié)合律，無(wú)零元和單位元非零整數(shù)集合普通的除法運(yùn)算。不封閉實(shí)矩陣集合（R）和矩陣加法及乘法運(yùn)算，其中n2。封閉均滿足交換律，結(jié)合律，乘法對(duì)加法滿足分配律；加法單位元是零矩陣，無(wú)零元；乘法單位元是單位矩陣，零元是零矩陣；全體實(shí)可逆矩陣集合關(guān)于矩陣加法及乘法運(yùn)算，其中n2。不封閉正實(shí)數(shù)集合和運(yùn)算，其中運(yùn)算定義為：不封閉 因?yàn)椋?）關(guān)于普通的加法和乘法運(yùn)算。封閉，均滿足交換律，結(jié)合律，乘法對(duì)加法滿足分配律加法單位元是0，無(wú)零元；乘法無(wú)單位元（），1（7）A={n運(yùn)算定義如下：封閉不滿足交換律，滿足結(jié)合律，（8）S=關(guān)于普通的加法和乘法運(yùn)算。封閉 均滿足交換律，結(jié)合律，乘法對(duì)加法滿足分配律（9）S={0,1},S加法不封閉，乘法封閉；乘法滿足交換律，結(jié)合律（10）S=,S關(guān)于普通的加法和乘法運(yùn)算。加法不封閉，乘法封閉，乘法滿足交換律，結(jié)合律5．見(jiàn)上題7．設(shè)*為上的二元運(yùn)算，X*Y=min(x，yxy(1)4*6，7*3。4, 3(2)*在上是否適合交換律，結(jié)合律，和冪等律？滿足交換律，結(jié)合律，和冪等律(3)求*運(yùn)算的單位元，零元及中所有可逆元素的逆元。單位元無(wú)，零元1, 所有元素?zé)o逆元8．為有理數(shù)集，*為S上的二元運(yùn)算，<a,b>,<x,y>S有<a，b>*<x，y>=<ax，ay+b>*S不可交換：<x,y>*<a,b>=<xa，xb+y><a，b>*<x，y>可結(jié)合：(<a,b>*<x,y>)*<c,d>=<ax，ay+b>*<c,d>=<axc，axd+(ay+b)><a,b>*(<x,y>*<c,d>)=<a,b>*<xc,xd+y>=<axc，a(xd+y)+b>(<a,b>*<x,y>)*<c,d>=<a,b>*(<x,y>*<c,d>)不是冪等的*S逆元。設(shè)<a,b>是單位元，<x,y>S，<a,b>*<x,y>=<x,y>*<a,b>=<x,y>則<ax,ay+b>=<xa,xb+y>=<x,y>，解的<a,b>=<1,0>，即為單位。設(shè)<a,b>是零元，<x,y>S，<a,b>*<x,y>=<x,y>*<a,b>=<a,b>則<ax,ay+b>=<xa,xb+y>=<a,b>，無(wú)解。即無(wú)零元。<x,y>S，設(shè)<a,b>是它的逆元<a,b>*<x,y>=<x,y>*<a,b>=<1,0><ax,ay+b>=<xa,xb+y>=<1,0>a=1/x,b=-y/x010．令S={a，b}，S上有四個(gè)運(yùn)算：*，分別有表10.8確定。(a) (b)(d)4(a)a,(b)a,滿足交換律,不滿足冪等律,不滿足結(jié)合律沒(méi)有單位元,沒(méi)有零元不滿足交換律，滿足結(jié)合律和冪等律

(c)沒(méi)有單位元,沒(méi)有零元見(jiàn)上16．設(shè)V=〈N，+，〉，其中+，V什么？（1）S1=是（2）S2=不是加法不封閉（3）S3={-1，0，1} 第十一章部分課后習(xí)題參考答案8.4"x,y∈S, xy=(xy)mod4問(wèn)〈S，〉是否構(gòu)成群？為什么？解x,y∈S, xy=(xy)mod4,是S上的代數(shù)運(yùn)算。(2)x,y,z∈S,設(shè)xy=4k+r(xy)z=((xy)modz=rz=(rz)mod4=(4kz+rz)mod4=((4k+r)z)mod4=(xyz)modx(yz)=(xyz)mod4所以，(xy)z=(yz)，結(jié)合律成立。(3)x∈S,(x1)=(1x)=x1(4)2所以，〈S，〉不構(gòu)成群9.ZZ"x,y∈Z,xoy=x+y-2Zo解：(1)x,y∈Z, xoy=x+y-2,oZ(2)x,y,z∈Z,(xoy)oz=(x+y-2)oz=(x+y-2)+z-2=x+y+z-4同理(xoy)oz=xo(yoz)，結(jié)合律成立。(3)設(shè)是單位元，x∈Z,xo=ox=x,即x+-2=+x-2=x, e=2(4)x∈Z,設(shè)x的逆元是y,xoy=yox=x+y-2=y+x-2=2,所以，所以〈Z，o〉構(gòu)成群11.設(shè)G=G解：(1)x,y∈G, xy∈G,Z(2)矩陣乘法滿足結(jié)合律(3)設(shè)是單位元，(4)每個(gè)矩陣的逆元都是自己。G14.Ga∈G,使得G={ak∣k∈Z}證明：G是交換群。證明:x,y∈G，設(shè)，則所以，G是交換群GeG證明:設(shè)也是冪等元，則，即，由消去律知G，a,b,c∈G,證明∣abc∣=∣bca∣=∣cab∣證明：先證設(shè)設(shè)則，即左邊同乘，右邊同乘得反過(guò)來(lái)，設(shè)則由元素階的定義知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣19.證明：偶數(shù)階群G必含2階元。證明：設(shè)群G不含2階元，時(shí)，3G是有限階的，設(shè)是k階的,則也是k階的，所以高于3階的元成對(duì)出現(xiàn)的，G不含2階元，G含唯一的1階元,這與群G是偶數(shù)階的矛盾。所以，偶數(shù)階群G必含2階元GAbelGab,a≠b,G3G1G={e},GAbelG1e均為2階元，則，，GAbel所以，G含至少含一個(gè)3階元，設(shè)為，則，且。令的證。GMn(R)上的加法群，n≥2，判斷下述子集是否構(gòu)成子群。全體對(duì)稱矩陣 是子群全體對(duì)角矩陣 是子群0全體上（下）三角矩陣。 是子群G，aG，aN（a）Ga的元素構(gòu)成的集合，即N（a）={x∣x∈G∧xa=ax}N（a）G證明：ea=ae,,所以由，得，即，所以N（a）G31.設(shè)G1G2G2G312G1G3證明：有已知G1G2G2G31·2G1G3所以:1·2G1G333.證明循環(huán)群一定是阿貝爾群，說(shuō)明阿貝爾群是否一定為循環(huán)群，并證明你的結(jié)論。證明：設(shè)G是循環(huán)群,令G=<a>,,令,那么,G是阿貝爾群克萊因四元群,是交換群,但不是循環(huán)群,因?yàn)閑是一階元，a,b,c是二階元。36.設(shè)是5元置換，且，計(jì)算；將表成不交的輪換之積。將（2）中的置換表示成對(duì)換之積，并說(shuō)明哪些為奇置換，哪些為偶置換。解：(1)(2)(3)奇置換，偶置換奇置換第十四章部分課后習(xí)題參考答案5G10，3423，問(wèn)G至少有多少個(gè)頂點(diǎn)？在最少頂點(diǎn)的情況下，寫出度數(shù)列、。解：由握手定理圖G的度數(shù)之和為：3度與4度頂點(diǎn)各2個(gè)，這4個(gè)頂點(diǎn)的度數(shù)之和為14度。其余頂點(diǎn)的度數(shù)共有6度。3，G所以，G73,3,4,4,2,2,2,.7D2，3，2，3，1，2，1，1，D列，并求，,.解：D2，3，2，3，1，2，1，1，D1,1,1,2.,,86，3512該圖有多少個(gè)頂點(diǎn)？解：由握手定理圖G的度數(shù)之和為：設(shè)2度點(diǎn)個(gè)，則，，該圖有4個(gè)頂點(diǎn).14、下面給出的兩個(gè)正整數(shù)數(shù)列中哪個(gè)是可圖化的？對(duì)可圖化的數(shù)列，試給出3種非同構(gòu)的無(wú)向圖，其中至少有兩個(gè)時(shí)簡(jiǎn)單圖。(1)2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4解：(1)2+2+3+3+4+4+5=23 是奇數(shù)，不可圖化；(2) 2＋2+2+2+3+3+4+4=16,是偶數(shù)，可圖化；18344G1、G2、G3，同構(gòu)的。證明：443，8，因而2，2，2，2；3，2，2，1；3，3，1，13，3，1，1單圖。所以從同構(gòu)的觀點(diǎn)看，44所以，G1、G2、G3至少有兩個(gè)是同構(gòu)的。20nGmG的邊數(shù)。解：21、無(wú)向圖G如下圖GG與邊連通度。解：點(diǎn)割集:{a,b},(d)邊割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}==123、求G的點(diǎn)連通度、邊連通度與最小度數(shù)。解：、、28n3-mn2n-3=m向圖有幾種非同構(gòu)的情況？解：得n=6,m=9.31G的邊數(shù)分別為和G解：得45D(1)求到1，2，3，4(2)求到長(zhǎng)度為1，2，3，4的回路數(shù)；D4D4(5)D解：有向圖D的鄰接矩陣為：，(1)到1，2，3，40,2,0,0；(2)到1，2，3，40,0,4,0；(3)D432；(4)D4(4)D第十六章部分課后習(xí)題參考答案1、畫出所有5階