形成性考核作業(yè) 姓 名： 學 號： 得 分： 教師簽名： 離散數(shù)學作業(yè)4離散數(shù)學圖論部分形成性考核書面作業(yè)本課程形成性考核書面作業(yè)共3次，內容主要分別是集合論部分、圖論部分、數(shù)理邏輯部分的綜合練習，基本上是按照考試的題型（除單項選擇題外）安排練習題目，目的是通過綜合性書面作業(yè)，使同學自己檢驗學習成果，找出掌握的薄弱知識點，重點復習，爭取盡快掌握本次形考書面作業(yè)是第二次作業(yè)，大家要認真及時地完成圖論部分的綜合練習作業(yè)要求：學生提交作業(yè)有以下三種方式可供選擇：1. 可將此次作業(yè)用A4紙打印出來，手工書寫答題，字跡工整，解答題要有解答過程，完成作業(yè)后交給輔導教師批閱2. 在線提交word文檔3. 自備答題紙張，將答題過程手工書寫，并拍照上傳一、填空題1已知圖G中有1個1度結點，2個2度結點，3個3度結點，4個4度結點，則G的邊數(shù)是 15 2設給定圖G(如右由圖所示)，則圖G的點割集是 f ， e,c 3設G是一個圖，結點集合為V，邊集合為E，則G的結點 度數(shù)之和 等于邊數(shù)的兩倍4無向圖G存在歐拉回路，當且僅當G連通且 不含奇數(shù)度結點 5設G=是具有n個結點的簡單圖，若在G中每一對結點度數(shù)之和大于等于 v ，則在G中存在一條漢密爾頓路 6若圖G=中具有一條漢密爾頓回路，則對于結點集V的每個非空子集S，在G中刪除S中的所有結點得到的連通分支數(shù)為W，則S中結點數(shù)|S|與W滿足的關系式為 W S 7設完全圖K有n個結點(n2)，m條邊，當 n為奇數(shù)時 時，K中存在歐拉回路8結點數(shù)v與邊數(shù)e滿足 e=v - 1 關系的無向連通圖就是樹9設圖G是有6個結點的連通圖，結點的總度數(shù)為18，則可從G中刪去 條邊后使之變成樹10設正則5叉樹的樹葉數(shù)為17，則分支數(shù)為i = 4 二、判斷說明題（判斷下列各題，并說明理由）1如果圖G是無向圖，且其結點度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路 答：錯誤。應敘述為：“如果圖G是無向連通圖，且其結點度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路?！?如下圖所示的圖G存在一條歐拉回路答：錯誤。因為圖中存在奇數(shù)度結點，所以不存在歐拉回路。3如下圖所示的圖G不是歐拉圖而是漢密爾頓圖 G 答：正確。因為有4個結點的度數(shù)為奇數(shù)，所以不是歐拉圖；而對于圖中任意點集V中的非空子集V1，都有P(G-V1) V1。其中P(G-V1)是從圖中刪除V1結點及其關聯(lián)的邊。4設G是一個有7個結點16條邊的連通圖，則G為平面圖答：錯誤。若G是連通平面圖，那么若V 3,就有e3v-6而16376，所以不滿足定理條件，敘述錯誤。 5設G是一個連通平面圖，且有6個結點11條邊，則G有7個面答：正確。因為連通平面圖滿足歐拉公式。即：v-e+r=2。由此題條件知6-11+7=2成立三、計算題1設G=，V= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，試(1) 給出G的圖形表示； (2) 寫出其鄰接矩陣；(3) 求出每個結點的度數(shù)； (4) 畫出其補圖的圖形答：（1） （2） （3）=deg(v1)=1, deg(v2)=2 ,deg(v3)=4 ,deg(v4)=3,deg(v5)=2 (4) 2圖G=，其中V= a, b, c, d, e，E= (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) ，對應邊的權值依次為2、1、2、3、6、1、4及5，試（1）畫出G的圖形； （2）寫出G的鄰接矩陣；（3）求出G權最小的生成樹及其權值（2） （3） 其中權值是：7 3已知帶權圖G如右圖所示 (1) 求圖G的最小生成樹； (2)計算該生成樹的權值答：（1） （2） 權值：184 設有一組權為2, 3, 5, 7, 17, 31，試畫出相應的最優(yōu)二叉樹，計算該最優(yōu)二叉樹的權 權值：65四、證明題1設G是一個n階無向簡單圖，n是大于等于3的奇數(shù)證明圖G與它的補圖中的奇數(shù)度頂點個數(shù)相等證明：設a為G中任意一個奇數(shù)度頂點，由定義，a仍為頂點，為區(qū)分起見，記為a,則deg(a)+deg(a)=n-1,而n為奇數(shù)，則a必為奇數(shù)度頂點。由a的任意性，容易得知結論成立。2設連通圖G有k個奇數(shù)度的結點，證明在圖G中至少要添加條邊才能使其成為歐拉圖證明：由定理推論知：在任何圖中，度數(shù)為奇數(shù)的