離散數(shù)學(xué)網(wǎng)絡(luò)課程形成性考核第4次形考任務(wù)?一、任務(wù)說(shuō)明本次形考任務(wù)主要涵蓋離散數(shù)學(xué)中的多個(gè)重要知識(shí)點(diǎn)，包括圖論、樹(shù)等相關(guān)內(nèi)容。通過(guò)一系列的題目，旨在考查學(xué)生對(duì)這些知識(shí)的理解、掌握和應(yīng)用能力。二、題目及解答（一）單項(xiàng)選擇題1.設(shè)圖G的鄰接矩陣為\[\begin{pmatrix}0&1&1&1\\1&0&0&1\\1&0&0&0\\1&1&0&0\end{pmatrix}\]則G的邊數(shù)為（）A.5B.6C.3D.4答案：B解答：對(duì)于無(wú)向圖的鄰接矩陣\(A=(a_{ij})\)，其邊數(shù)\(m=\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}\)。這里\(n=4\)，計(jì)算可得：\[\begin{align*}m&=\frac{1}{2}(0+1+1+1+1+0+0+1+1+0+0+0+1+1+0+0)\\&=\frac{1}{2}\times12\\&=6\end{align*}\]2.已知圖G的鄰接矩陣為\[\begin{pmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{pmatrix}\]則G有（）A.5點(diǎn)，8邊B.6點(diǎn)，7邊C.6點(diǎn)，8邊D.5點(diǎn)，7邊答案：D解答：同樣根據(jù)上述邊數(shù)計(jì)算公式，\(n=5\)，計(jì)算邊數(shù)\(m\)：\[\begin{align*}m&=\frac{1}{2}(0+1+0+1+1+0+1+0+0+1+0+1+1+0+1+0)\\&=\frac{1}{2}\times14\\&=7\end{align*}\]所以圖\(G\)有\(zhòng)(5\)個(gè)點(diǎn)，\(7\)條邊。3.設(shè)圖G=<V,E>，則下列結(jié)論成立的是()A.\(deg(V)=\sum_{v\inV}deg(v)\)B.\(deg(V)=2|E|\)C.\(\sum_{v\inV}deg(v)=2|E|\)D.\(\sum_{v\inV}deg(v)=|E|\)答案：C解答：這是圖論中的握手定理，對(duì)于任意無(wú)向圖\(G=(V,E)\)，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的\(2\)倍，即\(\sum_{v\inV}deg(v)=2|E|\)。4.圖G如圖一所示，以下說(shuō)法正確的是()A.\((a,d)\)是割邊B.\((a,d)\)是邊割集C.\(\{(a,d),(b,d)\}\)是邊割集D.\(\{(b,d)\}\)是邊割集答案：C解答：邊割集是指刪除該集合中的邊會(huì)使圖不連通的邊集合。選項(xiàng)A：刪除\((a,d)\)后圖仍連通，所以\((a,d)\)不是割邊。選項(xiàng)B：僅\((a,d)\)不能使圖不連通，不是邊割集。選項(xiàng)C：刪除\(\{(a,d),(b,d)\}\)后圖不連通，所以\(\{(a,d),(b,d)\}\)是邊割集。選項(xiàng)D：刪除\(\{(b,d)\}\)后圖仍連通，不是邊割集。5.圖G如圖一所示，以下說(shuō)法正確的是()A.\(a\)是割點(diǎn)B.\(\{b,c\}\)是點(diǎn)割集C.\(\{b,d\}\)是點(diǎn)割集D.\(\{c\}\)是點(diǎn)割集答案：B解答：點(diǎn)割集是指刪除該集合中的點(diǎn)會(huì)使圖不連通的點(diǎn)集合。選項(xiàng)A：刪除\(a\)后圖仍連通，\(a\)不是割點(diǎn)。選項(xiàng)B：刪除\(\{b,c\}\)后圖不連通，所以\(\{b,c\}\)是點(diǎn)割集。選項(xiàng)C：刪除\(\{b,d\}\)后圖仍連通，不是點(diǎn)割集。選項(xiàng)D：刪除\(\{c\}\)后圖仍連通，不是點(diǎn)割集。6.設(shè)有向圖（a）、（b）、（c）與（d）如圖二所示，則下列結(jié)論成立的是()A.（a）是強(qiáng)連通的B.（b）是強(qiáng)連通的C.（c）是強(qiáng)連通的D.（d）是強(qiáng)連通的答案：A解答：選項(xiàng)A：有向圖（a）中任意兩點(diǎn)都相互可達(dá)，是強(qiáng)連通的。選項(xiàng)B：（b）中存在從某些點(diǎn)不可達(dá)其他點(diǎn)的情況，不是強(qiáng)連通的。選項(xiàng)C：（c）同理，不是強(qiáng)連通的。選項(xiàng)D：（d）也不是強(qiáng)連通的。7.設(shè)完全圖\(K_n\)有n個(gè)結(jié)點(diǎn)(n≥2)，m條邊，當(dāng)（）時(shí)，\(K_n\)中存在歐拉回路．A.m為奇數(shù)B.n為偶數(shù)C.n為奇數(shù)D.m為偶數(shù)答案：C解答：對(duì)于完全圖\(K_n\)，其邊數(shù)\(m=\frac{n(n1)}{2}\)。存在歐拉回路的充要條件是圖中每個(gè)頂點(diǎn)的度數(shù)都是偶數(shù)。在\(K_n\)中，每個(gè)頂點(diǎn)的度數(shù)為\(n1\)，所以當(dāng)\(n\)為奇數(shù)時(shí)，\(n1\)為偶數(shù)，此時(shí)\(K_n\)中存在歐拉回路。8.設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r=()A.e－v＋2B.v＋e－2C.e－v－2D.e＋v＋2答案：A解答：這是平面圖的歐拉公式，對(duì)于連通平面圖\(G=(V,E,F)\)，有\(zhòng)(ve+r=2\)，移項(xiàng)可得\(r=ev+2\)。9.無(wú)向簡(jiǎn)單圖G是棵樹(shù)，當(dāng)且僅當(dāng)()A.G連通且邊數(shù)比結(jié)點(diǎn)數(shù)少1B.G連通且結(jié)點(diǎn)數(shù)比邊數(shù)少1C.G的邊數(shù)比結(jié)點(diǎn)數(shù)少1D.G中沒(méi)有回路答案：A解答：無(wú)向簡(jiǎn)單圖\(G\)是棵樹(shù)的定義就是\(G\)連通且邊數(shù)比結(jié)點(diǎn)數(shù)少\(1\)。10.已知一棵無(wú)向樹(shù)T中有8個(gè)結(jié)點(diǎn)，4度，3度，2度的分支點(diǎn)各一個(gè)，T的樹(shù)葉數(shù)為（）A.8B.5C.4D.3答案：B解答：設(shè)樹(shù)葉數(shù)為\(x\)，根據(jù)樹(shù)的性質(zhì)，邊數(shù)\(e=v1=81=7\)。再根據(jù)握手定理\(\sum_{v\inV}deg(v)=2e\)，可得\(4+3+2+x=2\times7\)，即\(9+x=14\)，解得\(x=5\)。（二）填空題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解答：根據(jù)握手定理\(\sum_{v\inV}deg(v)=2e\)，可得\(1\times1+2\times2+3\times3+4\times4=2e\)，即\(1+4+9+16=2e\)，\(30=2e\)，解得\(e=15\)。2.設(shè)給定圖G(如圖三所示)，則圖G的點(diǎn)割集是。答案：\(\{f\}\)，\(\{c,e\}\)解答：點(diǎn)割集是刪除該集合中的點(diǎn)會(huì)使圖不連通的點(diǎn)集合。刪除\(\{f\}\)或\(\{c,e\}\)后圖\(G\)不連通，所以圖\(G\)的點(diǎn)割集是\(\{f\}\)，\(\{c,e\}\)。3.設(shè)G是一個(gè)圖，結(jié)點(diǎn)集合為V，邊集合為E，則G的結(jié)點(diǎn)等于邊數(shù)的兩倍。答案：度數(shù)之和解答：這是握手定理的內(nèi)容，即\(\sum_{v\inV}deg(v)=2|E|\)。4.無(wú)向圖G存在歐拉回路，當(dāng)且僅當(dāng)G連通且。答案：所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)解答：這是無(wú)向圖存在歐拉回路的充要條件。5.設(shè)G=<V，E>是具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，若在G中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于，則在G中存在一條漢密爾頓路。答案：\(n1\)解答：這是圖中存在漢密爾頓路的充分條件。6.若圖G=<V,E>中具有一條漢密爾頓回路，則對(duì)于結(jié)點(diǎn)集V的每個(gè)非空子集S，在G中刪除S中的所有結(jié)點(diǎn)得到的連通分支數(shù)為W，則S中結(jié)點(diǎn)數(shù)|S|與W滿足的關(guān)系式為。答案：\(W\leq|S|\)解答：這是漢密爾頓圖的一個(gè)必要條件。7.設(shè)完全圖K_n有n個(gè)結(jié)點(diǎn)(n≥2)，m條邊，當(dāng)n為時(shí)，K_n中存在歐拉回路。答案：奇數(shù)解答：前面已說(shuō)明，\(K_n\)中存在歐拉回路時(shí)\(n\)為奇數(shù)。8.結(jié)點(diǎn)數(shù)v與邊數(shù)e滿足關(guān)系的無(wú)向連通圖就是樹(shù)。答案：\(e=v1\)解答：這是樹(shù)的邊數(shù)與結(jié)點(diǎn)數(shù)的關(guān)系。9.設(shè)圖G是有6個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的總度數(shù)為18，則可從G中刪去條邊后使之變成樹(shù)。答案：4解答：已知邊數(shù)\(e=\frac{1}{2}\sum_{v\inV}deg(v)=\frac{1}{2}\times18=9\)，樹(shù)的邊數(shù)\(e'=v1=61=5\)，所以要?jiǎng)h去\(95=4\)條邊。10.設(shè)正則5叉樹(shù)的樹(shù)葉數(shù)為17，則分支數(shù)為。答案：4解答：設(shè)分支數(shù)為\(i\)，根據(jù)正則\(m\)叉樹(shù)的性質(zhì)\((m1)i=t1\)（\(t\)為樹(shù)葉數(shù)），這里\(m=5\)，\(t=17\)，則\((51)i=171\)，\(4i=16\)，解得\(i=4\)。（三）判斷說(shuō)明題（判斷下列各題，并說(shuō)明理由）1.如果圖G是無(wú)向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路．答案：錯(cuò)誤。理由：圖\(G\)是無(wú)向圖且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，這只是圖\(G\)存在歐拉回路的必要條件而非充分條件。還需要圖\(G\)是連通的，才能得出圖\(G\)存在一條歐拉回路。例如一個(gè)由兩個(gè)不連通的子圖組成的圖，每個(gè)子圖的結(jié)點(diǎn)度數(shù)均為偶數(shù)，但整個(gè)圖不存在歐拉回路。2.如下圖所示的圖G存在一條歐拉回路．答案：錯(cuò)誤。理由：該圖中存在度數(shù)為奇數(shù)的結(jié)點(diǎn)，不滿足無(wú)向圖存在歐拉回路的充要條件（所有結(jié)點(diǎn)度數(shù)均為偶數(shù)且圖連通），所以圖\(G\)不存在歐拉回路。3.如下圖所示的圖G不是歐拉圖而是漢密爾頓圖．答案：正確。理由：該圖不是歐拉圖，因?yàn)榇嬖诙葦?shù)為奇數(shù)的結(jié)點(diǎn)（如中間度數(shù)為\(3\)的結(jié)點(diǎn)），不滿足歐拉圖的條件。該圖是漢密爾頓圖，存在漢密爾頓回路，比如從左上角的點(diǎn)開(kāi)始，按順時(shí)針或逆時(shí)針順序經(jīng)過(guò)所有點(diǎn)再回到起點(diǎn)，所以該圖不是歐拉圖而是漢密爾頓圖。4.設(shè)G是一個(gè)有7個(gè)結(jié)點(diǎn)16條邊的連通圖，則G為平面圖．答案：錯(cuò)誤。理由：對(duì)于連通平面圖，有歐拉公式\(ve+r=2\)，假設(shè)該圖是平面圖，這里\(v=7\)，\(e=16\)，則\(r=ev+2=167+2=11\)。又因?yàn)槠矫鎴D滿足\(e\leq3v6\)，將\(v=7\)代入得\(3v6=3\times76=15\)，而\(e=16>15\)，不滿足平面圖的條件，所以\(G\)不是平面圖。5.設(shè)G是一個(gè)連通平面圖，且有6個(gè)結(jié)點(diǎn)11條邊，則G有7個(gè)面．答案：正確。理由：根據(jù)歐拉公式\(ve+r=2\)，已知\(v=6\)，\(e=11\)，則\(r=ev+2=116+2=7\)，所以\(G\)有\(zhòng)(7\)個(gè)面。（四）計(jì)算題1.設(shè)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)寫(xiě)出其鄰接矩陣；(3)求出每個(gè)結(jié)點(diǎn)的度數(shù)；(4)畫(huà)出其補(bǔ)圖的圖形。解答：(1)\(G\)的圖形表示如下：```v1\\v3/\/\v2v4/\/\v5```(2)鄰接矩陣為：\[\begin{pmatrix}0&0&1&0&0\\0&0&1&1&0\\1&1&0&1&1\\0&1&1&0&1\\0&0&1&1&0\end{pmatrix}\](3)\(deg(v1)=1\)，\(deg(v2)=2\)