第一篇：《離散數(shù)學》圖論部分習題

《離散數(shù)學》圖論部分習題

1.已知無向圖G有12條邊，6個3度頂點，其余頂點的度數(shù)均小于3，問G至少有幾個頂點？并畫出滿足條件的一個圖形.（24-3*6）/2 +6=9 2.是否存在7階無向簡單圖G，其度序列為1、3、3、4、6、6、7.給出相應證明.不存在；7階無向簡單圖G中最大度≤6 3.設d1、d2、…、dn為n個互不相同的正整數(shù).證明：不存在以d1、d2、…、dn為度序列的無向簡單圖.Max{d1，d2，…，dn}≥n，n階無向簡單圖G中最大度≤n-1 4.求下圖的補圖.5.1)試畫一個具有5個頂點的自補圖

2)是否存在具有6個頂點的自補圖，試說明理由。

對于n階圖，原圖與其補圖同構(gòu)，邊數(shù)應相等，均為(n*(n-1)/2)/2，即n*(n-1)/4且為整 數(shù)，n=4k或n=4k+1，不存在6階自補圖。

6.設圖G為n(n>2且為奇數(shù))階無向簡單圖，證明：G與G的補圖中奇度頂點個數(shù)相等.n(n>2且為奇數(shù))，奇度點成對出現(xiàn)

7.無向圖G中只有2個奇度頂點u和v，u與v是否一定連通.給出說明或證明。

只有2個奇度頂點u和v，如果不連通，在u和v在2個連通分支上，每個分支上僅有一個奇度頂點，與握手引理相矛盾。

8.圖G如下圖所示：

1)寫出上圖的一個生成子圖.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.說明：δ(G)=min{ d(v)| v?V } ；κ(G)=min{ |V’| |V’是圖G的點割集} ； λ(G)=min{ |E’| |E’是圖G的邊割集} 9.在什么條件下無向完全圖Kn為歐拉圖？

n為奇數(shù)時

10.證明：有橋的圖不是歐拉圖.假設是歐拉圖：橋的端點是u和v，并且圖各頂點度均為偶數(shù)； 橋為割邊，刪除橋，圖不再連通，u和v應該在2各不同的連通分支上；且u和v度數(shù)變?yōu)槠鏀?shù)；由于其他頂點度數(shù)均為偶數(shù)，則u和v所在的連通分支上只有一個奇度頂點，與握手引理矛盾。

11.證明：有橋的圖不是哈密爾頓圖.若G是K2，顯然不是哈密爾頓圖；

否則n≥3，則橋的兩個端點u和v至少有一個不是懸掛頂點（容易證明懸掛頂點不是割點）；設u不是懸掛點，則u是割點，存在割點顯然不是哈密爾頓圖。

12.樹T有2個4度頂點，3個3度頂點，其余頂點全為樹葉，問T有幾片樹葉？

X+2*4+3*3=2*（2+3+x-1）

x=9 13.證明：最大度Δ（T）≥k的樹T至少有k片樹葉。

設有n個頂點，其中x片樹葉

2*（n-1）≥1*K+（n-x-1）*2+x*1

x≥k 14.已知具有3個連通分支的平面圖G有4個面，9條邊，求G的階數(shù).n-9+4=3+1

n=9

15.給出全部互不同構(gòu)的4階簡單無向圖的平面圖形。

16.如果G是平面圖, 有n個頂點、m條邊、f個面，G有k個連通分支。試利用歐拉公式證明:：n-m+f=k+1.

第二篇：離散數(shù)學圖論習題

第4章圖論

綜合練習

一、單項選擇題

1．設L是n階無向圖G上的一條通路，則下面命題為假的是()．

(A)L可以不是簡單路徑，而是基本路徑

(B)L可以既是簡單路徑,又是基本路徑

(C)L可以既不是簡單路徑，又不是基本路徑

(D)L可以是簡單路徑，而不是基本路徑

答案：A

2．下列定義正確的是()．

(A)含平行邊或環(huán)的圖稱為多重圖(B)不含平行邊或環(huán)的圖稱為簡單圖

(C)含平行邊和環(huán)的圖稱為多重圖(D)不含平行邊和環(huán)的圖稱為簡單圖答案：D

3．以下結(jié)論正確是()．

(A)僅有一個孤立結(jié)點構(gòu)成的圖是零圖

(B)無向完全圖Kn每個結(jié)點的度數(shù)是n

(C)有n(n>1)個孤立結(jié)點構(gòu)成的圖是平凡圖

(D)圖中的基本回路都是簡單回路

答案：D

4．下列數(shù)組中，不能構(gòu)成無向圖的度數(shù)列的數(shù)組是()．

(A)(1,1,1,2,3)(B)(1,2,3,4,5)(C)(2,2,2,2,2)(D)(1,3,3,3)

答案：B

5．下列數(shù)組能構(gòu)成簡單圖的是()．

(A)(0,1,2,3)(B)(2,3,3,3)(C)(3,3,3,3)(D)(4,2,3,3)

答案：C

6．無向完全圖K3的不同構(gòu)的生成子圖的個數(shù)為（）．

(A)6(B)5(C)4(D)

3答案：C

7．n階無向完全圖Kn中的邊數(shù)為（）．(A)n(n?1)n(n?1)(B)(C)n(D)n(n+1)2

2答案：B

8．以下命題正確的是()．

(A)n(n?1)階完全圖Kn都是歐拉圖

(B)n(n?1)階完全圖Kn都是哈密頓圖

(C)連通且滿足m=n－1的圖(?V?=n,?E?=m)是樹

(D)n(n?5)階完全圖Kn都是平面圖

