華南理工網(wǎng)絡教育離散數(shù)學同步練習冊.doc

《華南理工網(wǎng)絡教育離散數(shù)學同步練習冊.doc》由會員分享，可在線閱讀，更多相關(guān)《華南理工網(wǎng)絡教育離散數(shù)學同步練習冊.doc（30頁珍藏版）》請在裝配圖網(wǎng)上搜索。

離散數(shù)學 同步練習冊 學　　號＿＿＿＿＿＿＿＿ 　　　姓　　名＿＿＿＿＿＿＿＿ 　　　?！　I(yè)＿＿＿＿＿＿＿＿ 　　　教學中心＿＿＿＿＿＿＿＿ 華南理工大學 二O一O年九月 第一章命題邏輯 一填空題 （1）設：p：派小王去開會。q：派小李去開會。則命題： “派小王或小李中的一人去開會” 可符號化 為： p∨q 。 （2）設A，B都是命題公式，AB，則AB的真值是 T 。 （3）設：p：劉平聰明。q：劉平用功。在命題邏輯中，命題： “劉平不但不聰明，而且不用功” 可符號化為： ﹃p∧﹃q 。 （4）設A , B 代表任意的命題公式，則蘊涵等值式為 A B ﹃P(guān)∨Q 。 （5）設，p：徑一事；q：長一智。在命題邏輯中，命題： “不徑一事，不長一智?！?可符號化為： ﹃p→﹃q 。 （6）設A , B 代表任意的命題公式，則德 摩根律為 （A B） ﹃A∨﹃B 　　　 。 （7）設，p：選小王當班長；q：選小李當班長。則命題：“選小王或小李中的一人當班長?！?可符號化為： (A∧﹃B) ∨(﹃A∧B) 。 （8）設，P：他聰明；Q：他用功。在命題邏輯中，命題： “他既聰明又用功?！?可符號化為： P∧Q 。 （9）對于命題公式A，B，當且僅當 A→B 是重言式時，稱“A蘊含B”，并記為AB 。 （10）設：P：我們劃船。Q：我們跑步。在命題邏輯中，命題： “我們不能既劃船又跑步?！?可符號化為： ﹃(P∧Q) 。 （11）設P , Q 是命題公式，德摩根律為： （P Q） ﹃P(guān)∧﹃Q 。 （12）設 P：你努力。Q：你失敗。在命題邏輯中，命題：“除非你努力，否則你將失敗。 ” 可符號化為： ﹃P(guān)→Q 。 （13）設 p：小王是100米賽跑冠軍。q：小王是400米賽跑冠軍。在命題邏輯中，命題：“小王是100米或400米賽跑冠軍。 ” 可符號化為： p∨q 。 （4）設A，C為兩個命題公式，當且僅當 A C 為一重言式時，稱C可由A邏輯地推出 。 二．判斷題 1. 設A，B是命題公式，則蘊涵等值式為ABAB。 （ F ） 2. 命題公式pqr是析取范式。 （ T ） 3. 陳述句“x + y > 5” 是命題。 （ T ） 4. 110 (p=1,q=1, r=0)是命題公式 (((pq))r)q 的成真賦值。 （ T ） 5. 命題公式 p(pq) 是重言式。 （ F ） 6. 設A，B都是合式公式，則ABB也是合式公式。 （ F ） 7. A(BC)( AB)(AC)。 （ F ） 8. 陳述句“我學英語，或者我學法語” 是命題。 （ T ） 9. 命題“如果雪是黑的，那么太陽從西方出”是假命題。 （ T ） 10. “請不要隨地吐痰！” 是命題。 （ F ） 11. P Q P Q 。 （ F ） 12. 陳述句“如果天下雨，那么我在家看電視” 是命題。 （ T ） 13. 命題公式（PQ）（RT）是析取范式。 （ T ） 14. 命題公式 (PQ) R (PQ) 是析取范式。 （ T ） 三、選擇題：在每小題的備選答案中只有一個正確答案，將正確答案序號填入下列敘述中的 內(nèi)。 1． 設：P：天下雪。Q：他走路上班。則命題“只有天下雪，他才走路上班?！笨煞柣癁? （1） 。 （1）PQ （2）Q P （3） Q P （4）Q P 2． (1 ) 明年國慶節(jié)是晴天。 (2 ) 在實數(shù)范圍內(nèi)，x+y〈3。 (3 ) 請回答這個問題！ (4 ) 明天下午有課嗎？ 在上面句子中，是命題的只有 (2 ) 。 3． 命題公式A與B是等值的，是指 (4 ) 。 （1） A與B有相同的命題變元 （2） AB是可滿足式 （3） AB為重言式 （4） AB為重言式 4． (1 ) 雪是黑色的。 (2 ) 這朵花多好看呀！。 (3 ) 請回答這個問題！ (4 ) 明天下午有會嗎？ 在上面句子中，是命題的是 (1 ) 。 5． 設：P：天下大雨。Q：他乘公共汽車上班。則命題“只要天下大雨，他就乘公共汽車上班?！? 可符號化為 （2） 。 （1）QP （2）P Q （3） Q P （4）Q P 6． 設：P：你努力；Q：你失敗。則命題“除非你努力，否則你將失敗?！? 在命題邏輯中可符號化為 （3） 。 （1）QP （2）P Q （3） P Q （4）Q P 7． (1 ) 現(xiàn)在開會嗎？ (2 ) 在實數(shù)范圍內(nèi)，x+y >5。 (3 ) 這朵花多好看呀！ (4 ) 離散數(shù)學是計算機科學專業(yè)的一門必修課。 在上面語句中，是命題的只有 (2 ) 。 8． 設：P：天氣好。Q：他去郊游。則命題“如果天氣好，他就去郊游?！? 可符號化為 （1） （1）PQ （2）Q P （3） Q P （4）Q P 9． 下列式子是合式公式的是 （4） 。 （1）（P Q） （2） （P （Q R）） （3）（P Q） （4） Q R 10． （1）1＋101＝110 （2） 中國人民是偉大的。 （3） 全體起立！ （4） 計算機機房有空位嗎？ 在上面句子中，是命題的是 （1） 。 11． 設：P：他聰明；Q：他用功。則命題“他雖聰明但不用功?！? 在命題邏輯中可符號化為 （4） 。 （1）P Q （2）P Q （3）P Q （4）P Q 12． (1 ) 如果天氣好，那么我去散步。 (2 ) 天氣多好呀！ (3 ) x=3。 (4 ) 明天下午有會嗎？ 在上面句子中 (1 ) 是命題。 13． 設：P：王強身體很好；Q：王強成績很好。命題“王強身體很好，成績也很好?！痹诿}邏輯中可符號化為 （4） 。 （1）P Q （2）P Q （3）P Q （4）P Q 四、解答題 1．設命題公式為（pq）（qp）?！? （1）求此命題公式的真值表； （2）給出它的析取范式； （3）判斷該公式的類型。 （1） P q p q pq qp （pq）（qp） T T F F T F F T F F T T T T F T T F T T T F F T T F T T （2）（p q）p q （3）可滿足式 2．設命題公式為（p q）（p r）?！? （1）求此命題公式的真值表； （2）給出它的析取范式； （3）判斷該公式的類型。 （1） p q r pq p r （p q）（p r） T T T T T T T T F T T T T F T F T F T F F F T F F T T T T T F T F T T T F F T T T T F F F T F F (2)(pq) ( p r) (pr) (3) 可滿足式 3．設命題公式為 Q （P Q） P。　 （1）求此命題公式的真值表； （2）求此命題公式的析取范式； （3）判斷該命題公式的類型。 （1） P Q P Q P Q （P Q） P Q （P Q） P T T F F T T F T F F T F T T F T T F T T F F F T T T F F (2) P（P Q） (3) 可滿足式 4．完成下列問題　 （1）求此命題公式 Q （P Q） P 的真值表； （2）求命題公式（P∧（Q→R））→S的析取范式。 （1）同上表 （2） P(Q R) S 5．設命題公式為（P （P Q）） Q?！? （1）求此命題公式的真值表； （2）判斷該公式的類型。 （1） P Q P Q P （P Q） （P （P Q）） Q T T T T T T F F F T F T T F F F F T F F (2) 可滿足式 6．設命題公式為（（P Q）P） Q?！? （1）求此命題公式的真值表； （2）給出它的析取范式； （3）判斷該公式的類型。 (1) P Q P P Q （P Q）P （（P Q）P） Q T T F T F T T F F T F T F T T T T T F F T F F T (2) P Q(P Q) (3)重言式 7．用直接證法證明 前提：P Q，P R，Q S 結(jié)論：S R 證明： 8．用直接證法證明 前提：P (Q R)，S Q，P，S。 結(jié)論：R 證明：S Q，S推出 Q （假言推論） P (Q R)，P推出Q R （假言推論） Q ，Q R推出R （析取三段論） 第二章謂詞邏輯 一填空題 （1）若個體域是含三個元素的有限域{a，b，c}，則 A(x) A(a)A(b)A(c) （2）取全總個體域，令F(x)：x為人,G(x)：x愛看電影。則命題“沒有不愛看電影的人?！笨煞柣癁開_($x_(F(x)_ G(x)))_________________________________。 （3）若個體域是含三個元素的有限域{a，b，c}，則 "xA(x) A(a) A(b) A(c) 。 （4）取全總個體域，令M(x)：x是人,G(y)：y是花, H(x,y)：x喜歡y。則命題“有些人喜歡所有的花?！笨煞柣癁開$x$y (_M(x) H(x,y) G(y))_______________________。 （5）取個體域為全體人的集合。令F(x)：x在廣州工作,G(x)：x是廣州人。在一階邏輯中，命題“在廣州工作的人未必都是廣州人?！笨煞柣癁開$x (F(x) G(x))____________________________________。 （6）P(x)：x是學生，Q(x)：x要參加考試。在謂詞邏輯中，命題： “每個學生都要參加考試” 可符號化為："x(P(x) Q(x) ) 。 （7）M(x)：x是人，B(x)：x勇敢。則命題“有人勇敢，但不是所有的人都勇敢”謂詞符號化為 _$x (M(x) B(x)) ("x(M(x) B(x)))__________________________________________。 （8）P(x)：x是人，M(x)：x聰明。則命題“盡管有人聰明，但不是一切人都聰明”謂詞符號化為 _$x (P(x) M(x)) ("x(P(x) M(x)))_________________________________________。 （9）I(x)：x是實數(shù)，R(x)：x是正數(shù)，N(x)：x是負數(shù)。在謂詞邏輯中，命題： “任何實數(shù)或是正的或是負的” 可符號化為："x(I(x) R(x) R(x) 。 （10）P(x)：x是學生，Q(x)：x要參加考試。在謂詞邏輯中，命題： “每個學生都要參加考試” 可符號化為："x(P(x) Q(x) ) 。 （11）令M(x)：x是大學生,P(y)：y是運動員, H(x, y)：x欽佩y。則命題“有些大學生不欽佩所有運動員?！笨煞柣癁? __$x"y(M(x) P(y) H(x, y)) ______________ _______。 二．判斷題 1. 設A，B都是謂詞公式，則"x AB也是謂詞公式。 （ T ） 2. 設c是個體域中某個元素，A是謂詞公式，則A(c) "xA(x)。 （ F ） 3. "x"yA(x,y) "y"xA(x,y) 。 （ T ） 4. "x$yA(x,y) $y"xA(x,y) 。 （ F ） 5. 取個體域為整數(shù)集，則謂詞公式"x"y(x y = y ) 是假命題。 （T ） 6. ("x)（P(x)Q(x)） ("x)（P(x) Q(x)）。 （T ） 7. 命題公式 (PQ R) (PQ) 是析取范式。 （ F ） 8. 謂詞公式("x)(A (x) B(x, y)) R(x) 的自由變元為x, y。 （ F ） 9. （（"x）A（x） B）（$x）（A（x） B）。 （F ） 10. R(x)：“x是大學生?！?是命題。 （T ） 三、選擇題：在每小題的備選答案中只有一個正確答案，將正確答案序號填入下列敘述中的 內(nèi)。 1．設F（x）：x是火車，G（x）：x是汽車，H（x，y）：x比y快。命題“某些汽車比所有火車慢”的符號化公式是 (2) 。 （1） $y（G（y）"x（F（x）H（x，y））） （2） $y（G（y）"x（F（x）H（x，y））） （3） "x $y（G（y）（F（x）H（x，y））） （4） $y（G（y）"x（F（x）H（x，y））） 2．設個體域為整數(shù)集，下列真值為真的公式是 (3) 。 （1）$y"x (x – y =2) （2）"x"y(x – y =2) （3）"x$y(x – y =2) （4）$x"y(x – y =2) 3．設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）） 5．下列式子中正確的是 (4) 。 （1）（"x）P（x）（$x）P（x） （2）（"x）P（x）（"x） P（x） （3）（$x）P（x）（$x） P（x） （4）（$x）P（x）（"x） P（x） 6．下面謂詞公式是永真式的是　　(d) 　　　　　　。 a) P（x） Q（x） b) （"x）P（x）（$x）P（x） c) P（a）（"x）P（x） d) P（a）（$x）P（x） 5． 設S（x）：x是運動員，J（y）：y是教練員，L（x，y）：x欽佩y。命題“所有運動員都欽佩一些教練員”的符號化公式是 (c) 。 a) "x（S（x） " y（J（y） L（x，y））） b) "x $y（S（x）（J（y） L（x，y））） c) "x（S（x） $y（J（y） L（x，y））） d) $y"x（S（x）（J（y） L（x，y））） 6． 下列式子是合式公式的是 (2) 。 （1）（P Q） （2） （P （Q R）） （3）（P Q） （4） Q R 7． 下列式子中正確的是 (4) 。 （1）（"x）P（x）（$x）P（x） （2）（"x）P（x）（"x） P（x） （3）（$x）P（x）（$x） P（x） （4）（$x）P（x）（"x） P（x） 四、解答題 1．構(gòu)造下面推理的證明：　　　　　　　　　　　　　　　　　　 前提：$ x F（x）"y（（F（y） G（y）） R（y））， $ x F（x）。 結(jié)論：$ x R（x）。 2．在一階邏輯中構(gòu)造下面推理的證明 每個喜歡步行的人都不喜歡坐汽車。每個人或者喜歡坐汽車或者喜歡騎自行車。有的人不喜歡騎自行車。因而有的人不喜歡步行。 令F(x)：x喜歡步行。G(x)：x喜歡坐汽車。H(x)：x喜歡騎自行車。 "x( F(x) G(x)), "x(G(x) H(x)), $ x H(x) $ x F(x) 3．在命題邏輯中構(gòu)造下面推理的證明：　　　　　　 　 如果他是理科學生，他必須學好數(shù)學。如果他不是文科學生，他必是理科學生。他沒學好數(shù)學，所以他是文科學生。 4．用直接證法證明：　　 前提：（"x）（C（x）→ W（x）∧R（x）），（$x）（C（x）∧Q（x）） 結(jié)論：（$x）（Q（x）∧R（x））。 第三章集合與關(guān)系 一填空題 （1）如果|A|＝n，那么|AA|＝　n*n　　　。A上的二元關(guān)系有___2_____個。 （2）集合A上關(guān)系R的自反閉包r（R）=___________________。 （3）設集合A上的關(guān)系R和S，R={（1，2），（1，3），（3，2）}，S={（1, 3），（2，1），（3，2）}，則S?R= {(2,2),(1，2) } 。 （4）如果|A|＝n，那么|P(A)|＝　　　　。 （5）設集合A上的關(guān)系R和S，R={<1，2>，<2，1>，<3，4>，<4，3>}，S={<1，3>，<3，1>，<2，4>，<4，2>}，則R?S= {<1,4>,<2,3>,<3,2>,<4,1>} 。 （6）設集合E={a, b, c}，E的冪集P(E)＝ { ,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}___________________________。 （7）設R是定義在集合X上的二元關(guān)系，如果對于每個x, yX， ______ ____ ____________ ，則稱集合X上的關(guān)系R是對稱的。 （8）設關(guān)系R和S為，R={<1，2>，<3，4>，<2，2>}，S={<4，2>，<2，5>，<3，1>，<1，3>}，則R?S =______ ___ __ _______________。 （9）設R是定義在集合X上的二元關(guān)系，如果對于每個x, yX， ______ ____ ____________ ，則稱集合X上的關(guān)系R是自反的。 二．判斷題 1．設A、B、C為任意的三個集合，則A(BC)=A(BC)。 （ ） 2．設S，T是任意集合，如果S -T = ，則S = T。 （ ） 3．集合A={1,2,3,4}上的關(guān)系{<1,2>,<2,3>,<2,4>,<3,4>}是一個函數(shù)。 （ ） 4．集合A={1，2，3，4}上的整除關(guān)系是等價關(guān)系。 （ ） 5．集合A 的冪集P(A)上的包含關(guān)系是偏序關(guān)系。 （ ） 6．設A={a, b, c}, R AA且R={< a, b>,< a, c>}, 則R是傳遞的。 （ ） 6．設A，B是任意集合，如果B ，則A – B A。 （ ） 7．集合A={1,2,3}上的關(guān)系{<1,1>,<2,2>,<3,3>,<1,2>}是傳遞的。 （ ） 8．集合A={1，2，3，4}上的小于關(guān)系是等價關(guān)系。 （ ） 9．關(guān)系{x1, x2N, x1+x2<6}能構(gòu)成一個函數(shù)。 （ ） 10．集合A 上的恒等關(guān)系是偏序關(guān)系。 （ ） 11．集合A={1,2,3}上的關(guān)系S={<1,1>,<1,2>,<3,2>,<3,3>}是自反的。 （ ） 12．設X={1, 2, 3}, Y={a, b, c}。函數(shù)F={<1, a>,<2, c>,<3, b>}是雙射。 （ ） 13．集合A上的關(guān)系R的自反閉包r(R)=R∪IA。 （ ） 14．集合A上的偏序關(guān)系R是自反的、對稱的、傳遞的。 （ ） 15. 設A，B是任意集合，則A B ＝(A-B) ∪(B-A)。 （ ） 三、選擇題：在每小題的備選答案中只有一個正確答案，將正確答案序號填入下列敘述中的 內(nèi)。 1． 設A={a，b，c}，B={a，b}，則下列命題不正確的是 。 a) A－B={a，b} b) A∩B={ a，b } c) AB={c} d) BA 2． 設 A = {a, b, c, d}, A 上的關(guān)系R = {, , , }，則它的對稱閉包為　　　　　　　　　。 a) R = {, , , , , , }， b) R = {, , , , }， c) R = {, , , , , }， d) R = {, , , , , }， 3． 對于集合{1, 2, 3, 4}上的關(guān)系是偏序關(guān)系的是 。 a) R={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>, <2,3>,<2,4>,<3,3>,<3,4>,<4,4>} b) R={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>, <2,1>,<2,4>,<3,1>,<3,4>,<4,4>} c) R={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>, <2,1>,<3,1>,<3,3>,<4,1>,<4,4>} d) R={<2,1>,<1,2>,<1,3>,<1,4>,<2,2>, <4,3>,<2,4>,<3,3>,<3,4>,<4,4>} 4． 設A={1，2，3，4，5}，B={6，7，8，9，10}，以下哪個關(guān)系是從A到B的單射函數(shù) 。 a) f ={<1，7>，<2，6>，<3，5>，<1，9>，<5，10>} b) f ={<1，8>，<2，6>，<3，7>，<4，9>，<5，10>} c) f ={<1，7>，<2，6>，<3，5>，<4，6>} d) f ={<1，10>，<2，6>，<3，7>，<4，8>，<5，10>} 5．設 A = {a, b, c}，要使關(guān)系{, , , }∪R 具有對稱性，則 。 a) R = {, } b) R = {, } c) R = {, } d) R = {, } 6．設S={F，{1}，{1，2}}，則S的冪集P（S）有 個元素 （1）3 （2）6 （3）7 （4）8 7．設R為定義在集合A上的一個關(guān)系，若R是 ，則R為等價關(guān)系 。 （1）反自反的，對稱的和傳遞的 （2）自反的，對稱的和傳遞的 （3） 自反的，反對稱的和傳遞的 （4）對稱的，反對稱的和傳遞的 8．設S，T，M為任意集合，下列命題正確的是 。 a) 如果S∪T = S∪M，則T = M b) 如果S-T = F，則S = T c) S-T S d) S S = S 9． 設 A = {a, b, c}，要使關(guān)系{, , , }∪R 具有對 性，則 。 （1）R = {, } （2）R = {, } （3） R = {, } （4）R = {, } 10．設A={1，2，3，4，5}，B={a，b，c，d，e}，以下哪個函數(shù)是從A到B的入射函數(shù) 。 a) F ={<1，b>，<2，a>，<3，c>，<1，d>，<5，e>} b) F={<1，c>，<2，a>，<3，b>，<4，e>，<5，d>} c) F ={<1，b>，<2，a>，<3，d>，<4，a>} d) F={<1，e>，<2，a>，<3，b>，<4，c>，<5，e>} 四、解答題 1．已知偏序集（A，≦），其中A={a，b，c，d，e}，“≦”為{（a，b）， （a，c），（a，d），（c，e），（b，e），（d，e），（a，e）}∪IA。 （1）畫出偏序集（A，≦）的哈斯圖。 （2）求集合A的極大元，極小元，最大元，最小元。 2．設R是集合A = {1, 2, 3, 4, 5, 6, 7, 8, 9}上的整除關(guān)系。 （1） 給出關(guān)系R；（2）畫出關(guān)系R的哈斯圖； （3）指出關(guān)系R的最大、最小元，極大、極小元。 3．設R是集合A = {1, 2, 3, 4, 6, 12}上的整除關(guān)系。 （2） 給出關(guān)系R； （2） 給出COV A （3） 畫出關(guān)系R的哈斯圖； （4） 給出關(guān)系R的極大、極小元、最大、最小元。 第五章代數(shù)結(jié)構(gòu) 一填空題 （1）集合S的冪集P(S)關(guān)于集合的并運算“∪”的零元為 ___________。 （2）集合S的冪集P(S)關(guān)于集合的并運算“∩”的零元為 ___________。 （3）集合S的冪集P(S)關(guān)于集合的并運算“∪”的么元為 _____________。 （4）一個代數(shù)系統(tǒng)＜S, * ＞，其中S是非空集合。*是S上的一個二元運算，如果 ，則稱代數(shù)系統(tǒng)＜S, * ＞為廣群。 二．判斷題 1．含有零元的半群稱為獨異點。 （ ） 2．運算“＋”是整數(shù)集I上的普通加法，則群的么元是1。 （ ） 三、填空題：在每小題的備選答案中只有一個正確答案，將正確答案序號填入下列敘述中的 內(nèi)。 1． 下列群一定為循環(huán)群的是　　　　　　　　　。 e) （運算“＋”是整數(shù)集I上的普通加法） f) （R是實數(shù)集，“”是普通乘法） g) （運算“＋”是有理數(shù)集Q上的普通加法） h) （P（S）是集合S的冪集，“”為對稱差） 2． 運算“－”是整數(shù)集I上的普通減法，則代數(shù)系統(tǒng) 滿足下列 性質(zhì) 。 （1）結(jié)合律 （2）交換律 （3）有零元 （4） 封閉性 3．設I是整數(shù)集，N是自然數(shù)集，P（S）是S的冪集，“，＋，∩”是普通的乘法，加法和集合的交運算。下面代數(shù)系統(tǒng)中 是群。 （1） （2） （3） （4） 4．下列代數(shù)系統(tǒng)不是群的是　　　　　　　　　。 （5） （運算“＋”是整數(shù)集I上的普通加法） （6） （P（S）是集合S的冪集，“∩”為交運算） （7） （運算“＋”是有理數(shù)集Q上的普通加法） （P（S）是集合S的冪集，“”為對稱差） 第七章圖論 一填空題 （1）一個無向圖G=（V，E）是二部圖當且僅當G中無 長度的回路。 （2）任何圖(無向的或有向的)中，度為奇數(shù)的頂點個數(shù)為　　　　　　。 （3）設D是一個有向圖，若D中任意一對頂點都是相互可達的，則稱D是_______________。 （4）既不含平行邊，也不含環(huán)的圖稱為 。 （5）經(jīng)過圖中　　 　　　一次且僅一次并且行遍圖中每個頂點的回路，稱為歐拉回路。 （6）一棵有n個頂點的樹含有_______________邊。 （7）設G =（V，E），G =（V，E）是兩個圖，若 且 ，稱G是G的生成子圖。 （8）經(jīng)過圖中　　 　　　一次且僅一次的回路，稱為哈密爾頓回路。 二．判斷題 1．5個頂點的有向完全圖有20條邊。 （ ） 2．連通無向圖的歐拉回路經(jīng)過圖中的每個頂點一次且僅一次。 （ ） 3． 圖中的初級通路都是簡單通路。 （ ） 4． 已知n (n2)階無向簡單圖G有n – 1條邊，則G一定為樹。 （ ） 5． n階無向完全圖Kn的每個頂點的度都是n。 （ ） 6．一個無向圖是二部圖當且僅當它沒有奇數(shù)度的頂點。 （ ） 7．任何圖都有一棵生成樹。 （ ） 8．連通無向圖的哈密爾頓回路經(jīng)過圖中的每條邊一次且僅一次。 （ ） 9．圖中的初級回路都是簡單回路。 （ ） 10．任一圖G=（V，E）的頂點的最大度數(shù)必小于G的頂點數(shù)。 （ ） 11．歐拉圖一定是漢密爾頓圖。 （ ） 12．無向連通圖G的任意兩結(jié)點之間都存在一條路。 （ ） 13．根樹中除一個結(jié)點外，其余結(jié)點的入度為1。 （ ） 三、選擇題：在每小題的備選答案中只有一個正確答案，將正確答案序號填入下列敘述中的 內(nèi)。 1． 下列為歐拉圖的是 。 2． 下列各圖為簡單圖的是　　　 　　　　　　。 (4) (3) (2) (1) 　 3． 設無向圖G有12條邊，已知G中3度頂點有6個，其余頂點的度數(shù)都小于3，則該圖至少有 個頂點。 （1）6 （2）8 （3）9 （4） 12 4．下列四個有6個結(jié)點的圖 是連通圖。 (2) (1) (3) (4) 5．稱圖G′=為圖G = 的生成子圖是指________. （1）V′ V （2）V′ V且E′ E （3）V′= V且E′ E （4）V′ V且E′ E 6．有向圖中結(jié)點之間的可達關(guān)系是______________。 （1） 自反的，對稱的 （2） 自反的，傳遞的 （3） 自反的，反對稱的 （4） 反自反的，對稱的 7．在下列關(guān)于圖論的命題中，為真的命題是 。 a) 完全二部圖Kn, m (n 1, m 1)是歐拉圖 b) 歐拉圖一定是哈密爾頓圖 c) 無向完全圖Kn（n3）都是歐拉圖 d) 無向完全圖Kn（n3）都是哈密爾頓圖 8．下列各圖為平面圖的是　　　　　　　　　。 (4) (2) (3) (1) 　 9． 設G為任意的連通的平面圖，且G有n個頂點，m條邊，r個面，則平面圖的歐拉公式為 。 （1）n – m + r = 2（2）m – n + r = 2（3）n + m – r =2（4）r + n + m = 2 10． 下列四個圖中與其余三個圖不同構(gòu)的圖是 。 （1） （2） （3） （4） 四、解答題 1．給定邊集：{（1，2），（1，3），（2，3），（2，4），（2，5），（3，4）， （3，5），（4，5）}， （8） 畫出相應的無向圖G（設G無孤立點）； （9） 畫出頂點子集V1 = { 2, 3, 4, 5}導出的導出子圖； （10） 畫出圖G的一棵生成樹。　　　　　　　　　　　　　 2．如圖所示帶權(quán)圖，用避圈法(Kruskal算法)求一棵最小生成樹并計算它的權(quán)值。　 3．如圖所示帶權(quán)圖，用避圈法(Kruskal算法)求一棵最小生成樹并計算它的權(quán)值?！? 4．求帶權(quán)圖G的最小生成樹，并計算它的權(quán)值。 5．給定權(quán)為2，6，3，9，4；構(gòu)造一顆最優(yōu)二叉樹?！? 6．給定權(quán)為1，9，4，7，3；構(gòu)造一顆最優(yōu)二叉樹。 7．給定權(quán)為2，6，5，9，4，1；構(gòu)造一顆最優(yōu)二叉樹。