2007級(下)離散數(shù)學(xué)標(biāo)準(zhǔn)答案(尤楓)

千里之行，始于足下。第2頁/共2頁精品文檔推薦2007級(下)離散數(shù)學(xué)標(biāo)準(zhǔn)答案(尤楓)北京化工大學(xué)2008——2009學(xué)年第一學(xué)期

《離散數(shù)學(xué)（II）》期末考試試卷標(biāo)準(zhǔn)答案

一、填空題（本題共20分，每題2分）

1.設(shè)R是實(shí)數(shù)集合，f：R→R，f(x)=x2-x+2，g：R→R，g(x)=x-3，則：

g。f=x2-x-1。

2.設(shè)I,Q,R,C分不表示整數(shù)集、有理數(shù)集、實(shí)數(shù)集和復(fù)數(shù)集，在集合I,R-Q,C中，彼此等勢的集合是R-Q與C。

3.設(shè)A={1,-1}，則A對于一般加法、減法、乘法和除法中乘法和除法運(yùn)就是封閉的。

4.設(shè)G=是24階循環(huán)群，則G的生成元有8個(gè)。

5.設(shè)是環(huán)，則對任意的a∈S，有a·0=0。

6.設(shè)是由實(shí)數(shù)集上的小于等于關(guān)系構(gòu)成的格，對任意的x,y∈R，則x和y的最小上界x∨y=x與y的最小公倍數(shù)。

7.設(shè)v是有n個(gè)結(jié)點(diǎn)的有向徹底圖Kn的一具結(jié)點(diǎn)，則d(v)=2(n-1)。

8.具有n個(gè)結(jié)點(diǎn)的k-正則圖G的邊數(shù)m=kn/2。

9.設(shè)G=是有n個(gè)結(jié)點(diǎn)和m條邊的無向圖，若G是連通的且m=n-1，則稱G是無向樹。

10.設(shè)G*是連通平面圖G的對偶圖，已知G的邊數(shù)m=10，面數(shù)k=3,則G*的面數(shù)k*=9。

二、簡答題（本題共30分，每題10分）

1.關(guān)于給定的整數(shù)集I和自然數(shù)集N，推斷f是否是從I到N的函數(shù)f：I→N，

f(x)=x2+1

并講明理由。假如是，講明f是否為單射、滿射或雙射。

解：（6分）f是從I到N的函數(shù)。因?yàn)閷θ我鈞∈I，有f(x)=x2+1∈N，且唯一，故

f是從I到N的函數(shù)。

（4分）f別是單射、滿射或雙射。

因0∈N，但別存在x∈I，使f(x)=0，因此f別是滿射的。

又因?yàn)楫?dāng)x=1或x=-1時(shí)，f(x)=2，即1≠-1，而f(1)=f(-1)，故f別是單射的。

2.設(shè)R是實(shí)數(shù)集合，推斷R×R對于·運(yùn)算能否構(gòu)成群，請講明理由。其中·運(yùn)算定義為：

·=

解：（2分）能構(gòu)成群。

(1)（2分）封閉性。任意的,∈R×R,有a,c∈R,b,d∈R，a+c∈R,b+d∈R，故·=，因此R×R

(2)（2分）結(jié)合律。任意,,∈R×R

則(·)·=

=

=·(·)

(3)（2分）單位元為。因?yàn)?/p>

任意對∈R×R，有·=·=

(4)（2分）逆元。任意對∈R×R，其逆元為。因?yàn)?/p>

·=·=。

3.格L的哈斯圖如下圖所示，咨詢下述子集中哪些是L的子格，請講明理由。關(guān)于L的子格講明是否是有界格、分配格。

L1={0,a,b,1}

L2={0,a,1}

L3={a,c,d,1}

L4={0,c,e,1}解：（2分）L1別是L的子格。因?yàn)閧a,b}的最小上界是c，但c別在L1中。

ba

d

（3分）L2是L的子格。因?yàn)長2中任意兩元素的最小上界和最大下界均在L2中。且它是有界格和分配格。

（3分）L3是L的子格。因?yàn)長3中任意兩元素的最小上界和最大下界均在L3中。且它是有界格和分配格。

（2分）L4別是L的子格。因?yàn)閧c,e}的最大下界是b，但b別在L4中。