答案：C

10．下列結(jié)論不正確是()．

(A)無向連通圖G是歐拉圖的充分必要條件是G不含奇數(shù)度結(jié)點

(B)無向連通圖G有歐拉路的充分必要條件是G最多有兩個奇數(shù)度結(jié)點

(C)有向連通圖D是歐拉圖的充分必要條件是D的每個結(jié)點的入度等于出度

(D)有向連通圖D有有向歐拉路的充分必要條件是除兩個結(jié)點外，每個結(jié)點的入度等

1于出度 答案：D

11．無向完全圖K4是（）．

（A）歐拉圖（B）哈密頓圖（C）樹答案：B

12．有4個結(jié)點的非同構(gòu)的無向樹有()個．

(A)2(B)3(C)4(D)5 答案：A

13．設G是有n個結(jié)點，m條邊的連通圖，必須刪去G的()條邊，才能確定G的一棵生成樹．

(A)m?n?1(B)n?m(C)m?n?1(D)n?m?1 答案：A

14．設G是有6個結(jié)點的完全圖，從G中刪去()條邊，則得到樹．(A)6(B)9(C)10(D)15 答案：C

二、填空題

1．數(shù)組{1，2，3，4，4}是一個能構(gòu)成無向簡單圖的度數(shù)序列，此命題的真值是.答案：0

2．無向完全圖K3的所有非同構(gòu)生成子圖有個． 答案：

43．設圖G??V,E?，其中?V??n,?E??m．則圖G是樹當且僅當G是連通的，且m?． 答案：n－

14．連通圖G是歐拉圖的充分必要條件是 答案：圖G無奇數(shù)度結(jié)點

5．連通無向圖G有6個頂點9條邊，從G中刪去G的一棵生成樹T． 答案：4

6．無向圖G為歐拉圖，當且僅當G是連通的，且G中無 答案：奇數(shù)度

7．設圖G??V,E?是簡單圖，若圖中每對結(jié)點的度數(shù)之和，則G一定是哈密頓圖． 答案：?

8．如圖1所示帶權(quán)圖中最小生成樹的權(quán)是．

答案：1

2三、化簡解答題

1．設無向圖G＝，V={v1，v2，v3，v4，v5，v6}，E={(v1，v2),(v2，v2),(v4，v5),(v3，v4),(v1，v3),(v3，v1),(v2，v4)}．(1)畫出圖G的圖形；

圖

1圖

2(2)寫出結(jié)點v2, v4，v6的度數(shù)；(3)判斷圖G是簡單圖還是多重圖．解：(1)圖G的圖形如圖5所示．

(2)deg(v2)?4,deg(v4)?3,deg(v6)?0．

(3)圖G是多重圖．作圖如圖2.2．設圖G＝，其中

V＝{a,b,c,d,e}, E={(a,b),(b,c),(c,d),(a,e)}

試作出圖G的圖形，并指出圖G是簡單圖還是多

重圖？是連通圖嗎？說明理由.be

解：圖G如圖8所示．.圖G中既無環(huán)，也無平行邊，是簡單圖． cd 圖G是連通圖．G中任意兩點都連通.圖

3所以，圖G有9個結(jié)點．作圖如圖3．

四、計算題

1．設簡單連通無向圖G有12條邊，G中有2個1度結(jié)點，2個2度結(jié)點，3個4度結(jié)點，其余結(jié)點度數(shù)為3．求G中有多少個結(jié)點．試作一個滿足該條件的簡單無向圖．

解：設圖G有x個結(jié)點，由握手定理

2?1+2?2+3?4+3?（x?2?2?3）＝12?

23x?24?21?18?27x＝9 故圖G有9個結(jié)點． 圖

4滿足該條件的簡單無向圖如圖4所示

2．設圖G(如圖5表示)是6個結(jié)點a,b,c, d,e,f的圖，試求，圖G的最小生成樹，并計算它的權(quán)．

c 解：構(gòu)造連通無圈的圖，即最小生成樹，用

克魯斯克爾算法：

第一步： 取ab＝1；第二步： 取af=4第三步： 取fe＝3；第四步： 取ad=9圖5第五步： 取bc=2

3如圖6．權(quán)為1+4+3+9+23=40

3．一棵樹T有兩個2度頂點，1個3度頂點；3個4

問它有幾片樹葉？

解：設T有n頂點，則有n－1條邊．T中有2個 2度頂點，1個3度頂點，3個4度頂點，其余n－2－1-3個1度頂

點．

由握手定理： 2·2+1·3+3·4+(n－2－1-3)=2(n－1)解得 n=15．于是T有15-6=9片樹葉

五、證明題

1．若無向圖G中只有兩個奇數(shù)度結(jié)點，則這兩個結(jié)點一定是連通的．

證：用反證法．設G中的兩個奇數(shù)度結(jié)點分別為u和v．假若u和v不連通．

即它們之間無任何通路，則G至少有兩個連通分支G1，G2，且u和v分別屬于G1和G2，于是G1和G2各含有一個奇數(shù)度結(jié)點．這與握手定理的推論矛盾．因而u和v一定是連通的．

第三篇：離散數(shù)學習題

集合論

