國家開放大學《離散數(shù)學》形考任務(wù)2

《離散數(shù)學》形考任務(wù)二一、單項選擇題圖G如圖三所示，以下說法正確的是( )．A.{c}是點割集B.a是割點C.{b,c}是點割集D.{b,d}是點割集正確答案是：{b,c}是點割集圖G如圖四所示，以下說法正確的是( )．{(ad)}是割邊{(ad,(bd)}是邊割集{(b,d)}是邊割集{(a,d)}是邊割集正確答案是：{(a,d),(b,d)}是邊割集如圖一所示，以下說法正確的是( )．{(ae)}是邊割集{(ae,(bc)}是邊割集{(ae)}是割邊{(de)}是邊割集正確答案是：{(d,e)}是邊割集如圖二所示，以下說法正確的是( )．{ae}是點割集cn0ckcb是點割集C.e是割點D.{b,e}是點割集正確答案是：e是割點設(shè)G是連通平面圖，有v個結(jié)點，e條邊，r個面，則r=( )．e－v＋2v＋e－2C.e＋v＋2D.e－v－2正確答案是：e－v＋2A.設(shè)圖G＝<V,則下列結(jié)論成立的是( )．A.C.B.deg(v)=2|E|C.正確答案是：D.deg(v)=|E|正確答案是：已知一棵無向樹T中有8個頂點，4度、3度、2度的分支點各一個，T的樹葉數(shù)為( A.4B.5C.3D.8正確答案是：5若G是一個歐拉圖，則G一定是( )．AB.連通圖C.平面圖D正確答案是：連通圖GnG一棵生成樹．A.m-nB.m-n+1C.n-m+1D.m+n+1正確答案是：m-n+1無向樹T有8個結(jié)點，則T的邊數(shù)為( A.6B.9C.7D.8正確答案是：7

)條邊，才能確定G的設(shè)無向圖G的鄰接矩陣為則G的邊數(shù)為( A.5B.4C.3D.6正確答案是：5無向圖G存在歐拉回路，當且僅當（ ）．A.G連通且所有結(jié)點的度數(shù)全為偶數(shù)B.G連通且至多有兩個奇數(shù)度結(jié)點C.G中所有結(jié)點的度數(shù)全為偶數(shù)D.G中至多有兩個奇數(shù)度結(jié)點正確答案是：G連通且所有結(jié)點的度數(shù)全為偶數(shù)以下結(jié)論正確的是( )．A.有n個結(jié)點n－1條邊的無向圖都是樹B.無向完全圖都是平面圖C.無向完全圖都是歐拉圖D.樹的每條邊都是割邊正確答案是：樹的每條邊都是割邊已知無向圖G的鄰接矩陣為則G有（ ）．A.68B.57C.67D.58GG)．A.14B.1C.7D.6正確答案是：7若G是一個漢密爾頓圖，則G一定是()．連通圖B.歐拉圖C.對偶圖D正確答案是：連通圖圖六設(shè)有向圖（b）（c）與如圖六所示，則下列結(jié)論成立的( )．圖六A.（c）只是弱連通的B.（a）只是弱連通的C.（b）只是弱連通的D.（d）只是弱連通的正確答案是：（d）只是弱連通的無向完全圖K4是（ A.漢密爾頓圖樹歐拉圖非平面圖正確答案是：漢密爾頓圖設(shè)有向圖（b）（c）與如圖五所示，則下列結(jié)論成立的( )．A.（d）是強連通的B.（c）是強連通的C.（b）是強連通的D.（a）是強連通的正確答案是：（a）是強連通的無向簡單圖G是棵樹，當且僅當( )．A.G的邊數(shù)比結(jié)點數(shù)少1B.G連通且結(jié)點數(shù)比邊數(shù)少1C.G中沒有回路．D.G連通且邊數(shù)比結(jié)點數(shù)少1正確答案是：G連通且邊數(shù)比結(jié)點數(shù)少1二、判斷題設(shè)G是一個連通平面圖，且有6個結(jié)點11條邊，則G有7個面．( )正確答案是“對”。設(shè)G是一個有7個結(jié)點16條邊的連通圖，則G為平面圖．( 正確答案是“錯”。無向圖G的結(jié)點數(shù)比邊數(shù)多1，則G是樹．( 正確答案是“錯”。無向圖G存在歐拉回路，當且僅當G連通且結(jié)點度數(shù)都是偶數(shù)．( 正確答案是“對”。設(shè)完全圖K有n個結(jié)點條邊當n為奇數(shù)時中存在歐拉回路正確答案是“對”。結(jié)點數(shù)v與邊數(shù)e滿足e=v的無向連通圖就是樹．( 正確答案是“錯”。設(shè)G=<V，E>是具有n個結(jié)點的簡單圖，若在G中每一對結(jié)點度數(shù)之和小于1，則在G中存在一條漢密爾頓路．( )正確答案是“錯”。G=<V,E>VS，GSWS|W滿足的關(guān)系式為)正確答案是“對”。設(shè)圖G是有5個結(jié)點的連通圖，結(jié)點度數(shù)總和為10，則可從G中刪去6條邊使之變成樹．( )正確答案是“錯”。設(shè)連通平面圖G的結(jié)點數(shù)為5，邊數(shù)為6，則面數(shù)為4．( 正確答案是“錯”。如圖九所示的圖G不是歐拉圖而是漢密爾頓圖．( )正確答案是“對”。已知圖G中有1個1度結(jié)點個2度結(jié)點，3個3度結(jié)點，4個4度結(jié)點，則G的邊數(shù)是15．( )正確答案是“對”。若圖G=<V,E>，其中V={a,b,c,d}，E={(a,b),(a,d),(b,c),(b,d)}，則該圖中的割邊為(b,c)．( )正確答案是“對”。兩個圖同構(gòu)的必要條件是結(jié)點數(shù)相等邊數(shù)相等度數(shù)相同的結(jié)點數(shù)相等正確答案是“對”。如果圖G是無向圖，且其結(jié)點度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路正確答案是“錯”。設(shè)圖G是有6個結(jié)點的連通圖，結(jié)點的總度數(shù)為18，則可從G中刪去4條邊使之變成樹．( )正確答案是“對”。漢密爾頓圖一定是歐拉圖