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