1.A={?,1}，B={{a}}求A的冪集、A×B、A∪B、A+B。2.A={1,2,3,4,5}, R={(x,y)|x

4.A={a,b,c},R= IA ∪{(a,b),(b,a)}，求a和b關于R的等價類。

5.R是A上的等價關系，A/R={{1,2}，{3}},求A，R。6.請分別判斷以下結(jié)論是否一定成立，如果一定成立請證明，否則請舉出反例。

①如果A∪B?C，則A?C或者B?C。②如果A×B=A×C且A??，則B=C。

27.如果R是A上的等價關系，R,r(R)是否一定是A上的等價關系？證明或舉例。

8.已知A∩C?B∩C,A-C?B-C,證明：A?B。9.證明：AX(B∩C)=(AXB)∩(AXC)10.證明：P(A)∪P(B)?P(A∪B)-111.證明：R[sym] iff R=R

-1212.證明：r(R)=R∪IA,S(R)=R∪R,t(R)=R∪R∪...13.證明：s(R∪S)=s(R)∪s(S)14.R是A上的關系，證明：如果R是對稱的，則r(R)也是對稱的。

15.I是整數(shù)集，R={(x,y)|x-y是3的倍數(shù)}，證明：R是I上的等價關系。

16.如果R是A上的等價關系，則A/R一定是A的劃分。17.R是集合A上的自反關系，S是A上的自反和對稱關系，證明t(R∪S)是A上的等價關系。18.I是正整數(shù)集合，R是I×I上的二元關系，R={<,>|xv=yu},證明：R是等價關系。

19.f:A?B，R是B上的等價關系，令S={|x?A且y?A且?R}，證明：S是A上的等價關系。

20.R是集合A上的自反關系，S是A上的自反和對稱關系，證明t(R∪S)是A上的等價關系。

21.P和Q都是集合A上的劃分，請問P∪Q，P-Q是否是A上的劃分，22.R?AXA,R[irref]且R[tra],證明：r(R)是A上的偏序關系。

23.畫出{1,2,3,4,6}上整除關系的哈斯圖，求{2,3,6}的4種元素。

24.A={a,b,c,d,e,f,g},R={(a,c),(a,e),(b,d),(b,f),(d,e),(d,f)},S=tr(R),畫出S的哈斯圖并求{b,c,d,f}的極大元等8種元素。

25.f:A→B,g:B→C都是單（滿）射，證明：復合映射gof一定是單（滿）射。

26.f:A→B,g:B→C，gof是單射，請問f和g是否一定是單射？請證明或舉出反例。27.R是實數(shù)集，f:R×R?R×R,f()=,請問f是否為單射？是否為滿射？分別證明或舉反例。28.已知B∩C=?,令f：P(B∪C)?P(B)×P(C)，對X?P(B∪C),令f(X)=(B∩X,C∩X),證明：f是雙射。

代數(shù)系統(tǒng)

1.是模8加群，Z8={0,1,2,3,4,5,6,7},+8是模8加法，求出的單位元、每個元素的逆元、所有的生成元和所有的子群。

2.求的單位元，零元，每個元素的逆元，每個元素的階，它是循環(huán)群嗎？求出它所有的子群。

3.R是實數(shù)集，在R上定義運算*為x*y=x+y+xy,問：是代數(shù)系統(tǒng)嗎？有單位元嗎？每個元素都有逆元嗎？ ***4.R是非零實數(shù)集合，是代數(shù)系統(tǒng)，對于R中元素*x,y，令xoy=2x+2y-2。請問中是否存在單位元、零元、哪些元素有逆元？運算o是否滿足交換律和結(jié)合律。分別說明理由。

5.R是實數(shù)集，R上的6運算定義如下：對R中元素x,y，f1()=x+y；f2()=x-y；f3()=xy；f4()=x/y；f5()=max{x,y}；f6()=|x-y|。問：哪些滿足交換律、結(jié)合律、有單位元、有零元？說明理由。

6.是一個群，證明：G是交換群當且僅當對任意G中222元素x,y,都有等式(xy)=xy成立。

7.證明：如果群G中每個元素的逆元素都是它自已，則G是交換群。

8.循環(huán)群一定是交換群。

9.證明：階為素數(shù)的群一定是循環(huán)群。

-110.是一個群，u?G,定義運算*：x*y=xouoy, 證明：是一個群。

11.整數(shù)集Z上定義運算*：對任意整數(shù)x和y,x*y=x+y-4,其中+，-為普通加減法。證明：是一個群。

12.證明：如果群G中至少有兩個元素，則群中沒有零元。13.S是G的子群，證明：{x|x是S的左陪集}是G的一個劃分

14.是一個群,a?G,n是a的階(周期)，證明：k<{a|k=0,2,…,n-1},o>是的一個子群。

15.H，K都是群G的子群，請問H∩K,H∪K,H-K是否一定是G的子群？ 16.H，K是G的兩個子群，a?G, 試證：aH?aK當且僅當H?K。17.G={1,3,4,5,9},*是模11的乘法(即x*y=xy mod 11)，請問(G,*)是否構(gòu)成群？

n18.是群，e是單位元，a?G,a的階為k,證明：a=e當且僅當 n是k的倍數(shù)。

19.S是G的子群，證明：{x|x是S的左陪集}是G的一個劃分

20.G是群，證明：S={a?G|?x?G(ax=xa)},則S是G的子群。21.是偶數(shù)階群，則G中必存在2階元素。22.證明：6個元素的群在同構(gòu)意義下只有兩個。

++23.R為實數(shù)集，R為正實數(shù)集，與是否同構(gòu)？ 24.是有限群，證明：G不可能表示成兩個真子群的并。25.圖論

1.如何判斷二部圖？完全圖、完全二部圖的邊數(shù)。2.如何求E回路？

3.Petersen圖是否為E圖或H圖。

4.哪些完全圖是H圖？哪些完全圖是E圖？ 5.n為何值時輪圖為H圖？ 6.如何求最小生成樹。

7.證明：奇數(shù)個頂點的二部圖（兩步圖）不是哈密爾頓圖。8.證明：如果G是歐拉圖，則其邊圖L(G)也是歐拉圖。9.證明：奇數(shù)個頂點的二部圖（兩步圖）不是哈密爾頓圖。10.G是平面圖，G有m條邊，n個頂點，證明：m?3n-6。并由此證明K5不是平面圖。

11.證明：有6個頂點的簡單無向圖G和它的補圖中至少有一個三角形。

12.證明：在至少有兩個頂點的無向樹中，至少有2個一度頂點。

13.G是無向簡單連通圖，G有n個頂點，則G最少有幾條邊，最多有幾條邊？

14.證明：簡單無向圖G和它的補圖中至少有一個是連通圖。15.證明：無向圖中奇度點（度數(shù)為奇數(shù)的點）有偶數(shù)個。16.證明：n個頂點的無向連通圖至少有n-1條邊。17.G是H圖，V是G的頂點集，證明：對任意頂點集S，??S?V，都有ω（G-S）≤|S|。其中ω（G-S）表示G-S的分圖數(shù)目。18.一棵無向樹有3個3次點，1個頂點次數(shù)為2，其余頂點次數(shù)為1，問它有幾個次數(shù)為1的頂點？寫出求解過程。19.證明：每個簡單平面圖都包含一個次至多為5的頂點。20.連通平面圖G有n個頂點，m條邊和f個面，證明：n-m+f=2。21.如果圖G的最大頂點次數(shù)≤ρ，證明：G是ρ+1可點著色的。

22.G是無向簡單連通圖，G有n個頂點，則G最少有幾條邊，最多有幾條邊？

23.如果一個簡單圖G和它的補圖同構(gòu)，則稱G是自補圖，求所有4個頂點自補圖。

24.G是平面圖，G有m條邊，n個頂點，證明：m?3n-6。如果G中無三角形，則m?2n-4。數(shù)理邏輯

1.如果今天是星期一，則要進行英語或數(shù)理邏輯考試。

沒有不犯錯誤的人。整數(shù)都是有理數(shù)。有的有理數(shù)不是整數(shù)。

不存在最大的整數(shù)。有且只有一個偶數(shù)是素數(shù)。2.求真值表及范式：P?(┓Q?R)、(┓Q?R)?(P?R)3.推理：

p?(q?r)，┓s∨p，q ├ s?r p?r，q?s，p∨q ├ r∨s p∨q，p?┓r，s?t，┓s?r，┓t ├ q p?(┓(r∧s)?┓q),p,┓s ├ ┓q 4.如果小王是理科學生，他一定會學好數(shù)學。如果小王不是文科學生，他一定是理科學生。小王沒學好數(shù)學。所以小王是文科學生。

5.判斷各公式在給定解釋時的真假值，并且改變論域使該公式在新的解釋下取值相反。論域：D={-2,3,6}, F(x):x≤3, G(x):x>5, R(x,y):x+y<4 ①?x(F(x)∨G(x))②?y?yR(x,y)

第四篇：離散數(shù)學及其應用集合論部分課后習題答案

作業(yè)答案：集合論部分

P90:習題六

5、確定下列命題是否為真。（2）???（4）??{?}

（6）{a,b}?{a,b,c,{a,b}} 解答：（2）假（4）真（6）真

8、求下列集合的冪集。（5）{{1,2},{2,1,1},{2,1,1,2}}（6）{{?,2},{2}} 解答：

（5）集合的元素彼此互不相同，所以{2,1,1,2}?{1,2}，所以該題的結(jié)論應該為

{?,{{1,2}},{{2,1,1}},{{1,2},{2,1,1}}}

（6）{?,{{?,2}},{{2}},{{?,2},{2}}}

9、設E?{1,2,3,4,5,6}，A?{1,4}，B?{1,2,5},C?{2,4},求下列集合。（1）A（2）解答：（1）A（2）

31、設A,B,C為任意集合，證明 B

(AB)

B?{1,4}{3,4,6}?{4}

(AB)?{1}?{2,3,4,5,6}

(A?B)證明：

(B?A)?(AB)?(AB)

(A?B)(B?A)?{x|x?A?B?x?B?A}?{x|(x?A?x?B)?(x?B?x?A)}?{x|(x?A?x?B)?(x?B?x?B)?(x?A?x?A)?(x?B?x?A)} ?{x|(x?A?x?B)?(x?B?x?A)}?{x|(x?A?{x|(x?A?A

B)?(x?A?x?B)}?{x|(x?AB)?(x?ABB)}?{x|(x?AB)?(x?A?x?B)}B)}B)?(x?AB?A34、設A,B為集合，證明：如果(A?B)證明：（反證法）

設a?A(B?A)?AB，則AB??。

B，則a?A,a?B，所以a?A?B,a?B?A； 所以a?(A?B)但是a?A與(A?B)

37、設A,B,C為任意集合，證明：C?A?C?B?C?(A證明：

對任意x?C，由于C?A,C?B，所以x?A且x?B所以x?A因此，C?(A

(B?A)

B矛盾。

B)。

B B。

(B?A)?AB)。

P121:習題七

5、設A,B為任意集合，證明

若A?A?B?B，則A?B。

證明：

x?A??x,x??A?A

??x,x??B?B?x?B所以有A?B

9、設A?{1,2,4,6}，列出下列關系R（2）R?{?x,y?|x,y?A?|x?y|?1}（3）R?{?x,y?|x,y?A?y為素數(shù)} 解答：

11、Ri是X上的二元關系，對于x?X定義集合（2）R?{?1,2?,?2,1?}

（3）R?{?1,2?,?2,2?,?4,2?,?6,2?}

Ri(x)?{y|xRy}

顯然Ri(x)?X。如果X?{?4,?3,?2,?1,0,1,2,3,4},且令

R1?{?x,y?|x,y?X?x?y}

R2?{?x,y?|x,y?X?y?1?x?y?2} R3?{?x,y?|x,y?X?x2?y}

求R1(0),R1(1),R2(0),R2(?1),R3(3)。解答：

R1(0)?{1,2,3,4}R1(1)?{2,3,4}R2(0)?{?1,0}R2(?1)?{?2,?1}R3(3)??，B?{?1,3?,?2,4?,?4,2?}。求A13、設A?{?1,2??,2,4,??3,3}?

B，AB，domA,domB,dom(A解答：

B),ranA,ranB,ran(AB),fld(A?B).AAB?{?1,2?,?2,4?,?3,3?,?1,3?,?4,2?} B?{?2,4?}

domA?{1,2,3} domB?{1,2,4} dom(AB)?{1,2,3,4}

ranA?{2,3,4} ranB?{2,3,4} ran(A B)?{4}

fld(A?B)?{1,2,3}

16、設A?{a,b,c,d}，R1,R2為A上的關系，其中

R1?{?a,a?,?a,b?,?b,d?}，R2?{?a,d?,?b,c?,?b,d?,?c,b?}。求R1R2，R2R1，R12，R23。

解答：

R1R2?{?a,d?,?a,c?,?a,d?} R2R1?{?c,d?}

R12?{?a,a?,?a,b?,?a,d?} R22?{?b,b?,?c,c?,?c,d?} R23?{?b,c?,?b,d?,?c,b?}

20、給定A?{1,2,3,4}，A上的關系R?{?1,3?,?1,4?,?2,3?,?2,4?,?3,4?}（1）畫出R的關系圖。（2）說明R的性質(zhì)。解答：

（1）

（2）R具有反自反性，反對稱性，傳遞性

21、設A?{1,2,3}，圖7.11給出12種A上的關系，對于每種關系寫出相應的關系矩陣，并說明它所具有的性質(zhì)。

解答：

?110???（a）111,具有自反性。????101???110???（b）001,具有反對稱性和傳遞性。????100???111???（c）111,具有自反性，對稱性和傳遞性。????111??

23、設R的關系圖如圖7.12所示，試給出r(R)，s(R)和t(R)的關系圖。

25、設A?{1,2,3,4}，R是A上的等價關系，且R是A上所構(gòu)成的等價類為{1},{2,3,4}。（1）求R。（2）求RR（3）求R傳遞閉包。解答：

（1）R?{?1,1?,?2,2?,?3,3?,?4,4?,?2,3?,?3,2?,?2,4?,?4,2?,?3,4?, ?1?4,3?}

（2）由于等價關系滿足對稱性，所以R所以RR?1?1?R

?R

（3）由于等價關系滿足傳遞性，所以傳遞閉包為其自身，即t(R)?R

26、對于給定的A和R，判斷R是否為A上的等價關系。（1）A為實數(shù)集，?x,y?A,xRy?x?y?2。（2）A?{1,2,3}，?x,y?A,xRy?x?y?3。（3）A?Z，?x,y?A,xRy?xy為奇數(shù)。

（5）A?P(X),C?X，?x,y?A,xRy?x?y?C 解答：

（1）不是，不滿足自反性、對稱性、傳遞性。（2）不是，由于A?{1,2,3}集合較小，①自反性：?x?A,x?x?3??x,x??R

②對稱性，??x,y??R,x?y?3?y?x?3??y,x??R 但是傳遞性不滿足，?1,3?,?3,2??R，但是?1,2??R。?（3）不是，滿足對稱性、傳遞性，但是不滿足自反性 取x?2，但是2?2?4不為奇數(shù)，所以?2,2??R。

（5）滿足

①自反性：?x?A?x?X?x?x???C??x,x??R ②對稱性：??x,y??R?y?x?x?y?C??y,x??R ③傳遞性：??x,y?,?y,z??R

?x?y?C,y?z?C ?(x?y)?(y?x)?C,(y?z)?(z?y)?C?(x?y)?C,(y?x)?C,(y?z)?C,(z?y)?C下面證明(x?z)?C

?a?(x?z)?a?x,a?z

若a?y，則a?y?z，所以a?C 若a?y，則a?x?y，所以a?C

所以(x?z)?C，同理可證，(z?x)?C 所以x?z?(x?z)?(z?x)?C 所以?x,z??R。因此滿足傳遞性。

27、設A?{a,b,c,d},A上的等價關系

R?{?a,b?,?b,a?,?c,d?,?d,c?}?IA

畫出R的關系圖，并求出A中各元素的等價類。解答：關系圖為

等價類[a]?[b]?{a,b}；[c]?[d]?{c,d}

30、設A?{1,2,3,4},，在A?A上定義二元關系R，??u,v?,?x,y??A?A,?u,v?R?x,y??u?y?x?v。

（1）證明R為A?A上的等價關系。（2）確定由R引起的對A?A的劃分。解答：（1）證明：

①自反性：??x,y??A?A，由于x?y?x?y，所以??x,y?,?x,y???R； ②對稱性：???x,y?,?u,v???R

有x?v?u?y，所以u?y?x?v 因此??u,v?,?x,y???R

③傳遞性：???x,y?,?u,v??,??u,v?,?s,t???R

有x?v?u?y，u?t?s?v，所以x?s?t?y 因此??x,y?,?s,t???R。

（2）等價類有

[?1,1?]?{?1,1?,?2,2?,?3,3?,?4,4?} [?1,2?]?{?1,2?,?2,3?,?3,4?} [?1,3?]?{?1,3?,?2,4?} [?1,4?]?{?1,4?} [?2,1?]?{?2,1?,?3,2?,?4,3?} [?3,1?]?{?3,1?,?4,2?} [?4,1?]?{?4,1?}

37、對于下列集合與整除關系畫出哈斯圖。（1）{1,2,3,4,6,8,12,24}（2）{1,2,3,4,5,6,7,8,9,10,11,12} 解答：（1）

（2）

38、針對圖7.14中的每個哈斯圖，寫出集合以及偏序關系的表達式。

解答：

（a）集合為A?{1,2,3,4,5}，偏序關系為{?1,3?,?1,5?,?2,4?,?2,5?,?3,5?,?4,5?}?IA（b）集合為B?{a,b,c,d,e,f}，偏序關系為{?a,b?,?c,d?,?e,f?}?IB（c）集合為C?{1,2,3,4,5}，偏序關系{?1,2?,?1,3?,?1,4?,?1,5?,?2,4?,?2,5?,?3,4?,?3,5?,?4,5?}?IC

40、分別畫出下列偏序集?A,R??的哈斯圖，并找出A的極大元、極小元、最大元和最小元。

（1）A?{a,b,c,d,e,f}，R??{?a,d?,?a,c?,?a,b?,?a,e?,?b,e?,?c,e?,?d,e?}?IA

R??{?c,d?}?IA（2）A?{a,b,c,d,e}

解答：

（1）哈斯圖為

極小元為a,f,極大元為e,f，無最大元、最小元（2）哈斯圖為

極小元為a,b,c,e，極大元為a,b,d,e，無最大元、最小元

41、A?{1,2,3....,12}，R為整除關系，B?{x|2?x?4}，在偏序集?A,R?中求B的上界、下界、最小上界和最大下界。

解：下界即為公約數(shù)，2，3，4的公約數(shù)只有1，所以下界為1，最大下界也為1；

下界即為公倍數(shù)，2，3，4的公倍數(shù)只有12，所以上界為1，最大上界也為12；

P141:習題八

4、判斷下列函數(shù)中哪些是滿射？哪些是單射？哪些是雙射？（2）f:N?N,f(x)?x2?2（4）f:N?{0,1},f(x)???0?1xisodd

xiseven（6）f:R?R,f(x)?x2?2x?15

解答：（2）單射；（3）滿射；（4）既不為單射也不為滿射。

{1,2,3}

5、設X?{a,b,c,d},Y?，f?{?a,1?,?b,2?,?c,3?}，判斷下列命題的真假。

（1）f是從X到Y(jié)的二元關系，但不是X到Y(jié)的函數(shù)。（3）f是從X到Y(jié)的滿射，但不是單射。解答：（1）真；（3）假

15、設A?{a,b,c}，R為A上的等價關系，且R?{?a,b?,?b,a?}?IA，求自然映射g:A?A/R。

解答： A/R?{{a,b},{c}}

?{a,b}g(x)???cx?a,b x?c19、設f,g是從N到N的函數(shù)，且

?x?1?f(x)??0?x?（1）求f（2）說明f解答： x?0,1,2,3x?4x?5g

?x?

g(x)??2??3xiseven

xisoddg是否為單射、滿射、雙射？

（1）f?3?x?1??g?g(f(x))??2?0?x??2x?0,2,5,7,9......x?1,3x?4x?6,8,10,12.....（2）為滿射，但是不為單射。

20、設f:N?N?N，f(x)??x,x?1?（1）說明f是否為單射和滿射，說明理由。

（2）f的反函數(shù)是否存在，如果存在，求出f的反函數(shù)；（3）求ranf。解答：

（1）x?y時，?x,x?1???y,y?1?，所以為單射； 而對?1,3??N?N，不存在x?N，使得f(x)??x,x?1?，所以不為滿射。

（2）不存在反函數(shù)，因為不是雙射函數(shù)；（3）ranf?{?x,x?1?|x?N}

22、對于以下集合A和B，構(gòu)造從A到B的雙射函數(shù)。（1）A?{1,2,3},B?{a,b,c}（2）A?(0,1),B?(0,2)

（3）A?{x|x?Z?x?0},B?N（4）A?R,B?R 解答： ??a?（1）f(x)??b?c?（2）f(x)?2xx?1x?2 x?3x?(0,1)（3）f(x)??x?1

（4）f(x)?ax(a?0,a?1)

第五篇：離散數(shù)學習題及答案

離散數(shù)學考試試題（A卷及答案）

一、（10分）某項工作需要派A、B、C和D 4個人中的2個人去完成，按下面3個條件，有幾種派法？如何派？

(1)若A去，則C和D中要去1個人；

(2)B和C不能都去；

(3)若C去，則D留下。

解設A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據(jù)題意應有：A?C?D，?(B∧C)，C??D必須同時成立。因此

(A?C?D)∧?(B∧C)∧(C??D)

?(?A∨(C∧? D)∨(?C∧D))∧(?B∨?C)∧(?C∨?D)

?(?A∨(C∧? D)∨(?C∧D))∧((?B∧?C)∨(?B∧?D)∨?C∨(?C∧?D))

?(?A∧?B∧?C)∨(?A∧?B∧?D)∨(?A∧?C)∨(?A∧?C∧?D)

∨(C∧? D∧?B∧?C)∨(C∧? D∧?B∧?D)∨(C∧? D∧?C)∨(C∧? D∧?C∧?D)∨(?C∧D∧?B∧?C)∨(?C∧D∧?B∧?D)∨(?C∧D∧?C)∨(?C∧D∧?C∧?D)

?F∨F∨(?A∧?C)∨F∨F∨(C∧? D∧?B)∨F∨F∨(?C∧D∧?B)∨F∨(?C∧D)∨F ?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D∧?B)∨(?C∧D)

