試題總匯數(shù)理邏輯部分1、判斷下列句子中哪些是命題（1）2是素數(shù)（2）血是黑色的（3）2+3=5（4）明年10月1日是晴天（5）3能被2整除（6）這朵花多好看呀?。?）明天下午有會嗎？（8）請關上門?。?）X + y > 5（10）地球外的星球上也有人2、將下列命題符號化（1）3不是偶數(shù)（2）2是素數(shù)和偶數(shù)（3）李芳學過英語或日語（4）如果角A和角B是對頂角，則角A等于角B（5）李平雖然聰明，但不用功（6）李平不但聰明，而且用功（7）小王是游泳冠軍或者百米賽跑冠軍（8）小王現(xiàn)在在宿舍或者在圖書館（9）選小王或者小李中的一人當班長（10）如果我上街，我就去書店看看，除非我很累（11）如果明天天氣好，我們去郊游。否則，不去郊游（12）你愛我，我就嫁給你3、判斷下列命題公式是否等值（1）（pq）與pq（2）（pq）與pq4、驗證下列等值式（1）p（qr）（ pq）r（2）p（ pq）（pq）5、用等值演算法解決下面問題：A、B、C、D 4人百米競賽。觀眾甲、乙、丙預報比賽的名次為，（1）甲：C第一，B第二。（2）乙：C第二，D第三。（3）丙：A第二，D第四。比賽結束后發(fā)現(xiàn)甲、乙、丙每人報告的情況都是給對一半。試問，實際名次如何？6、求下面命題公式的主析取范式和主合取范式（1）（pq）r）p7、利用真值表求主析取范式和主合取范式（1）（pq）r8、邏輯推理證明（1）前提：pr，qs，pq。結論：rs。（2）前提：pq，pr，st，sr，t。結論：q（3）前提：p（qr），sp，q。結論：sr。（4）前提：p（rs）q），p，s。結論：q9、給定語句如下：（1）15是素數(shù)（2）10能被2整除，3是偶數(shù)（3）你下午有會嗎？（4）2x+3> 0（5）2是素數(shù)或是合數(shù)（6）這個男孩真勇敢呀?。?）如果2+2=6，則5是奇數(shù)（8）只有4是偶數(shù)，3才能被2整除（9）明年5月1日是晴天（10）圓的面積等于半徑的平方與的乘積以上10個語句中，是簡單命題的為A，是復合命題的為B，是真命題的為C，是假命題的為D，真值待定（真值客觀存在，只是現(xiàn)在不知道）的命題為E。A：（1）、（4）、（8）（4）、（6）、（9）、（10）（1）、（9）、（10）B：（3）、（10）（2）、（5）、（7）、（8）（7）、（8）C：（2）、（5）、（9）、（10）（7）、（8）、（10）（2）、（9）、（10）（5）、（7）、（8）、（10）D：（1）、（2）、（8）（1）、（2）（1）、（5）E：（4）、（9）（9）（7）、（8）10、判斷公式類型（1）（pq）（pq）（2）（pq）（pq）（qp）（3）（pq）q（4）（pp）q（5）p（pq）（6）（pp）（qq）r）（7）（pq）p）p（8）（pq）（pq）（9）（pq r）（p qr）（10）（pq）r11、給定命題公式如下：（pq）（pq）該命題公式的主析取范式中含極小項的個數(shù)為A，主合取范式中含極大項的個數(shù)為B，成真賦值個數(shù)為C，成假賦值個數(shù)為D。A、B、C、D：（1）0,（2）1,(3)2,(4)3,(5)412、一公安人員審查一件盜竊案，已知的事實如下：（1）甲或乙盜竊了錄音機（2）若甲盜竊了錄音機，則作案時間不能發(fā)生在午夜前（3）若乙的證詞正確，則午夜時屋里燈光未滅（4）若乙的證詞不正確，則作案時間發(fā)生在午夜前（5）午夜時屋里燈光滅了推理證明，誰盜竊了錄音機。13、設p=1，q=0，r=1，s=0，有下列命題公式（1）（pq）（sr）（2）（pqrs）(sq)（3）（pqr）（ps）那么，（1）的真值為 ；（2）的真值為 ；（3）的真值為 ；14、對于下面的語句，（1）只要43，就有32（2）只要43，就有32（3）只有43，才有32（4）只有43，才有32（5）除非43，否則32（6）43僅當32（7）43當且僅當32則，他們的真值是（1） （2） （3） （4） （5） （6） （7） 。15、設A是含n個命題變項的公式，下面4個結論中，哪個是錯誤的？（1）若A的主析取范式中含2n 個極小項，則A是重言式（2）若A的主合取范式中含2n 個極大項，則A是矛盾式（3）若A的主析取范式中不含任何極小項，則A的主析取范式為0（4）若A的主合取范式中不含任何極大項，則A的主合取范式為016、已知命題公式A含有3個命題變項，其成真賦值為000，010，100，110。則A的主析取范式為 ，主合取范式為 。17、判斷下列語句是否為命題，如是命題請指出是簡單命題還是復合命題，并討論真值（1）是無理數(shù)（2）5能被2整除（3）現(xiàn)在開會嗎？（4）x+50（5）這朵花真好看呀?。?）2是素數(shù)當且僅當三角形有3條邊（7）血是黑色的當且僅當太陽從東方升起（8）2008年10月1日天氣晴朗（9）太陽系以外的星球上有生物（10）小李在宿舍里（11）全體起立（12）4是2的倍數(shù)或是3的倍數(shù)（13）4是偶數(shù)且是奇數(shù)（14）李明與王華是同學（15）藍色和黃色可以調配成綠色18、將下列命題符號化，并討論其真值（1）如果今天是1號，則明天是2號（2）如果今天是1號，則明天是3號19、設A、B、C為任意的命題公式（1）已知 ACBC，問AB嗎？（2）已知 ACBC，問AB嗎？（3）已知 A B，問AB嗎？20、設計一個符合如下要求的室內照明控制線路：在房間的門外、門內及床頭分別裝有控制同一個電燈F的3個開關A、B、C。當且僅當一個開關的鍵向上或3個開關的鍵都向上時電燈亮。則F的邏輯關系式可化簡為 。（1）ABC （2）ABC（ABC） （3）AB（AC）（4）C（AB）21、將下列語句用謂詞表達式符號化（1）2是素數(shù)且是偶數(shù)（2）如果2大于3，則2大于4（3）凡是有理數(shù)均可表成分數(shù)（4）有的有理數(shù)是整數(shù)（5）沒有不吃飯的人（6）素數(shù)不全是奇數(shù)（7）一切人都不一樣高（8）有的自然數(shù)無先驅數(shù)（9）有些人喜歡所有的花（10）任何金屬都可以溶解在某種液體中（11）凡是對頂角都相等22、指出下列各合式公式中的指導變項、量詞的轄域、個體變項的自由出現(xiàn)和約束出現(xiàn)（1）x（F（x）yH（x，y）（2）x F（x）G（x，y）（3）xy（R（x，y）L（x，y）x H（x，y）23、給定解釋I如下：1）DI=2，32）DI中特定元素a=23）函數(shù)f（x）為f（2）=3，f（3）=24）謂詞F（x）為F（2）=0，F(xiàn)（3）=1； G（x，y）為G（ i，j）=1，i，j=2，3； L（x，y）為L（ 2，2）= L（ 3，3）=1；L（ 2，3）= L（ 3，2）=0在解釋I下，求下列各式的值。（1）x（F（x）G（x，a）（2）x（F（f（x）G（x，f（x）（3）xy L（x，y）24、求下列公式的前束范式（1）xF（x）x G（x）（2）xF（x）x G（x）（3）xF（x）x G（x）（4）xF（x）x G（x）25、設F（x）：x是人，G（x）：x愛吃糖。有人給出語句“不是所有人都愛吃糖”的4種謂詞表達式：（1）x（F（x）G（x）（2）x（F（x）G（x）（3）x（F（x）G（x）（4）x（F（x）G（x）正確的答案是 。26、給出解釋I，使下面兩個公式在解釋I下均為假，從而說明這兩個公式都不是永真式（1）x（F（x）G（x）（xF（x）x G（x）（2）（xF（x）x G（x）x（F（x）G（x）27、取個體域為整數(shù)集，給定下列公式（1）xy（x*y=0）（2）xy（x*y=1）（3）yx（x*y=2）（4）xy z（x y = z）（5）x y = - y + x（6）xy（x *y = y）（7）x（x*y = x）（8）xy（x + y = 2y）在上面的公式中，真命題的為A，假命題的為B。A：（1）、（3）、（4）、（6）；（3）、（4）、（5）； （1）、（3）、（4）、（5）；（3）、（4）、（6）、（7）B：（2）、（3）、（6）；（2）、（6）、（8）； （1）、（2）、（6）、（7）；（2）、（6）、（8）、（7）集合部分1、下列命題（1）；（2）；（3）；（4）正確的是 ；錯誤的是 。2、計算一下冪集（1）P（）；（2）P（）；（3）P（，）；（4）P（1，2，3）3、證明（1）（A-B）B=AB；4、化簡 （ABC）（AB）- （A（B - C）A5、已知：AB=AC，證明：A = B6、求在1到1000之間不能被5和6，也不能被8整除的數(shù)的個數(shù)7、某班有25個學生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2人會打這三種球。而6個會打網(wǎng)球的人都會打另一種球（指籃球或排球），求不會打這三種球的人數(shù)。8、設F表示一年級大學生的集合，S表示二年級大學生的集合，R表示計算機科學系學生的集合，M表示數(shù)學系學生的集合，T表示選修離散數(shù)學的學生的集合，L表示愛好文學的學生的集合，P表示愛好體育運動的學生的集合，則下列各句子所對應的集合表達式分別是：（1）所有計算機科學系二年級的學生都選修離散數(shù)學。A（2）數(shù)學系的學生或者愛好文學或者愛好體育運動。B（3）數(shù)學系一年級的學生都沒有選修離散數(shù)學。C（4）只有一、二年級的學生才愛好體育運動。D（5）除去數(shù)學系和計算機科學系二年級的學生外都不選修離散數(shù)學。EA、B、C、D、E：T（MR）S；RST；（MF）T =；MLP；PFS；S -（MR）P9、設S1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，S5=3，5。確定在以下條件下X可能與S1,S5中哪個集合相等。（1）若XS5 = ，則A（2）若XS4但XS2 = ，則B（3）若XS1但XS3，則C（4）若X - S3= ，則D（5）若XS3但XS1，則EA、B、C、D、E：X=S2或者S3；X= S4或者S5；X=S1，S2或者S4；X與其中任何集合都不等；X=S2；X=S5；X=S3或者S5；X=S2或者S4；10、設A、B、C為任意集合，判斷下述命題是否恒真，如果恒真給出證明，否則舉出反例。（1）AB=ACB=C（2）AB=AB=（3）A（B - C）=（AB）-（AC）（4）（AB）（B - A）= B11、設A、B為集合，試確定下列各式成立的充分必要條件：（1）A B = B（2）A B = B - A（3）AB = AB12、求使得以下集合等式成立時，a，b，c，d應該滿足的條件：（1）a，b=a，b，c（2）a，b，a=a，b（3）a，b，c=a，d（4）a，b，c=b（5）a，b，c=13、計算AB、AB、A - B、AB（1）A=a，b，c，B=c，d（2）A=a，b，c，c，a，b，B=a，b，c，b（3）A=x|xNx<3，B=x|xNx2（4）A=x|xRx<1，B=x|xZx<1（5）A=x|xZx<0，B=x|xZx214、設|A|=3，|P（A）|=64，|P（AB）|=256，求：|B|，|AB|，|A - B|，|AB|15、設A=1，2，求：P（A）A16、設A、B、C、D為任意集合，判斷以下等式是否成立，若成立給與證明，否則，舉出反例。（1）（AB）（CD）=（AC）（BD）（2）（AB）（CD）=（AC）（BD）（3）（A - B）（C - D）=（A - C）（B - D）（4）（AB）（CD）=（AC）（BD）17、設F、G是N上的關系，其定義為：F=<x，y>|x，yNy =x2；G=<x，y>|x，yNy =x+1；求：G-1、FG、GF、F1，2、F1，218、設F=<a，a>，<a，a，a>，求：FF，F(xiàn)a，F(xiàn)a。19、設A=a，b，c，d，R=<a，b>，<b，a>，<b，c>，<c，d>。給出R、r（R）、s（R）、t（R）的關系圖。20、設A=1，2，3，求出A上的所有的等價關系21、設A=1，2，3，11，12，R為A上整除關系，畫出哈斯圖。22、畫出<P（a，b，c），R>的哈斯圖。23、R是X上的二元關系，對于xX定義集合：R（x）=y|xRy顯然R（x） X。如果X=-4，-3，-2，-1，0，1，2，3，4，且令R1=<x，y>|x，yXx< y，R2=<x，y>|x，yXy -1< x< y +2，R3=<x，y>|x，yXx2 y，則下列集合滿足（1）R1（0）=A（2）R2（0）=B（3）R3（3）=C（4）R1（1）=D（5）R2（-1）=EA、B、C、D、E：；-4，-3，-2，-1；-2，-1；-1，0，1；-1，0；1，2，3；2，3，4；0，1，2，3；1，2，3，4；以上結果都不對24、設S=1，2，3，定義SS上的等價關系R，<a，b>，<c，d>SS有：<a，b><c，d>a + d = b + c則由R產(chǎn)生了SS的一個劃分。在該劃分中共有A 個劃分塊，其中最大的塊有B 個元素，并且含有元素C 。最小的劃分塊有D 塊，每塊含有E 個元素。A、B、D、E：1；2；3；4；5；6；9；C：1；<1，2>；<2，2>25、設S=0，1，F(xiàn)是S中的字符構成的長度不超過4的串的集合，即F=，0，1，00，01， ，1111，其中表示空串。在F上定義偏序關系R：x，yF，有<x，y>Rx 是y的前綴。例如，00是001的前綴，但01不是001的前綴。（1）偏序集<F，R>的哈斯圖是A；（2）<F，R>的極小元是B；（3）<F，R>的最大元是C；（4）GF，G=101，1001，則G的最小上界是D ，最大下屆是E 。A：鏈；樹；既不是鏈，也不是樹；B、C、D、E：；0；0、1和；不存在；10；1；111126、設S=1，2，則S上可定義A 個不同的二元關系，其中B 個等價關系，C 個偏序關系，Is是D ，是E 。A、B、C：1；2；3；4；8；16；D、E：等價關系但不是偏序關系；偏序關系但不是等價關系；等價關系和偏序關系；既不是等價關系也不是偏序關系；27、下面給定5個函數(shù)，其中單射而非滿射的有A ，滿射而非單射的有B ，雙射的有C ，既不單射，又不滿射的有D 。設R為實數(shù)集合，Z為整數(shù)集合，R+、Z+分別表示正實數(shù)和正整數(shù)集合。f：RR，f（x）= -x2+2x-1；f：RZ+，f（x）=lnx；f：RZ，f（x）=，表示不大于x的最大整數(shù)；f：RR，f（x）=2 x+1；f：R+R+，f（x）=28、對于給定集合A和B，構造從A到B的雙射函數(shù)。（1）A=Z，B=N，其中Z，N分別表示整數(shù)集和自然數(shù)集；（2）A=，2，B=-1，1的實數(shù)區(qū)間29、（1）設S=1，2，R為S上的二元關系，且xRy。如果R=Is，則A ；如果R是數(shù)的小于等于關系，則B ；如果R=Es，則C 。（2）設有序對< x+2，4 > 與有序對<5，2x+y >相等，則x=D ，y=E 。A、B、C：x與y可任意選擇1或2；x=1，y=1；x=1，y=1或2；x=y=2；x=2，y=2；x=y=1或x=y=2；x=1，y=2；x=2，y=1；D、E：3；9； -230、設S=<1，2，3，4>，R為S上的關系，其關系矩陣是，則（1）R的關系表達式是A；（2）domR=B ；ranR=C ；（3）RR中有D 個有序對；（4）R-1的關系圖中有E 個環(huán)。A：<1，1>，<1，2>，<1，4>，<4，1>，<4，3>；<1，1>，<1，4>，<2，1>，<4，1>，<3，4>；B、C：1，2，3，4；1，2，4；1，4；1，3，4；D、E：1；3；6；731、設S=1，2，9，10，是S上的整除關系，則<S, >的哈斯圖是A ，其中最大元是B ，最小元是C ，最小上界是D ，最大下界是E 。A：一棵樹；一條鏈；以上都不對；B、C、D、E：；1；10；6，7，8，9，10；6；0；不存在32、設R的關系圖如所示，試給出r（R）、s（R）、t（R）的關系圖。33、畫出下列集合關于整除關系的哈斯圖。（1）1，2，3，4，6，8，12，24（2）1，2，8，934、設A=a，b，B=0，1，（1）求P（A）和BA；（2）構造一個從P（A）到BA的雙射函數(shù)。代數(shù)系統(tǒng)部分1、設Z+=x|xZx>0，*表示求兩個數(shù)的最小公倍數(shù)的運算，則（1）4*6=A；（2）*在Z+上B；（3）對于*運算的幺元是C ，零元是D ；（4）在Z+中E；A：24；12；B：只滿足交換率；只滿足結合律；滿足交換率、結合律和冪等律；C、D：0；1；不存在；E：不存在逆元；只有唯一的逆元2、在有理數(shù)集合Q上定義二元運算*，x，yQ有 x * y = x + y - xy則（1）2*（-5）=A ，7*1/2 = B 。（2）*在Q上是C；（3）關于*的幺元是D；（4）Q中滿足E；A、B：4；7；-13；C：可結合的；不可結合的；D：1；0；E：所有的元素都有逆元；只有唯一的逆元；xQ，x1時，有逆元x-1。3、設V1=<S1，>，V2=<S2，*>，其中S1=a，b，c，d，S2=0，1，2，3。和*由運算表1和表2給出。定義同態(tài)：S1S2，且 （a）=0，（b）=1，（c）=0，（d）=1，則（1）V1中的運算A ，其幺元是B ，V2中的運算*C ；（2）是D ，V1在下的同態(tài)像是E ；A、C：滿足交換律，不滿足結合律；不滿足交換律，滿足結合律；滿足交換律，滿足結合律；B：a；d；D：單同態(tài)；滿同態(tài)；以上兩者都不是；E：<S2，*>；<0，1，*>4、設V1=<1，2，3，1>，其中xy表示取x和y之中較大的數(shù)，V2=<5，6，*，6>，其中x*y表示取x和y之中較小的數(shù)。（1）V1含有A 個子代數(shù)，其中平凡的真子代數(shù)有B 個；V2含有C 個平凡的子代數(shù)。（2）積代數(shù)V1V2中有D 個元素，其幺元是E 。A、B、C、D：0；1；2；3；4；5；6；E：<1，5>；<1，6>；<3，6>5、設S=a，b，則S上可以定義A 個二元運算，其中有4個運算f1，f2，f3，f4，其運算表如下：則只有B 滿足交換律，C 滿足冪等律，D 有幺元，E 有零元。A：4；8；16；2；B、C、D、E：f1和f2；f1、f2和f3；f3和f4；f4；f1；f2；6、設S=1，2，9，10，問下面定義的二元運算*是否為S上的二元運算？（1）x*y = gcd（x，y），x與y的最大公約數(shù)；（2）x*y = lcm（x，y），x與y的最小公倍數(shù)；（3）x*y =大于等于xy的最小整數(shù)；（4）x*y =max（x，y）；（5）x*y =質數(shù)P的個數(shù)，其中xpy。7、設V = <R*，> 是代數(shù)系統(tǒng)，其中R*為非零實數(shù)的集合。分別對下述小題討論運算是否可交換、可結合，并求幺元和所有可逆元素的逆元。8、某二進制通信編碼由4個數(shù)據(jù)位x1、x2、x3、x4和3個校驗位x5、x6、x7構成，它們的關系如下： x5=x1x2x3；x6=x1x2x4；x7=x1x3x4；其中為異或運算。（1）設S為所有滿足上述關系的碼字的集合，且x，yS，有xy =(x1y1,x2y2，,x7y7)，那么<S，>是一個A 。（2）設x，yS，定義H（x，y）=，那么當xy時，H（x，y）B 。（3）使用該種碼可查出接收碼中包含的所有kC 位錯誤。（4）使用該種碼可糾正接收碼中包含的所有kD 位錯誤。（5）如果接收到1000011，且知有一位出錯，那么出錯位是第E 位。A：半群，但不是群；群；環(huán)，但不是域；域；前4種都不對；B、C、D、E：1；2；3；4；5；6；7；0；9、對以下定義的集合和運算判斷它們是不是代數(shù)系統(tǒng)。如果是，是哪一種？（1）S1=1，1/2，2，1/3，3，1/4，4，*為普通乘法，則S1是A ；（2）S2=a1，a2，an，n2，aiR，i=1，2，n， ai，ajS2，有aiaj=ai，則S2是B ；（3）S3=0，1，*為普通乘法，則S3是C ；（4）S4=1，2，3，6，為整除關系，則S4是D ；（5）S5=0，1，+、*分別為模2加法和乘法，則S5是E 。A、B、C、D、E：半群，但不是獨異點；是獨異點，但不是群；群；環(huán)，但不是域；域；格，但不是布爾代數(shù)；布爾代數(shù)；代數(shù)系統(tǒng)，但不是以上7種；不是代數(shù)系統(tǒng)；10、圖6-5給出一個格L，則（1）L是A 元格；（2）L是B ；（3）b的補元是C ，a的補元是D ，1的補元是E 。A：5；6；B：分配格；有補格；布爾格；以上都不對；C、D、E：不存在；c和d；0；c；11、設<B，0，1>是布爾代數(shù)，（1）a，bB，公式f為b（a（a（bb）,在B中化簡f；（2）在B中等式（ab）（ab）=0 成立的條件是什么？12、對以下定義的集合和運算判斷它們能否構成代數(shù)系統(tǒng)？如果能，請說明是構成哪一種代數(shù)系統(tǒng)？（1）S1=0，1，2，n，+為普通加法，則S1是A ；（2）S2=1/2，0，2，*為普通乘法，則S2是B ；（3）S3=0，1，2，n-1，n為任意給定的正整數(shù)，且n2，*為模n乘法，為模n加法，則S3是C ；（4）S4=0，1，2，3，為小于等于關系，則S4是D ；（5）S5=Mn（R），+為矩陣加法，則S5是E ；A、B、C、D、E：半群，不是獨異點；獨異點，不是群；群；環(huán)，不一定是域；域；格，不是布爾代數(shù)；布爾代數(shù)；代數(shù)系統(tǒng)，不是以上7種；不是代數(shù)系統(tǒng)；13、（1）設G=0，1，2，3，若為模4乘法，則<G，>構成A ；（2）若為模4加法，則<G，>是B 階群，且是C 。G中的2階元是D ，4階元是E 。A：群；半群，不是群；B：有限；無限；C：Klein群；置換群；循環(huán)群；D、E：0；1和3；2；14、（1）設<L，0，1>是布爾代數(shù)，則L中的運算和A ，運算的幺元是B ，零元是C ，最小的子布爾代數(shù)是由集合D 構成；（2）在布爾代數(shù)L中的表達式 （ab）（abc）（bc）的等價式是E ；A：適合德.摩根律、冪等律、消去律和結合律；適合德.摩根律、冪等律、分配律和結合律；適合結合律、交換律、消去律和分配律；B、C：0；1；D：1；0，1；E：b（ac）；（ac）（ab）；（ab）（abc）（bc）；15、下列各集合對于整除關系都構成偏序集，判斷哪些偏序集是格？（1）L=1，2，3，4，5；（2）L=1，2，3，6，12；（3）L=1，2，3，4，6，9，12，18，36；（4）L=1，2，22，2n；16、設A=1，2，3，4，5，<P（A），>構成群，其中為集合的對稱差。（1）求解方程1，3X=3，4，5；（2）令B=1，4，5，求由B生成的循環(huán)子群<B>；17、設A=1，2，5，10，11，22，55，110是110的正因子集，<A，>構成偏序集，其中為整除關系。（1）畫出偏序集<A，>的哈斯圖；（2）說明該偏序集是否構成布爾代數(shù)，為什么？18、在圖6-7所示的3個有界格中哪些元素有補元？如果有，請指出該元素的所有的補元。P154圖論部分1、（1）（3，3，2，3）、（5，2，3，1，4）能成為圖的度數(shù)序列嗎？為什么？（2）已知圖G有10條邊，4個3度頂點，其余頂點的度數(shù)均小于等于2，問G中至少有多少個頂點？為什么？2、（1）畫出4個頂點3條邊的所有可能非同構的無向簡單圖；（2）畫出3個頂點3條邊的所有可能非同構的有向簡單圖；3、給定下列各圖：（1）G1=<V1，E1>，其中，V1=（a，b，c，d，e），E1=（a，b），（b，c），（c，d），（a，e）；（2）G2=<V2，E2>，其中，V2=V1，E2=（a，b），（b，e），（e，b），（a，e），（d，e）；（3）G3=<V3，E3>，其中，V3=V1，E3=（a，b），（b，e），（e，d），（c，c）；（4）G4=<V4，E4>，其中，V4=V1，E4=<a，b>，<b，c>，<c，a>，<a，d>，<d，a>，<d，e>；（5）G5=<V5，E5>，其中，V5=V1，E5=<a，b>，<a，b>，<b，c>，<c，d>，<d，e>；（6）G6=<V6，E6>，其中，V6=V1，E6=<a，a>，<a，b>，<b，c>，<e，c>，<e，d>；在以上6個圖中，A 為簡單圖，B 為多重圖。A：（1），（3），（6）；（3），（4），（5）；（1），（2），（4）；（1），（4）B：（2），（4），（5）；（2），（5）；（4），（5）4、給定下列各頂點度數(shù)序列：（1）（2，2，2，2，2）；（2）（1，1，2，2，3）；（3）（1，1，2，2，2）；（4）（0，1，3，3，3）；（5）（1，3，4，4，5）；以上5組數(shù)中，A 可以構成無向簡單圖的度數(shù)序列。A：（1），（3），（4）；（1），（2）；（1），（3）；（3），（4），（5）；5、完全圖K4的所有非同構的生成子圖中，0條邊的有A 個；1條邊的有B 個；2條邊的有C 個；3條邊的有D 個；4條邊的有E 個；5條邊的有F 個；6條邊的有G 個；A、B、C、D、E、F、G：0；1；2；3；4；5；6、設G為9階無向圖，每個頂點的度數(shù)不是5就是6，證明：G中至少有5個6度頂點或者至少6個5度頂點。7、畫出5階7條邊的所有非同構的無向簡單圖。8、下列各組數(shù)中，哪些 能構成無向圖的度數(shù)列？哪些 能構成無向簡單圖的度數(shù)列？（1）1，1，1，2，3；（2）2，2，2，2，2；（3）3，3，3，3；（4）1，2，3，4，5；（5）1，3，3，3；9、設有向簡單圖D的度數(shù)列為2，2，3，3，其中入度列為0，0，2，3，出度列為 。10、設D是4階有向簡單圖，度數(shù)列為3，3，3，3，它的入度列能為1，1，1，1嗎？ （能或者不能）11、下面各無向圖中有幾個頂點？（1）16條邊，每個頂點都是2度頂點；（2）21條邊，3個4度頂點，其余都是3度頂點；（3）24條邊，各頂點的度數(shù)是相同的；12、一個n（n2）階無向簡單圖G中，n為奇數(shù)，已知G中有r 個奇數(shù)度頂點，問G的補圖中有幾個奇數(shù)度頂點？13、畫出K4的所有非同構的字圖，其中有幾個是生成子圖？生成子圖中有幾個是連通圖？14、畫出3階有向完全圖所有非同構的子圖，問其中有幾個是生成子圖？生成子圖中又有幾個是自補圖？15、設G1、G2、G3均為4階無向簡單圖，它們均有兩條邊，它們能彼此均非同構嗎？為什么？16、在K6的邊上涂上紅色或藍色。證明對于任意一種隨意的涂法，總存在紅色K3或者藍色K3。17、（1）非同構的無向的4階自補圖有A 個；（2）非同構的無向的5階自補圖有B 個；A、B：0；1；2；3；18、給定有向帶權圖如圖所示，P175圖中b到a的最短路徑的權為A ；b到d的最短路徑的權為B ；b 到e的最短路徑的權為C ；b到g的最短路徑的權為D ；A、B、C、D：4；5；6；7；8；9；10；19、某中學有3個課外小組：物理組、化學組、生物組。今有張、王、李、趙、陳5名同學。若已知：（1）張、王為物理組成員，張、李、趙為化學組成員，李、趙、陳為生物組成員；（2）張為物理組成員，王、李、趙為化學組成員，王、李、趙、陳為生物組成員；（3）張為物理組和化學組成員，王、李、趙、陳為生物組成員；問在以上3中情況下能否各選出3名不兼職的組長？20、在圖8-17所示的各圖中，A 為歐拉圖，B 為哈密頓圖。P185A、B：（a），（b），（c）；（d），（e），（f）；（c），（e）；（b），（c），（d），（e），（f）；（b），（c），（d），（e）；21、在圖8-18所示的各圖中，是二部圖的為A ，在二部圖中存在完美匹配的是B ，它的匹配數(shù)是C 。P186A、B：（a）；（b）；（c）；（d）；（e）；（f）；（a），（b）；（b），（f）；（c），（d），（e）；（d），（e）；C：1；2；3；4；22、圖8-19所示的平面嵌入中，面數(shù)為A ，次數(shù)最高的面的次數(shù)為B ，次數(shù)最低的面的次數(shù)為C ，總次數(shù)為D 。A、B、C：5；6；7；8；9；10；11；1；D：24；26；28；23、畫出完全二部圖K13，K24，K22。24、完全二部圖Krs中，邊數(shù)為 ，匹配數(shù)1為 。25、今有工人甲、乙、丙去完成三項任務a、b、c。已知甲能勝任a、b、c三項任務；乙能勝任a、b兩項任務；丙能勝任b、c兩項任務。你能給出一種安排方案，使每個工人各去完成一項他們能勝任的任務嗎？26、畫一個無向歐拉圖，使它具有：（1）偶數(shù)個頂點，偶數(shù)條邊；（2）奇數(shù)個頂點，奇數(shù)條邊；（3）偶數(shù)個頂點，奇數(shù)條邊；（4）奇數(shù)個頂點，偶數(shù)條邊；27、畫一個無向圖，使它是：（1）是歐拉圖，是哈密頓圖；（2）是歐拉圖，不是哈密頓圖；（3）不是歐拉圖，是哈密頓圖；（4）不是歐拉圖，不是哈密頓圖；28、今有a、b、c、d、e、f、g7個人，已知如下事實：a：會講英語；b：會講英語和漢語；c：會講英語、意大利語和俄語；d：會講日語和漢語；e：會講德語和意大利語；f：會講法語、日語和俄語；g：會講法語和德語；試問：這7個人要圍成一圈，應如何排座位，才能使每個人都能和他身邊（相鄰）的人交談？29、彼得森圖如圖8-23所示。證明它不是二部圖，也不是歐拉圖，更不是平面圖。P18930、證明圖8-24所示圖G是哈密頓圖，但不是平面圖。P18931、圖8-25所示圖G為平面圖，試給出它的一個平面嵌入，它是極大平面圖嗎？P18932、（1）完全圖Kn（n1）都是歐拉圖，這個命題真值為A；（2）完全圖Kn（n1）都是哈密頓圖，這個命題真值為B；（3）完全二部圖Knm（n1，m1）都是歐拉圖，這個命題真值為C；（4）完全二部圖Knm（n1，m1）都是哈密頓圖，這個命題真值為D；A、B、C、D：真；假；33、6個頂點11條邊的所有可能的非同構的連通的簡單的非平面圖有A 個，其中有B 個含子圖K33，有C 個含與K5同胚的子圖。A、B、C：1；2；3；4；5；6；7；8；34、圖9-3所示的圖G中，實線邊所構成的子圖是G的一顆生成樹T，求T對應的基本回路和基本回路系統(tǒng)，基本割集和基本割集系統(tǒng)P19335、（1）求帶權為1、3、4、5、6的最優(yōu)二元樹；（2）求帶權為2、3、5、7、8、8的最優(yōu)二元樹；36、計算非同構無向樹的個數(shù)。（1）2個頂點非同構無向樹的有A 顆；（2）4個頂點非同構無向樹的有B 顆；（3）6個頂點非同構無向樹的有C 顆；（4）7個頂點非同構無向樹的有D 顆；A、B、C、D：1；2；4；6；7；8；9；10；11；12；37、（1）在一棵樹中有7片樹葉，3個3度頂點，其余都是4度頂點，則該樹有A 個4度頂點；（2）在一棵樹中有2個4度頂點，3個3度頂點，其余都是樹葉，則該樹有B 片樹葉；（3）一棵樹中有ni個頂點的度數(shù)為i，i=2，3，k，而其余的頂點都是樹葉，則該樹中有C 片樹葉。A、 B：1；2；3；4；5；6；7；8；9；10；C：；38、圖9-16給出兩個帶權圖。P200（1）圖（a）中最小生成樹的權為A；（2）圖（b）中最小生成樹的權為B；10；14；15；21；22；24；25；26；27；28；39、用Huffman算法求帶權為2、3、5、7、8的最優(yōu)二元樹T。（1）T的權為A ；（2）T中有B 片樹葉，C 個2度頂點，D 個3度頂點，E 個4度頂點，（3）T的高度為F 。A：40；45；50；55；60；B、C、D、E、F：0；1；2；3；4；5；6；7；8；40、（1）求一個帶權為1、2、3、4、5、5.5、7.5的最優(yōu)三元樹，其權為A；（2）求一個帶權為1.5、2.5、3、4、5、6的最優(yōu)三元樹，其權為B；A、B：30；35；37；45；47；48；48.5；50；52；55；41、設無向樹T有3個3度、2個2度頂點，其余頂點都是樹葉，樹葉頂點數(shù)為 。42、設無向樹T有7片樹葉，其余頂點的度數(shù)均為3，求T中3度頂點數(shù)？畫出所有具有此種度數(shù)的非同構的無向樹。45、畫出度數(shù)列為1，1，1，1，2，2，4的所有非同構的7階無向樹。46、在圖9-20所示的無向圖G中，實線邊所示的子圖為G的一棵生成樹T，求G對應于T的基本回路系統(tǒng)和基本割集系統(tǒng)。P20347、求圖9-21所示兩個帶權圖的最小生成樹，并計算它們的權。P20348、計算非同構的根數(shù)的個數(shù)。（1）2個頂點非同構的根數(shù)為A 個；（2）3個頂點非同構的根數(shù)為B 個；（3）4個頂點非同構的根數(shù)為C 個；（4）5個頂點非同構的根數(shù)為D 個；A、B、C、D：1；2；3；4；5；6；7；8；9；10；