1、姓 名： 學 號： 得 分： 教師簽名： 離散數學作業5離散數學圖論部分形成性考核書面作業本課程形成性考核書面作業共3次，內容主要分別是集合論部分、圖論部分、數理邏輯部分的綜合練習，基本上是按照考試的題型（除單項選擇題外）安排練習題目，目的是通過綜合性書面作業，使同學自己檢驗學習成果，找出掌握的薄弱知識點，重點復習，爭取盡快掌握。本次形考書面作業是第二次作業，大家要認真及時地完成圖論部分的綜合練習作業。要求：將此作業用a4紙打印出來，手工書寫答題，字跡工整，解答題要有解答過程，要求2010年12月5日前完成并上交任課教師（不收電子稿）。并在05任務界面下方點擊“保存”和“交卷”按鈕，以便教師評

2、分。一、填空題1已知圖g中有1個1度結點，2個2度結點，3個3度結點，4個4度結點，則g的邊數是 15 2設給定圖g(如右由圖所示)，則圖g的點割集是 f 3設g是一個圖，結點集合為v，邊集合為e，則g的結點 度數之和 等于邊數的兩倍4無向圖g存在歐拉回路，當且僅當g連通且 等于出度 5設g=<v，e>是具有n個結點的簡單圖，若在g中每一對結點度數之和大于等于 n-1 ，則在g中存在一條漢密爾頓路 6若圖g=<v, e>中具有一條漢密爾頓回路，則對于結點集v的每個非空子集s，在g中刪除s中的所有結點得到的連通分支數為w，則s中結點數|s|與w滿足的關系式為 w(g-v1

3、) £½v1½ 7設完全圖k有n個結點(n³2)，m條邊，當 n為奇數 時，k中存在歐拉回路8結點數v與邊數e滿足 e=v-1 關系的無向連通圖就是樹9設圖g是有6個結點的連通圖，結點的總度數為18，則可從g中刪去 4 條邊后使之變成樹10設正則5叉樹的樹葉數為17，則分支數為i = 5 二、判斷說明題（判斷下列各題，并說明理由）1如果圖g是無向圖，且其結點度數均為偶數，則圖g存在一條歐拉回路(1) 不正確，缺了一個條件，圖g應該是連通圖，可以找出一個反例，比如圖g是一個有孤立結點的圖。2如下圖所示的圖g存在一條歐拉回路(2) 不正確，圖中有奇數度結點，

4、所以不存在是歐拉回路。3如下圖所示的圖g不是歐拉圖而是漢密爾頓圖 g 解：正確因為圖中結點a，b，d，f的度數都為奇數，所以不是歐拉圖。如果我們沿著(a,d,g,f,e,b,c,a)，這樣除起點和終點是a外，我們經過每個點一次僅一次，所以存在一條漢密爾頓回路，是漢密爾頓圖4設g是一個有7個結點16條邊的連通圖，則g為平面圖解：(1) 錯誤假設圖g是連通的平面圖，根據定理，結點數v，邊數為e，應滿足e小于等于3v-6，但現在16小于等于3*7-6，顯示不成立。所以假設錯誤。 5設g是一個連通平面圖，且有6個結點11條邊，則g有7個面(2) 正確根據歐拉定理，有v-e+r=2，邊數v=11，結點數

5、e=6，代入公式求出面數r=7三、計算題1設g=<v，e>，v= v1，v2，v3，v4，v5，e= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，試(1) 給出g的圖形表示； (2) 寫出其鄰接矩陣；(3) 求出每個結點的度數； (4) 畫出其補圖的圖形解：(1)oooov1ov5v2v3v4(2) 鄰接矩陣為(3) v1結點度數為1，v2結點度數為2，v3結點度數為3，v4結點度數為2，v5結點度數為2(4) 補圖圖形為oooov1ov5v2v3v42圖g=<v, e>，其中v= a, b, c, d, e，e=

6、(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權最小的生成樹及其權值（1）g的圖形如下：（2）寫出g的鄰接矩陣（3）g權最小的生成樹及其權值3已知帶權圖g如右圖所示 (1) 求圖g的最小生成樹； (2)計算該生成樹的權值解：(1) 最小生成樹為12357(2) 該生成樹的權值為(1+2+3+5+7)=184設有一組權為2, 3, 5, 7, 17, 31，試畫出相應的最優二叉樹，計算該最優二叉樹的權35251071731173465權為 2*5+3*5+5*4+7*3+17*2+31=131四、證明題1設g是一個n階無向簡單圖，n是大于等于3的奇數證明圖g與它的補圖中的奇數度頂點個數相等證明：設，則是由n階無向完全圖的邊刪去e所得到的所以對于任意結點，u在g和中的度數之和等于u在中的度數由于n是大于等于3的奇數，從而的每個結點都是偶數度的（度），于是若在g中是奇數度結點，則它在中也是奇數度結點故圖g與它的補圖中的奇數度結點個數相等2設連通圖g有k個奇數度的結點，證明在圖g中至少要添加條邊才能使其成為歐拉圖證明：由定理3.1.2，任何圖中度數為奇數的結點必是偶數，可知k是偶數又根據定