東北大學(xué)考試試卷2010

得分總分—得分總分—二三四五-i-八七八九東北大學(xué)考試試卷（A卷）2010—2011學(xué)年第2學(xué)期課程名稱：圖論與代數(shù)結(jié)構(gòu)一.（15分）填空設(shè)A={2,4,6,8},A上的二元運(yùn)算*定義為：a*b=max{a,b},則在獨(dú)異點(diǎn)<A,*>中，單位元是2 ,零元是8 。設(shè)a是12階群的生成元，則a2是J階元素，a5是￡階元素。設(shè)〈G,*〉是一個(gè)群，G中的幕等元是j。若G={a,b,c},a*x=b，則村a-1*b；設(shè)a是幺元，則b*c=a。小于5個(gè)元素的格都是有補(bǔ)分配（布爾）格。有n個(gè)結(jié)點(diǎn)的樹，其結(jié)點(diǎn)度數(shù)之和是2（n-1） 。O6.一個(gè)無(wú)向圖有生成樹的充分必要條件是該圖是連通圖一7.n階無(wú)向完全圖Kn的邊數(shù)是一n（n-1）/2，每個(gè)結(jié)點(diǎn)的度數(shù)是一 n-1若Kn為歐拉圖，則n的取值為f數(shù)… 8.具有6個(gè)頂點(diǎn)，12條邊的連通簡(jiǎn)單平面圖中，每個(gè)面都是由^^條邊圍成?！?9.無(wú)向樹T有8片樹葉，2個(gè)3度分支結(jié)點(diǎn)，其余的分支結(jié)點(diǎn)都是4度頂點(diǎn)，封 則—個(gè)4度分支結(jié)點(diǎn)。得分（26分）判斷題4. （6分）判斷下列集合和運(yùn)算能否構(gòu)成半群、獨(dú)異點(diǎn)和群。如果不能，簡(jiǎn)單說明理由。（1）a是正整數(shù)，G={an|neZ，Z為整數(shù)集},運(yùn)算是普通乘法。（6分）設(shè)V1=<Z,+>,V2=<Z,?>，其中Z為整數(shù)集合，+和?分別代表普通加法和乘法。判斷下述集合S能否構(gòu)成v1和v2的子半群和子獨(dú)異點(diǎn)。如果不能，簡(jiǎn)單說明理由。（1） S={2klkeZ}是V1的子半群和子獨(dú)異點(diǎn)；是V2的子半群但不是子獨(dú)異點(diǎn)。因?yàn)椴缓墼?。（2分）（2） S={2k+1lkeZ}不是V1的子半群和子獨(dú)異點(diǎn)。因?yàn)椴环忾]。是V2的子半群和子獨(dú)異點(diǎn)。（2分）（3） S={-1,0,1}不是V1的子半群和子獨(dú)異點(diǎn)。因?yàn)椴环忾]。是V2的子半群和子獨(dú)異點(diǎn)。（2分）（6分）判斷下列集合和給定運(yùn)算能否構(gòu)成環(huán)、整環(huán)和域。如果不能，簡(jiǎn)單說明理由。（1） A是有理數(shù)集合Q，運(yùn)算為普通加法和乘法。構(gòu)成環(huán)、整環(huán)和域。（2分）（2） A={-1,0,1}，運(yùn)算為普通加法和乘法。不構(gòu)成環(huán)、整環(huán)和域。因?yàn)?lt;A,+>不是群。（2分）（3） <P（E）,?,n>，P（E）為集合E的幕集，運(yùn)算為集合的對(duì)稱差和交運(yùn)算。構(gòu)成環(huán)，但不構(gòu)成整環(huán)和域，因?yàn)楹辛阋蜃?。?分）（8分）下面給出三個(gè)偏序集的哈斯圖。判斷其中哪些是格。如果不是格，說明理由；如果是格，判斷是否為分配格。（1）和（3）是格，（2分）（2）不是，因?yàn)閧c,d}沒有上確界和下確界。（2分）（1）是分配格；（2分）（3）不是，因?yàn)樗形逶氐姆欠峙渥痈瘛＃?分）是半群、獨(dú)異點(diǎn)和群。（2分）（2）Q+是正有理數(shù)集，運(yùn)算為普通加法。（2分）是半群，不是獨(dú)異點(diǎn)和群。滿足封閉、結(jié)合，但沒有幺元。，，，（3）設(shè)Z為整數(shù)集，Vx,yE乙運(yùn)算x*y=x+y-2。，，，是半群、群和獨(dú)異點(diǎn)。（2分）三.（16分）計(jì)算題1.試求出8階循環(huán)群（a為生成元）的所有生成元和所有子群。四.（10分）設(shè)＜G,*＞為群，a是G中的2階元，H為G中與a可交換的元素構(gòu)成的集合，即H=｛xeG|a*x=x*a｝，證明H是G的子群。證明:得分（證明:得分（4分）首先e屬于H,H是G的非空子集。(2分)任取x,y^H，有(x*y-i)*a=x*(y-i*a)=x*(a-i*y)-i=x*(a*y)-i=x*(y*a)-i=x*a-i*y-i=x*a*y-i=a*x*y-i=a*(x*y-i)因此x*y-i屬于H。由判定定理，命題得證。(8分)生成元：a、a3、a5、a7（4分）所有子群：｛e｝、｛e,a2，a6，a4｝、｛e，a4｝、｛a,a2，a3，a4，a5，a6，a7，e｝另：可以利用子群的定義，證明運(yùn)算在子集上滿足封閉、含幺和可逆。（每個(gè)性質(zhì)得證為2分）TOC\o"1-5"\h\z2.設(shè)E（x,x,x）=（x△x）v（x△x）v（x△x）是＜｛0,I｝,V,人一＞上的一個(gè)布爾表I2 3 1 2 2 3 2 3另：可以利用子群的定義，證明運(yùn)算在子集上滿足封閉、含幺和可逆。（每個(gè)性質(zhì)得證為2分）達(dá)式。分別寫出它的析取范式與合取范式。合取范式：E(x,x,x)=(xvxvx)△(xvxvx)△(xvxvx)(4分)1 2 3 1 2 3 1 2 3 1 2 3析取范式:E(x,x,x)=(x△x△x)v(x△x△x)v(x△x△x)v(x△x△x)v(x△x△x)1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3(4分)O::::線得分五.(10分)設(shè)＜B,A,V,-,0,1＞是布爾代數(shù)，在B上定義二元運(yùn)算十，Vx,yEB,x?y=(xay)v(xay)o問＜B,?＞能否構(gòu)成代數(shù)系統(tǒng)？如果能，指出是哪一種代數(shù)系統(tǒng)，并給出證明。: 答：能構(gòu)成群。(2分)； 證明：備 由格代數(shù)性質(zhì)可知運(yùn)算封閉。(2分)任取a,b,c(a?Z?)?c=(aav(aaZ?)?c: =(((aaZ?)v(aab))ac)v((aaZ?)v(aaZ?)ac): =(?AZ?AC)V(aAZ?AC)V(aAZ?AaAZ?AC)O =(aAbac)v(aabac)v((avb)a(avb)ac)=(aaZ?ac)v(aaZ?ac)v(aaaac)v(aaZ?ac)v(Z?aaac)v(Z?aZ?ac): =(aaac)v(aaZ?ac)v(aaac)v(Z?aaac): =(aA((bAc)v(bac))v(aa((bac)vac))): =((bac)vac)aa)v(aa((bac)v(^ac)))營(yíng) =a?(b?c): 易見結(jié)合律成立。(2分): ??0=(?a6)v(?a0)=(?a1)v0=??0為單位元。(2分): "十"=("A")v("A")=°v°=°,a為其本身的逆元。(2分)命題得證。O得分六.(8分)設(shè)vG,★＞是群，而a^G,/:G^G是映射，對(duì)Vx^G,?a*x*a-i求證/■是G到G的自同構(gòu)。證明：1)證明/'是滿射：任取y^G,因a^Ga.ieGa-i*y*a^G,x=a-i*y*a,貝I]/(x)=a*x*a-i=a*(a-i*y*a)*a-i=(a*a-i)*y*(a*a-i)=y所以/是滿射的。(2分)證明/■是入射的：任取xpx2eG,設(shè)/(X])項(xiàng)乂2)艮a*x1*a-i=a*x2*a-i由群可消去性得x=x2-*.f是入射的所以/■是雙射的。(2分)再證/■滿足同構(gòu)等式：任取xpx2eG,=a*(X]*X2)*a-i=a^Cx^e^x^^a-i=a*(x1*(a-i*a)*x2)*a-i=(a*x1*a-i)*(a*x2*a-i)=/(Xi)”X2)(4分)所以/'是G到G的自同構(gòu)。得分七.（15分）簡(jiǎn)答題1.設(shè)無(wú)向圖G=<V,E>,|E|=12O已知有6個(gè)3度頂點(diǎn)，其他頂點(diǎn)的度數(shù)均小于3。問G中至少有多少個(gè)頂點(diǎn)？要求有計(jì)算過程。: 答：設(shè)G中度數(shù)小于3的頂點(diǎn)有k個(gè)，由歐拉握手定理24=Xdeg（v）（2分）宓* veVi知，度數(shù)小于3的頂點(diǎn)度數(shù)之和為6。故當(dāng)其余的頂點(diǎn)度數(shù)都為2時(shí)，G的頂: 點(diǎn)最少。即G中至少有9個(gè)頂點(diǎn)。（3分）6? 2.設(shè)G=<V,E>是連通的簡(jiǎn)單平面圖，|V|=n>3,面數(shù)為k,試證明k^2n-4o: 證明：: 記|E|=mo因?yàn)镚*V,E>是連通的簡(jiǎn)單平面圖，故每個(gè)面的度數(shù)都不身 小于3。從而由公式zdeg（f）=2|E|可得: f^F: 3k<2m（2分）: 再