?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D)

?T

故有三種派法：B∧D，A∧C，A∧D。

二、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：某學術會議的每個成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。

解：論域：所有人的集合。S(x)：x是專家；W(x)：x是工人；Y(x)：x是青年人；則推理化形式為：

?x(S(x)∧W(x))，?xY(x)?x(S(x)∧Y(x))

下面給出證明：

(1)?xY(x)P

(2)Y(c)T(1)，ES

(3)?x(S(x)∧W(x))P

(4)S(c)∧W(c)T(3)，US

(5)S(c)T(4)，I

(6)S(c)∧Y(c)T(2)(5)，I

(7)?x(S(x)∧Y(x))T(6)，EG

三、（10分）設A、B和C是三個集合，則A?B??(B?A)。

證明：A?B??x(x∈A→x∈B)∧?x(x∈B∧x?A)??x(x?A∨x∈B)∧?x(x∈B∧x?A)

???x(x∈A∧x?B)∧??x(x?B∨x∈A)???x(x∈A∧x?B)∨??x(x∈A∨x?B)

??(?x(x∈A∧x?B)∧?x(x∈A∨x?B))??(?x(x∈A∧x?B)∧?x(x∈B→x∈A))

??(B?A)。

四、（15分）設A＝{1，2，3，4，5}，R是A上的二元關系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}

