資源描述：
《離散數(shù)學(xué)形考任務(wù)07答案》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、★形成性考核作業(yè)★姓名：學(xué)號：得分：教師簽名：離散數(shù)學(xué)作業(yè)7離散數(shù)學(xué)圖論部分形成性考核書面作業(yè)本課程形成性考核書面作業(yè)共3次，內(nèi)容主要分別是圖論部分、數(shù)理邏輯部分的綜合練習(xí)，基本上是按照考試的題型安排練習(xí)題目，目的是通過綜合性書面作業(yè)，使同學(xué)自己檢驗學(xué)習(xí)成果，找出掌握的薄弱知識點，重點復(fù)習(xí)，爭取盡快掌握。本次形考書面作業(yè)是第二次作業(yè)，大家要認(rèn)真及時地完成圖論部分的綜合練習(xí)作業(yè)。要求：將此作業(yè)用A4紙打印出來，手工書寫答題，字跡工整，解答題要有解答過程，完成并上交任課教師（不收電子稿）。并在07任務(wù)界面下方點擊“
2、保存”和“交卷”按鈕，以便教師評分。一、單項選擇題1．設(shè)圖G的鄰接矩陣為，則G的邊數(shù)為(D)．A．5B．6C．3D．42．設(shè)圖G＝，則下列結(jié)論成立的是(C)．A．deg(V)=2?E?B．deg(V)=?E?C．D．3．設(shè)有向圖（a）、（b）、（c）與（d）如下圖所示，則下列結(jié)論成立的是(D)．a(chǎn)bdceooooo4題圖A．（a）是強(qiáng)連通的B．（b）是強(qiáng)連通的C．（c）是強(qiáng)連通的D．（d）是強(qiáng)連通的4．給定無向圖G如右圖所示，下面給出的結(jié)點集子集中，不是點割集的為（B）．A．{b,d}B．ki97o4b7★形
3、成性考核作業(yè)★C．{a,c}D．{b,e}oaoooobcde5題圖5．圖G如右圖所示，以下說法正確的是(C)．A．{(a,c)}是割邊B．{(a,c)}是邊割集C．{(b,c)}是邊割集D．{(a,c),(b,c)}是邊割集6．無向圖G存在歐拉通路，當(dāng)且僅當(dāng)(D)．A．G中所有結(jié)點的度數(shù)全為偶數(shù)B．G中至多有兩個奇數(shù)度結(jié)點C．G連通且所有結(jié)點的度數(shù)全為偶數(shù)D．G連通且至多有兩個奇數(shù)度結(jié)點7．若G是一個歐拉圖，則G一定是(C)．A．平面圖B．漢密爾頓圖C．連通圖D．對偶圖8．設(shè)G是連通平面圖，有v個結(jié)點，e條邊
4、，r個面，則r=(A)．A．e－v＋2B．v＋e－2C．e－v－2D．e＋v＋29．設(shè)G是有n個結(jié)點，m條邊的連通圖，必須刪去G的(A)條邊，才能確定G的一棵生成樹．A．B．C．D．10．已知一棵無向樹T中有8個結(jié)點，4度，3度，2度的分支點各一個，T的樹葉數(shù)為（D）．A．8B．5C．4D．3二、填空題1．已知圖G中有1個1度結(jié)點，2個2度結(jié)點，3個3度結(jié)點，4個4度結(jié)點，則G的邊數(shù)是15．2．設(shè)給定圖G(如右由圖所示)，則圖G的點割集是{f,c}．3．設(shè)G是一個圖，結(jié)點集合為V，邊集合為E，則G的結(jié)點度數(shù)等于
5、邊數(shù)的兩倍．4．設(shè)有向圖D為歐拉圖，則圖D中每個結(jié)點的入度 等于出度 ?。?．設(shè)G=是具有n個結(jié)點的簡單圖，若在G中每一對結(jié)點度數(shù)之和大于等于n-1，則在G中存在一條漢密爾頓路．6．設(shè)無向圖G＝是漢密爾頓圖，則V的任意非空子集V1，都有W(G-V1)￡?V1?．7．設(shè)完全圖K有n個結(jié)點(n32)，m條邊，當(dāng)當(dāng)m=2n時，K中存在歐拉回路．7★形成性考核作業(yè)★8．設(shè)圖G=，其中
6、V
7、=n，
8、E
9、=m．則圖G是樹當(dāng)且僅當(dāng)G是連通的，且m=2V-2．9．連通無向圖G有6個頂點9條邊，從G
10、中刪去4條邊才有可能得到G的一棵生成樹T．10．設(shè)正則5叉樹的樹葉數(shù)為17，則分支數(shù)為i=4．三、判斷說明題（判斷下列各題，并說明理由．）1．(1)如果圖G是無向圖，且其結(jié)點度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路．．(2)圖G1，(如下圖所示)是歐拉圖．解：(1)錯，圖G是無向圖，當(dāng)且僅當(dāng)G是連通的，且所有結(jié)點度數(shù)均為偶數(shù)，這里不能確定G圖是否是連通的。(2)錯，由歐拉圖的定理“無向圖G具有一條歐拉路，當(dāng)且僅當(dāng)G是連通的，且有零個或兩個奇數(shù)度結(jié)點”得到這里任何一個結(jié)點都沒有奇數(shù)度結(jié)點。2．圖G2（如下圖所示）不是
11、歐拉圖而是漢密爾頓圖．解：錯，既不是歐拉圖也不是漢密爾圖。歐拉圖要求所有結(jié)點度數(shù)均為偶數(shù)，這里結(jié)點b,d各有三個節(jié)點；漢密爾圖要求每一對結(jié)點度數(shù)之和大于等于總結(jié)點數(shù)，這里不滿足。7★形成性考核作業(yè)★3．(1)設(shè)G是一個有7個結(jié)點16條邊的連通圖，則G為平面圖．(2)設(shè)G是一個連通平面圖，且有6個結(jié)點11條邊，則G有7個面．解：(1)錯，沒有提到面。(2)對，由歐拉定理得到：結(jié)點-邊+面=2，即為連通平面圖，這里6-11+7=24．下圖給出的樹是否同構(gòu)的．解：(a)同構(gòu)，(b),(c)同構(gòu)。因為由圖的同構(gòu)相關(guān)聯(lián)，
12、得到同構(gòu)的必要條件：(1)結(jié)點數(shù)目相同。(2)邊數(shù)相同。(3)度數(shù)相同的結(jié)點數(shù)目相同故(a)不滿足，即不同構(gòu)。7★形成性考核作業(yè)★四、計算題1．設(shè)G=，V={v1，v2，v3，v4，v5}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，試(1)給出G的圖形表示；(2)寫出其鄰接矩陣；(3)求出每個結(jié)點的度數(shù)；(4)畫出
