2023年7月19日发(作者：)

一、单项选择题

1、三个结点最多可以构成__________个非同构的无向简单图。

A．1 B．2 C．3 D．4

2. 下列四组数据中，不能成为任何4阶无向简单图的度数序列的为（ ）

A. 1,1,1,3，

C. 2,2,2,2，

B.3,2,2,3

D. 1,2,3,4

3．无向图的关联矩阵中，每行的元素之和为（ ）。

A．边数的2倍 B．2 C．顶点数 D．顶点的度数

4、二部图（偶图）K2,3是（ ）。

A．欧拉图 B．哈密顿图 C．非平面图 D．平面图

5．3阶无向完全图（K3）不是以下哪种图？（ ）

A．欧拉图 B．平面图 C．二部图 D．哈密顿图

二、填空题

1． 一个无向图有4个结点，4条边，其中的3个顶点度数分别为1，2，3，则第4个结点度数一定是_______。

2、无向完全图K4要成为欧拉图至少要添加_____________条边。

3．完全二部图K2,3是平面图，它的平面嵌入共有______________个面。

4. 一棵无向树T有4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有_____________片树叶。

三、设无向图G有12条边，2个4度顶点，其余顶点度数均为3或2。

（1）计算该图最少有多少个顶点？

（2）画出一棵具有最少顶点的无向图。

四、以下是具有结点V1，V2，V3，V4的有向图的邻接矩阵：

01100101

00021001V4

V1

（1）画出该图；

（2）求长度为2的通路总数和回路总数；

（3）该图是否为欧拉图?

五、右图是具有四个结点的有向图：

（1）写出该图的邻接矩阵、可达矩阵；

V2

V3 （2）求长度为2的通路总数。

（3）判断该图为单向连通还是强连通？

六、右下图为无向图：

（1）它是否为平面图？若是，请画出它的一个平面嵌入图；否则，说明理由。

（2）判断该图是否为哈密尔顿图？请说明理由。

（3）判断该图是否为二部图？请说明理由。

为四边形（次数为4），计算平面图G的边数和面数。

八． 若无向图G是不连通的，证明G的补图是连通图。

b

a

f

e

d

七. 图G是一个简单的连通的平面图，顶点数为8，其无限面的次数为6，其余面都