离散数学图选择题

1、离散数学（图）选择题您的姓名：填空题*1.每个图中结点度的总和等于边数的（）倍。单选题*A.1B.2（正确答案）C.3D.4.有向图G是强连通图，当且仅当（）单选题*A.图G中至少有一条通路B.图G中有通过每个顶点至少一次的通路C.图G中至少有一条回路D.图G中有通过每个顶点至少一次的回路（正确答案）.有向图 G=,其中 V=a,b,c,d,e,f , E=,是（）。 单选题*A.弱连通图（正确答案）B.单向连通图C.强连通图D.不连通图I设图GI设图G的邻接短若为,则G的顶点数与边数分别为（人单选题*D.（正确答案）.无向图是欧拉图，则（）。单选题*A.该无向图是连通图（正确答案）B.该无向

2、图没有奇度顶点C.A和B同时成立D.以上全错.无向图是欧拉图，则（）。单选题*A.该无向图是连通图B.该无向图没有奇度顶点C.A和B同时成立（正确答案）D.以上全错.无向树简称（）。单选题*A.树（正确答案）B.森林C.结点D.以上全部错误.设G是有n个结点，m条边的连通图，必须删去G的（）条边，才能确定G的一棵 生成树。单选题*m-nm-n+1（正确答案）m+n+1n-m+18. 一个顶点入度为0,其余顶点入度为1的有向树称为（）。单选题*A.根树（正确答案）.环C.孤立点D.分支点.图中没有边关联的顶点称为（）。单选题*A.孤立点（正确答案）B.顶点C.元素D.以上全部错误.无向图中，如果

3、关联一对顶点的无向边多于1条，则这些边称为（）。单选题*A.集合B.平行边（正确答案）C.序偶D.度.在一个图既有有向边又有无向边，该图是（）。单选题*A.有向图B.无向图C.混合图（正确答案）D.以上全部错误.设L是无向图G中的一条通路，L中的顶点各不相同，则L是一条（）单选题*A.简单通路B.初级通路（正确答案）C.简单回路D.初级回路.若D=是连通图，而且vi,vj C V,均有vi vj,则称D是（）。单选题*A.强连通图（正确答案）B.弱连通图C.以上全部正确D.以上全部错误14一已知图G的邻接矩阵为14一已知图G的邻接矩阵为O 1 O 110 110 0 010。11 则G有（）心

4、0 1011110-A 5点，边 B6点，8边单选题*C6点，了边 D5点，7边小单选题*A.B.C.D.（正确答案）.半欧拉图具有（）。单选题*A.欧拉通路（正确答案）B.欧拉回路C都有D.都没有.设T是n阶非平凡的无向树，则T中至少有（）片树叶。单选题*A.1B.2（正确答案）C.3D.4.任何有n个结点m条边的连通无向图G至少有（）棵生成树。单选题*A.mB.nC.1（正确答案）D.m+n.根树T的每个分支点至多有r个儿子，则称T为（）。单选题*A.集合B.序偶C.有向边D.r叉树（正确答案）.如果一个图是简单图则该图不包含（）。单选题*A.平行边B.环C.A和B（正确答案）D.A或者B

5、.如果两个顶点之间有一条有向边，则称这 2个顶点（）。单选题*A.相邻（正确答案）B.相同C.以上全部正确D.以上全部错误.在一个有向图中有10个结点，入度之和可能（）出度之和。单选题*A.小于B.等于（正确答案）C.大于D.不确定22.以下正确的是（）。单选题*A.回路不是通路的特殊情况B.回路是通路的特殊情况（正确答案）C.A和C都正确D.以上全部错误23.若无向图G是平凡图或者G中任何两个顶点都是连通的，则称 G为（）单选题 *A.有向图B.连通图（正确答案）C.集合DM.设A（G）是有向图G=（V, E）的邻接矩阵，其中第i行中值为1的元素数目为（）。 单选题*A.结点Vi的入度B.结

6、点Vi的度数C.结点Vi的出度（正确答案）D.结点Vj的度数.有向图D是欧拉图当且仅当D是强连通的而且每个顶点的入度（）出度。单选 题*A.小于B.等于（正确答案）C.大于D.不确定.连通无回路的无向图称为（）。单选题*A.无向树（正确答案）B.有向树C.森林D.节点.无向图G有生成树当且仅当G是（）。单选题*A.非平凡图B.弱连通图C.强连通图D.连通图（正确答案）28.根树中（）可达根树的任意其他结点。单选题*A.根（正确答案）B.分支点C.树叶D.内点.无向完全图Kn有（）条边单选题*nn2n（n-1）n（n-1）/2（正确答案）.连通无回路的无向图称为（）。单选题*A.无向树B.树C.

7、AB者同寸（正确答案）D.以上全错.在有向图中射入一结点的边数是该结点的（）。单选题*A.入度（正确答案）B.出度C.A和B都正确D.以上全部错误.有向图G是单项连通图，当且仅当（）单选题*A.图G中至少有一条通路B.图G中有通过每个顶点至少一次的通路（正确答案）C.图G的连通分枝数为一D.图G中有通过每个顶点至少一次的回路.设 V=a,b,c,d,e,f）,E=,则有向图 G= 是（）单选题*A.强连通图B.单向连通图C.弱连通图（正确答案）D.不连通图.邻接矩阵具有对称性的图一定是（）单选题*A.有向图B.无向图（正确答案）C.混合图D.简单图.具有哈密顿回路的图称为（）。单选题*A.哈密顿图（正确答案）B.哈密顿回路C.哈密顿通路D.哈密顿.无向图G是树，则其边数大于等于其顶点数减（）。单选题*A.1（正确答案）B.2C.3D.4.设G为n阶m条边的无向连通图，则（）。单选题* TOC o 1-5 h z n+1n+1n-1n-1（正确答案）38.根树T的每个分支点恰好有r个儿子，称T为（）。单选题*A. r叉正则树（