2018國(guó)家開(kāi)放大學(xué)離散數(shù)學(xué)本形考任務(wù)答案

教師簽名：離散數(shù)學(xué)圖論部分形成性考核書(shū)面作業(yè)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).可修編.中存在歐拉回路.8.結(jié)點(diǎn)數(shù)v與邊數(shù)e滿足e=V-1關(guān)系的無(wú)向連通圖就是樹(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存在一條歐拉回路?！?.如下圖所示的圖G存在一條歐拉回路.答：錯(cuò)誤。因?yàn)閳D中存在奇數(shù)度結(jié)點(diǎn)，所以不存在歐拉回路。3.如下圖所示的圖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>3×7-6,所以不滿足定理?xiàng)l件，敘述錯(cuò)誤。5.設(shè)G是一個(gè)連通平面圖，且有6個(gè)結(jié)點(diǎn)11條邊，則G有7個(gè)面.答：(1).可修編.deg(v1)=1,deg(v2)=2,deg(v3)=42.圖G=<V,E>,其中V={a(c,d),(d,e)},對(duì)應(yīng)邊的權(quán)值依次為2、1、2、3、6、1、4及5,試(1)畫(huà)出G的圖形；(2)寫(xiě)出G的鄰接矩陣；(3)求出G權(quán)最小的生成樹(shù)及其權(quán)值.bC解：(1)22.可修編.b。其中權(quán)值是：73.已知帶權(quán)圖G如右圖所示.(1)求圖G的最小生成樹(shù)；(2)計(jì)算該生成樹(shù)的權(quán)值.227權(quán)值：184.設(shè)有一組權(quán)為2,3,