离散数学_图的基本概念_离散数学图的基本概念

离散数学_图的基本概念由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学图的基本概念”。

1、设简单无向图G是一个有12条边的4—正则图，则G有（）个顶点。

A．3；B．6；C．9；D．122、设图G(p,q)的补图为G(p,q),则下面说法正确的是().A.qqp(p1))B．若G(p,q)连通,则G(p,q)不连通

C．若G(p,q)连通,则G(p,q)不连通D．若G(p,q)不连通,则G(p,q)连通

3、无向图G有12条边,度为2,3,4,5,6的顶点各一个,其余顶点均为悬挂点（度为1的点）,G中悬挂点的个数为.4、设简单无向图G=〈V1，V2〉是二分图，则G中（）奇回路。

A．一定包含； B．一定不包含；C．不一定包含；D.不能确定

5、简单有向图的基础图()简单图.A.一定是B.不一定C.一定不是

6、下列四组数种，可以充当4阶无向简单图度数列的为（）

A．（1，2，3，4）B.（0，2，2，3）C.（1，3，3，3）D.（1，1，2，2）

7、、任何图中必定有偶数个（）。

A．度数为偶数的点；B．入度为奇数的点；

C．度数为奇数的点；D.出度为奇数的点

8、简单图的最大度（）顶点数。

A.大于B.小于C.等于D.以上三个都不是

9、求下图的关联矩阵M（G）及邻接矩阵A（G）。（4分）

10、（7分）设G是简单连通的非完全图, 求证：G中存在三个顶点u,和w, 使u,wEG, 但uwEG.11、设G(p,q)是简单图（p是顶点数量，q是边数量）,且qCP1 求证：G是连通图。

12、已知某有向图G的邻接矩阵如下： 2g7

v11

v20Av30v40

问：（1）画出图G。210010 101010

（2）试用邻接矩阵求G中长度小于等于2的通路的条数，其中回路有几条？

（3）该图是为强连通图还是弱连通图？

13、证明：若图Ｇ是不连通的，则Ｇ的补图G是连通的。