離散數(shù)學試卷及答案

一、

填空10%（每小題2分、

ZxxZ0}的幺元是，元是。

，*示求兩數(shù)的最小倍數(shù)的運算Z示整數(shù)集合于*運算、代數(shù)系統(tǒng)<A,*>中|A|>1如果

e和

分別為<A,*>幺元和零元，則

e和

的關(guān)系為。、設(shè)<G,*>一個群，<G,*>是阿貝爾群的充要條件是。、圖

的完全關(guān)聯(lián)矩陣為。、一個圖是平面圖的充要條件是。二、

選擇10%（每小題2分、下各集合都是N的集）合在普通加法運算下是封閉的。A{x|x的可以被整除}C、{xx是的因子}

B、{x|x與5互}D、{x|x是的數(shù)}、設(shè)

{0,1,2},

，

，其中

表示模加*示模法，則積代數(shù)

的幺元是（A；B、；C、<1,0>D、<1,1>。、設(shè)合S={1,2,3,6}”整關(guān)系，則代數(shù)系<,≤>是（A域；B、格，但不是布爾代數(shù)、布爾代數(shù)；D、是代數(shù)系統(tǒng)。、設(shè)n階有邊，每個結(jié)點度數(shù)不是k就是，G中個k度點，k則N=（kAn；Bn(k+1)；C、；

D、n(k+1)-2m。、一樹有7樹葉，結(jié)點，其余全是結(jié)點，則該樹有（）個4結(jié)點。

A1

B2；

、3；

D、4。三、判（每小題2）），S普通加法和乘法運算下都不封閉。）布<A,≤>中，對A任意原子，和另一非零元b在

b

或

a

中有且僅有一個成立。）

S{xZx

，+,·為普通法和乘法，<，+是域。）條路和任何一棵生成樹至少有一條公共邊。）是棵m叉樹，它有片葉i分枝點，(m-1)i=t-1。四、證38%分對代數(shù)系統(tǒng)A,*>，*A上元運算，為A中元，如*可結(jié)合的且每個元素都有右逆元，則1中每個元素在右逆元必定也是左逆元。（2每個元素的逆元是唯一的。12分）設(shè)

,,

是一個布爾代數(shù)，如果在A上定義二元運算☆，為ab)()

，則<A,>是一阿貝爾群。分）證明任一環(huán)的同態(tài)象也是一環(huán)。分）若

E

(,E)

是每一個面至少由k(k≥3)條邊圍成的連通平圖，則

e

k(vk

。五、應32%、（分某年級共有門修課程，期末考試前必須提前將這門程考完，每每天只在下午考一門課，若以課程表示結(jié)點，有一人同時選兩門課程，則這兩點間有邊（其圖如右問至少需幾天？

、用方求圖

的可達矩陣，并判斷圖的連通性分）、設(shè)、b、、d、、f七人，他們分別會講的語言如下a：英，：漢、英，c：、西班牙、俄，d日、漢，e：、西班牙，f法、日、俄，：法、德，能否這七個人的座位安排在圓桌旁，使得每個人均能與他旁邊的人交談？8分、用Huffman算求帶權(quán)為235，8的優(yōu)二叉樹T，求W（若傳遞a，，c，d，，f的頻率分別為，，，7%，求傳輸它的最佳前綴碼）一填10%（每題2分、，不在；2；3、

,bG有(a**(*a*)*(*b

；e

e

e

3

e

5

v3

、它不包含與K或K在結(jié)點內(nèi)同構(gòu)的子圖。3,5二選10%（每題分題目答案

A

B

C

D

A三判10%題目答案

Y

Y

N

N

N

四、證38%分）證明：（1設(shè)

b

，b是的右逆元c是右逆元，由于

*(*)*e

，*c**b**a)*(*)b*a**a所以b是的左逆元。（2設(shè)元素有兩個逆元、c，那么**(*)*)**ca的元是唯一的。分）證明：[乘][群]

閉,,c

運算☆在A上封閉。(☆☆(()a))☆)(a)))a()))a)(()b)))a)(((a)(a))))a)aa同理可得(b☆)a))))(a☆a(b)

即☆滿足結(jié)合性。[幺]

,0a(0))故全下界是A中于運算☆的幺元。[逆]

(☆a)aa)即A中每一個元素以其自身為逆元。[交]

a☆ba)b))a即運算☆具有可交換性。所以<A,☆是Abel群、(10分)證:設(shè)

是一環(huán)且

f(),

是關(guān)于同態(tài)映射f的態(tài)象。

由

,

是Abel群，易證

f()

也是Abel群

是半群，易證

f()

也是半群?，F(xiàn)只需證：對是分配的。,bf(),的,aa:f()i1,2,3113ii)f)(f(a)f())f(a((32323f(af((af()f(a)31111()f(a))f)f(a))213)(b)213

于是同理可證

(b)(b21因此

f(),

也是環(huán)。分）證明：設(shè)有r個面，ri

r)eg(r)(1ir)2e即rii

2ek而v2,故v

2rk

即

k(k

。五應用32%8分解：

)

即為最少考試天數(shù)。用Welch-Powell方對著：

vvvvv97456第一種顏色的點

vv914

，剩余點

vvv375第二種顏色的點第三種顏色的點)所以≤3

vv3v28

，剩余點

v28任

vv239

構(gòu)成一圈，所以

G)

≥3故

()

=3所以三天下午即可考完全部九門課程。

分）解：A(G)

i

：A[21]=1，

；i：A[4，，A

i

：3]=A[23]=A[4，，A

i

：A[k，，，，3，4A

11的各元素全為，所以G強連通圖，當然是單向連通和弱連通。分）解：用7個點表示7個，若兩人能交談可用一條無向邊連結(jié)，所