国家开放大学《离散数学》形考任务2

《离散数学》形考任务二一、单项选择题图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}是点割集{d}是点割集C.e是割点D.{b,e}是点割集正确答案是：e是割点设G是连通平面图，有v个结点，e条边，r个面，则r=( )．e－v＋2v＋e－2C.e＋v＋2D.e－v－2正确答案是：e－v＋2A.设图G＝<V,则下列结论成立的是( )．A.C.B.deg(v)=2|E|C.正确答案是：D.deg(v)=|E|正确答案是：已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( 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个结点，则T的边数为( A.6B.9C.7D.8正确答案是：7

)条边，才能确定G的设无向图G的邻接矩阵为则G的边数为( A.5B.4C.3D.6正确答案是：5无向图G存在欧拉回路，当且仅当（ ）．A.G连通且所有结点的度数全为偶数B.G连通且至多有两个奇数度结点C.G中所有结点的度数全为偶数D.G中至多有两个奇数度结点正确答案是：G连通且所有结点的度数全为偶数以下结论正确的是( )．A.有n个结点n－1条边的无向图都是树B.无向完全图都是平面图C.无向完全图都是欧拉图D.树的每条边都是割边正确答案是：树的每条边都是割边已知无向图G的邻接矩阵为则G有（ ）．A.68B.57C.67D.58GG)．A.14B.1C.7D.6正确答案是：7若G是一个汉密尔顿图，则G一定是()．连通图B.欧拉图C.对偶图D正确答案是：连通图图六设有向图（b）（c）与如图六所示，则下列结论成立的( )．图六A.（c）只是弱连通的B.（a）只是弱连通的C.（b）只是弱连通的D.（d）只是弱连通的正确答案是：（d）只是弱连通的无向完全图K4是（ A.汉密尔顿图树欧拉图非平面图正确答案是：汉密尔顿图设有向图（b）（c）与如图五所示，则下列结论成立的( )．A.（d）是强连通的B.（c）是强连通的C.（b）是强连通的D.（a）是强连通的正确答案是：（a）是强连通的无向简单图G是棵树，当且仅当( )．A.G的边数比结点数少1B.G连通且结点数比边数少1C.G中没有回路．D.G连通且边数比结点数少1正确答案是：G连通且边数比结点数少1二、判断题设G是一个连通平面图，且有6个结点11条边，则G有7个面．( )正确答案是“对”。设G是一个有7个结点16条边的连通图，则G为平面图．( 正确答案是“错”。无向图G的结点数比边数多1，则G是树．( 正确答案是“错”。无向图G存在欧拉回路，当且仅当G连通且结点度数都是偶数．( 正确答案是“对”。设完全图K有n个结点条边当n为奇数时中存在欧拉回路正确答案是“对”。结点数v与边数e满足e=v的无向连通图就是树．( 正确答案是“错”。设G=<V，E>是具有n个结点的简单图，若在G中每一对结点度数之和小于1，则在G中存在一条汉密尔顿路．( )正确答案是“错”。G=<V,E>VS，GSWS|W满足的关系式为)正确答案是“对”。设图G是有5个结点的连通图，结点度数总和为10，则可从G中删去6条边使之变成树．( )正确答案是“错”。设连通平面图G的结点数为5，边数为6，则面数为4．( 正确答案是“错”。如图九所示的图G不是欧拉图而是汉密尔顿图．( )正确答案是“对”。已知图G中有1个1度结点个2度结点，3个3度结点，4个4度结点，则G的边数是15．( )正确答案是“对”。若图G=<V,E>，其中V={a,b,c,d}，E={(a,b),(a,d),(b,c),(b,d)}，则该图中的割边为(b,c)．( )正确答案是“对”。两个图同构的必要条件是结点数相等边数相等度数相同的结点数相等正确答案是“对”。如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路正确答案是“错”。设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去4条边使之变成树．( )正确答案是“对”。汉密尔顿图一定是欧拉图