離散數學作業4
離散數學圖論部分形成性考核書面作業
本課程形成性考核書面作業共3次，內容主要分別是集合論部分、圖論部分、數理邏輯部分的綜合練習，基本上是按照考試的題型（除單項選擇題外）安排練習題目，目的是通過綜合性書面作業，使同學自己檢驗學習成果，找出掌握的薄弱知識點，重點複習，爭取盡快掌握．本次形考書面作業是第二次作業，大家要認真及時地完成圖論部分的綜合練習作業．
要求：學生提交作業有以下三種方式可供選擇：
1. 可將此次作業用a4紙列印出來，手工書寫答題，字跡工整，解答題要有解答過程，完成作業後交給輔導教師批閱．
2. **提交word文件
3. 自備答題紙張，將答題過程手工書寫，並拍照上傳．
一、填空題
1．已知圖g中有1個1度結點，2個2度結點，3個3度結點，4個4度結點，則g的邊數是 15 ．
2．設給定圖g(如右由圖所示)，則圖g的點割集是
， ．
3．設g是乙個圖，結點集合為v，邊集合為e，則
g的結點度數之和等於邊數的兩倍．
4．無向圖g存在尤拉迴路，當且僅當g連通且等於出度
5．設g=是具有n個結點的簡單圖，若在g中每一對結點度數之和大於等於 n-1 ，則在g中存在一條漢密爾頓路．
6．若圖g=中具有一條漢密爾頓迴路，則對於結點集v的每個非空子集s，在g中刪除s中的所有結點得到的連通分支數為w，則s中結點數|s|與w滿足的關係式為 w(g-v1) v1
7．設完全圖k有n個結點(n2)，m條邊，當 n為奇數時，k中存在尤拉迴路．
8．結點數v與邊數e滿足 e=v-1 關係的無向連通圖就是樹．
9．設圖g是有6個結點的連通圖，結點的總度數為18，則可從g中刪去
4 條邊後使之變成樹．
10．設正則5叉樹的樹葉數為17，則分支數為i = 5 ．
二、判斷說明題（判斷下列各題，並說明理由．）
1．如果圖g是無向圖，且其結點度數均為偶數，則圖g存在一條尤拉迴路．
解：不正確，缺了乙個條件，圖g應該是連通圖，可以找出乙個反例，比如圖g是乙個有孤立結點的圖。
2．如下圖所示的圖g存在一條尤拉迴路．
解：不正確，圖中有奇數度結點，所以不存在是尤拉迴路。
3．如下圖所示的圖g不是尤拉圖而是漢密爾頓圖．
解：正確
因為圖中結點a，b，d，f的度數都為奇數，所以不是尤拉圖。
如果我們沿著(a,d,g,f,e,b,c,a)，這樣除起點和終點是a外，我們經過每個點一次僅一次，所以存在一條漢密爾頓迴路，是漢密爾頓圖。
4．設g是乙個有7個結點16條邊的連通圖，則g為平面圖．
解：錯誤
假設圖g是連通的平面圖，根據定理，結點數v，邊數為e，應滿足e小於等於3v-6，但現在16小於等於3*7-6，顯然不成立。
所以假設錯誤。
5．設g是乙個連通平面圖，且有6個結點11條邊，則g有7個面．
解：正確
根據尤拉定理，有v-e+r=2，邊數v=11，結點數e=6，代入公式求出面數r=7。
三、計算題
1．設g=，v=，e=，試
(1) 給出g的圖形表示2) 寫出其鄰接矩陣；
(3) 求出每個結點的度數4) 畫出其補圖的圖形．
解：(1)
(2) 鄰接矩陣為
(3) v1結點度數為1，v2結點度數為2，v3結點度數為3，v4結點度數為2，v5結點度數為2
(4) 補圖圖形為
2．圖g=，其中v=，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) 最小生成樹為
(2) 該生成樹的權值為(1+2+3+5+7)=18
4．設有一組權為2, 3, 5, 7, 17, 31，試畫出相應的最優二叉樹，計算該最優二叉樹的權．
權為 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是偶數．
又根據定理4.1.1的推論，圖g是尤拉圖的充分必要條件是圖g不含奇數度結點．因此只要在每對奇數度結點之間各加一條邊，使圖g的所有結點的度數變為偶數，成為尤拉圖．
故最少要加條邊到圖g才能使其成為尤拉圖．
離散數學形成性考核作業2答案
1.若集合a 則下列表述正確的是 a.a b.a c.a d.a 2.設a b是兩個任意集合，側a b a.a b b.ab c.ab d.b 3.集合a 上的關係r r是a上的二元關係，其關係矩陣為 則r的關係表示式是 a.b.c.d.5.設集合a 上的二元關係r s 則s是r的 閉包 a.自反 ...
離散數學形成性考核作業5答案
一 填空題 1 已知圖g中有1個1度結點，2個2度結點，3個3度結點，4個4度結點，則g的邊數是 15 2 設給定圖g 如右由圖所示 則圖g的點割集是 和，e 試 1 給出g的圖形表示2 寫出其鄰接矩陣 3 求出每個結點的度數4 畫出其補圖的圖形 解 1 如右圖 2 3 v1的度數為1，v2的度數為...
《工程數學》形成性考核作業4答案
第6章統計推斷 一 單項選擇題 設是來自正態總體 均未知 的樣本，則 a 是統計量 a.b.c.d.設是來自正態總體 均未知 的樣本，則統計量 d 不是的無偏估計 ab.cd.二 填空題 1 統計量就是不含未知引數的樣本函式 2 引數估計的兩種方法是點估計和區間估計 常用的引數點估計有矩估計法和最大...