《离散数学 》习题6-1

第1页共8页第六章一、单选题1、n阶完全图结点v的度数为（）。A．n；B．n-1；C．n+1；D．2(n-1)2、如果无向图G中（），则称G是个简单无向图。A．无回路B．无自环C．无多重边D．无自环且无多重边3、设n阶图G中有m条边，每个结点的度数是k或k+1，若G中有Nk个k度顶点，Nk+1个k+1度顶点，则Nk=（）。A．n(k+1)-2m；B．2m(k+1)-n；C．2n(k+1)-m；D．m(k+1)-2n4、无向图中有16条边，且每个结点的度数均为2，则结点数是（）．A．8B．16C．4D．325、在具有n个结点的无向连通图中，（）。A．恰好有n条边；B．至少有条边；C．最多有n条边；D．至少有n条边6、下面哪个图是强连通的（）．7、任何无向图G中结点间的连通关系是（）。A.良序关系 B.偏序关系C.全序关系 D.等价关系8、设有向图，其中，则G是（）。A．强连通图B．单向连通图C．弱连通图D．非连通图9、设是有向图的邻接矩阵，其第列中“1”的数目为（）．A．结点的度数； B．结点的出度；C．结点的入度； D．结点的度数。10、设图G有5个结点，若各结点的度数分别为：3,4,6,2,3,则G有（）条边。A．10；B．20；C．9；D．18．11、设是图的邻接矩阵，，则为（）．A．结点的度数；B．结点的度数；C．结点的入度；D．图中由到长度为的路径的条数．12、设为无向图，=7，=23，则G一定是（）。A．完全图；B．树；C．简单图；D．多重图13、设有向图，其中，，则G是（）。A．强连通图B．单向连通图C．弱连通图D．非连通图14、设A为图G的邻接矩阵，的主对角线元素之和为600，则G上有（）个三角形。A．100；B．200；C．300；D．60015、下面四组数能构成无向图的度数列的有（）。A．2,3,4,5,6,7；B．1,2,2,3,4；C．2,1,1,1,2；D．3,3,5,6,016、n阶完全图的边数为（）。A．n(n-1)/2；B．n-1；C．n+1；D．2n(n-1)二、填空题1、在任何图中，其奇数度结点的个数必为。2、在任何有向图中，=。3、完全图K5的连通分支数是。4、在右图中，结点v5的度数是。5、无向图中有10条边，且每个结点的度数均为4，则结点数是．6、设是图的邻接矩阵，，则图中由到长度为的路径的条数为．7、设图G=〈V，E〉，V＝｛,,,｝的邻接矩阵A(G)=，则的入度为。8、完全图K5的边数是。9、在右图中，结点v2的度数是。10、设是图的邻接矩阵，，则图中由到长度为2的路径的条数为．11、在任何图中，=。12、设图G=〈V，E〉，V＝｛,,,｝的邻接矩阵A(G)=，则的出度为。13、设图G=〈V，E〉，V＝｛,,,｝的邻接矩阵A(G)=，则从到长度为２的路共有条。三、简答题1、对有向图求解下列问题：1）写出邻接矩阵；2）中长度为3的不同的路有几条？其中不同的回路有几条？2、对有向图求解下列问题：1）写出邻接矩阵；2）中由到长度为2和4的路有几条？3）求出的可达性矩阵。3、对有向图，通过邻接矩阵解下列问题：（1）从到长度为4的路有几条？（2）中长度为3的回路有几条？v1v1v4v2v34、对有向图求解下列问题：1）写出邻接矩阵；2