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