s(R)＝R∪R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}

R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}

R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R

t(R)＝?Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，i?1?4232－

15>}。

五、（10分）R是非空集合A上的二元關系，若R是對稱的，則r(R)和t(R)是對稱的。

證明對任意的x、y∈A，若xr(R)y，則由r(R)＝R∪IA得，xRy或xIAy。因R與IA對稱，所以有yRx或yIAx，于是yr(R)x。所以r(R)是對稱的。

下證對任意正整數(shù)n，R對稱。

因R對稱，則有xRy??z(xRz∧zRy)??z(zRx∧yRz)?yRx，所以R對稱。若Rn對稱，則xRn?1y??z(xRnz∧zRy)??z(zRnx∧yRz)?yRn?1x，所以Rn?1對稱。因此，對任意正整數(shù)n，Rn對稱。對任意的x、y∈A，若xt(R)y，則存在m使得xRy，于是有yRx，即有yt(R)x。因此，t(R)是對稱的。

六、（10分）若f：A→B是雙射，則f：B→A是雙射。

證明因為f：A→B是雙射，則f是B到A的函數(shù)。下證f是雙射。

對任意x∈A，必存在y∈B使f(x)＝y(tǒng)，從而f(y)＝x，所以f是滿射。

對任意的y1、y2∈B，若f(y1)＝f(y2)＝x，則f(x)＝y(tǒng)1，f(x)＝y(tǒng)2。因為f：A→B是函數(shù)，則y1＝y(tǒng)2。所以f是單射。