三、計(jì)算題（本題共30分，第1小題20分，第2小題10

1.設(shè)有向圖G=如圖所示，求

(1)G的關(guān)聯(lián)矩陣；

(2)G的鄰接矩陣；

(3)G的可達(dá)矩陣；

(4)圖中所有長度小于等于5的通路（包括回路）數(shù)目；

(5)求G的強(qiáng)分圖、單向分圖和弱分圖。

解：(1)（5分）G的關(guān)聯(lián)矩陣為

????????????????????=110000010110000001100000011001000110010001M(2)（5分）G的鄰接矩陣為

?????????

???????????=010000001001000000

001000100100000010A(3)（5分）G的可達(dá)矩陣為

1v2v3

v4v5Ge23e4e2e3

?????????

???????????=111111111111001000

001100111111111111P(4)（5分）圖中所有長度小于等于5的通路（包括回路）共35條。

(5)（5分）G的強(qiáng)分圖為G[{v1,v2,v5,v6}]，G[{v3}]，G[{v4}]；G的單向分圖為G；G的弱分圖為G。

2.設(shè)無向圖T中，有2個(gè)2度結(jié)點(diǎn)，2個(gè)3度結(jié)點(diǎn)，1個(gè)4度結(jié)點(diǎn)，其余結(jié)點(diǎn)均為樹葉，試求T的結(jié)點(diǎn)數(shù)n、邊數(shù)m和樹葉數(shù)t。

解：因?yàn)閙=n-1

2m=2×2+3×2+1×4+t×1

t=n-5

解得2m=9+n

故2(n-1)=9+n

因此得n=11，m=10，t=6

四、證明題（本題共20分，每小題10分）

1.設(shè)A={a+bi|a,b∈Q}，其中Q為有理數(shù)集合，i2=-1，運(yùn)算為復(fù)數(shù)的加法+和乘法×，證明A同復(fù)數(shù)的加法+和乘法×構(gòu)成環(huán)。

證明：是交換群。（5分）

任取a+bi，c+di，e+fi∈A,則a,b,c,d,e,f∈Q。

(1)封閉性。因a+c,b+d∈Q，故(a+c)+(b+d)i∈A。

(2)結(jié)合律。因((a+bi)+(c+di))+(e+fi)=(((a+c)+(b+d)i)+(e+fi))

=((a+c)+e)+((b+d)+f)i=(a+(c+e))+(b+(d+f))i

=(a+bi)+((c+e)+(d+f)i)=(a+bi)+((c+di))+(e+fi))

(3)單位元為0+0i。

因?yàn)?a+bi)+(0+0i)=(0+0i)+(a+bi)=(a+bi)

(4)逆元。a+bi的逆元是-a-bi。

因?yàn)?a+bi)+(-a-bi)=(-a-bi)+(a+bi)=0+0i

(5)交換律。

(a+bi)+(c+di)=(a+c)+(b+d)i=(c+a)+(d+b)i=(c+di)+(a+bi)

是半群。（3分）

(1)封閉性。(a+bi)(c+di)=(ac-bd)+(bc+ad)i∈A

結(jié)合律。((a+bi)(c+di))(e+fi)=((ac-bd)+(bc+ad)i)(e+fi))

=(ace-bde-bcf-adf)+(bce+ade+acf-bdf)i

(a+bi)((c+di)(e+fi))=(a+bi)((ce-df)+(de+cf)i)

=(ace-bde-bcf-adf)+(bce+ade+acf-bdf)i

故((a+bi)(c+di))(e+fi)=(a+bi)((c+di)(e+fi))

×對+的分配律。

(a+bi)((c+di)+(e+fi))=(a+bi)((c+e)+(d+f)i)

=(ac+ae-bd-bf)+(bc+be+ad+af)i

(a+bi)(c+di)+(a+bi)(e+fi)=((ac-bd)+(ad+bc)i)+((ae-bf)+(be+af)i)

=(ac+ae-bd-bf)+(bc+be+ad+af)i

故(a+bi)((c+di)+(e+fi))=(a+bi)(c+di)+(a+bi)(e+fi)

同理可證((c+di)+(e+fi))(a+bi)=(c+di