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