一、单项选择题
1、三个结点最多可以构成__________个非同构的无向简单图。 A．1 B．2 C．3 D．4
2. 下列四组数据中，不能成为任何4阶无向简单图的度数序列的为（ ） A. 1,1,1,3， B.辜鸿铭3,2,2,3
C. 2,2,2,2， 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的有向图的邻接矩阵：
（1）画出该图；
（2）求长度为2的通路总数和回路总数；
五、右图是具有四个结点的有向图：
（1）写出该图的邻接矩阵、可达矩阵；
（2）求长度为2的通路总数。
六、右下图为无向图：
a
f
e
b
d
（1）它是否为平面图？若是，请画出它的一个平面嵌入图；否则，说明理由。（2）判断该图是否为哈密尔顿图？请说明理由。
（3）判断该图是否为二部图？请说明理由。
七. 图G是一个简单的连通的平面图，顶点数惠从冰为8，其无限面的次数为6，其余面都为四边形（次数为4），计算平面图G的边数和面数。
八． 若无向图G是不连通的，证明G的补图是连通图。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议