綜上可得，f：B→A是雙射。

七、（10分）設是一個半群，如果S是有限集，則必存在a∈S，使得a*a＝a。

證明因為是一個半群，對任意的b∈S，由*的封閉性可知，b＝b*b∈S，b＝b*b∈S，…，bn∈S，…。

因為S是有限集，所以必存在j＞i，使得bi＝bj。令p＝j－i，則bj＝bp*bj。所以對q≥i，有bq＝bp*bq。

因為p≥1，所以總可找到k≥1，使得kp≥i。對于bkp∈S，有bkp＝bp*bkp＝bp*(bp*bkp)＝…＝232－1－1－1－1－1－1－1－1－1mm222nbkp*bkp。

令a＝bkp，則a∈S且a*a＝a。

八、（20分）（1）若G是連通的平面圖，且G的每個面的次數(shù)至少為l(l≥3)，則G的邊數(shù)m與結(jié)點數(shù)n有如下關系：

m≤

rl(n－2)。l?2l證明設G有r個面，則2m＝

2)。?d(f)≥lr。由歐拉公式得，n－m＋r＝2。于是，m≤l?2(n－ii?

1（2）設平面圖G＝是自對偶圖，則| E|＝2(|V|－1)。

證明設G＝是連通平面圖G＝的對偶圖，則G? G，于是|F|＝|V*|＝|V|，將其代入歐拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。**

離散數(shù)學考試試題（B卷及答案）

一、（10分）證明(P∨Q)∧(P?R)∧(Q?S)S∨R

證明因為S∨R??R?S，所以，即要證(P∨Q)∧(P?R)∧(Q?S)?R?S。

(1)?R附加前提

(2)P?RP

(3)?PT(1)(2)，I

(4)P∨QP

(5)QT(3)(4)，I

(6)Q?SP

(7)ST(5)(6)，I

(8)?R?SCP

(9)S∨RT(8)，E

二、（15分）根據(jù)推理理論證明：每個考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。

設P(e)：e是考生，Q(e)：e將有所作為，A(e)：e是勤奮的，B(e)：e是聰明的，個體域：人的集合，則命題可符號化為：?x(P(x)?(A(x)∨B(x)))，?x(A(x)?Q(x))，??x(P(x)?Q(x))?x(P(x)∧B(x))。

(1)??x(P(x)?Q(x))P

(2)??x(?P(x)∨Q(x))T(1)，E

(3)?x(P(x)∧?Q(x))T(2)，E

(4)P(a)∧?Q(a)T(3)，ES

(5)P(a)T(4)，I

(6)?Q(a)T(4)，I

(7)?x(P(x)?(A(x)∨B(x))P

(8)P(a)?(A(a)∨B(a))T(7)，US

(9)A(a)∨B(a)T(8)(5)，I

(10)?x(A(x)?Q(x))P

(11)A(a)?Q(a)T(10)，US

(12)?A(a)T(11)(6)，I

(13)B(a)T(12)(9)，I

(14)P(a)∧B(a)T(5)(13)，I

(15)?x(P(x)∧B(x))T(14)，EG

三、（10分）某班有25名學生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2人會打這三種球。而6個會打網(wǎng)球的人都會打另外一種球，求不會打這三種球的人數(shù)。

解設A、B、C分別表示會打排球、網(wǎng)球和籃球的學生集合。則：

|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。

因為|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩

B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|A?B?C|＝25－20＝5。故，不會打這三種球的共5人。

四、（10分）設A1、A2和A3是全集U的子集，則形如?Ai?(Ai?為Ai或Ai)的集合稱為由A1、A2和

i?1

3A3產(chǎn)生的小項。試證由A1、A2和A3所產(chǎn)生的所有非空小項的集合構(gòu)成全集U的一個劃分。

證明小項共8個，設有r個非空小項s1、s2、…、sr(r≤8)。

對任意的a∈U，則a∈Ai或a∈Ai，兩者必有一個成立，取Ai?為包含元素a的Ai或Ai，則a∈?Ai?，i?13即有a∈?si，于是U??si。又顯然有?si?U，所以U＝?si。

i?1i?1i?1i?1rrrr

任取兩個非空小項sp和sq，若sp≠sq，則必存在某個Ai和Ai分別出現(xiàn)在sp和sq中，于是sp∩sq＝?。綜上可知，{s1，s2，…，sr}是U的一個劃分。

五、（15分）設R是A上的二元關系，則：R是傳遞的?R*R?R。

證明(5)若R是傳遞的，則∈R*R??z(xRz∧zSy)?xRc∧cSy，由R是傳遞的得xRy，即有∈R，所以R*R?R。

反之，若R*R?R，則對任意的x、y、z∈A，如果xRz且zRy，則∈R*R，于是有∈R，即有xRy，所以R是傳遞的。

六、（15分）若G為連通平面圖，則n－m＋r＝2，其中，n、m、r分別為G的結(jié)點數(shù)、邊數(shù)和面數(shù)。證明對G的邊數(shù)m作歸納法。

當m＝0時，由于G是連通圖，所以G為平凡圖，此時n＝1，r＝1，結(jié)論自然成立。

假設對邊數(shù)小于m的連通平面圖結(jié)論成立。下面考慮連通平面圖G的邊數(shù)為m的情況。

設e是G的一條邊，從G中刪去e后得到的圖記為G?，并設其結(jié)點數(shù)、邊數(shù)和面數(shù)分別為n?、m?和r?。對e分為下列情況來討論：

若e為割邊，則G?有兩個連通分支G1和G2。Gi的結(jié)點數(shù)、邊數(shù)和面數(shù)分別為ni、mi和ri。顯然n1＋n2＝n?＝n，m1＋m2＝m?＝m－1，r1＋r2＝r?＋1＝r＋1。由歸納假設有n1－m1＋r1＝2，n2－m2＋r2＝2，從而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不為割邊，則n?＝n，m?＝m－1，r?＝r－1，由歸納假設有n?－m?＋r?＝2，從而n－(m－1)＋r－1＝2，即n－m＋r＝2。

由數(shù)學歸納法知，結(jié)論成立。

七、（10分）設函數(shù)g：A→B，f：B→C，則：

(1)f?g是A到C的函數(shù)；

(2)對任意的x∈A，有f?g(x)＝f(g(x))。

證明(1)對任意的x∈A，因為g：A→B是函數(shù)，則存在y∈B使∈g。對于y∈B，因f：B→C是函數(shù)，則存在z∈C使∈f。根據(jù)復合關系的定義，由∈g和∈f得∈g*f，即∈f?g。所以Df?g＝A。

對任意的x∈A，若存在y1、y2∈C，使得、∈f?g＝g*f，則存在t1使得∈g且∈f，存在t2使得∈g且∈f。因為g：A→B是函數(shù)，則t1＝t2。又因f：B→C是函數(shù)，則y1＝y(tǒng)2。所以A中的每個元素對應C中惟一的元素。

綜上可知，f?g是A到C的函數(shù)。

(2)對任意的x∈A，由g：A→B是函數(shù)，有∈g且g(x)∈B，又由f：B→C是函數(shù)，得∈f，于是∈g*f＝f?g。又因f?g是A到C的函數(shù)，則可寫為f?g(x)＝f(g(x))。

八、（15分）設是的子群，定義R＝{|a、b∈G且a1*b∈H}，則R是G中的－

一個等價關系，且[a]R＝aH。

證明對于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。－－

若∈R，則a1*b∈H。因為H是G的子群，故(a1*b)1＝b1*a∈H。所以∈R。－－－－

若∈R，∈R，則a1*b∈H，b1*c∈H。因為H是G的子群，所以(a1*b)*(b1*c)＝a－－－－

－1*c∈H，故∈R。

綜上可得，R是G中的一個等價關系。

對于任意的b∈[a]R，有∈R，a1*b∈H，則存在h∈H使得a1*b＝h，b＝a*h，于是b∈aH，－－

[a]R?aH。對任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH?[a]R。所以，[a]R－

＝aH。