D．f?x??2不是G的自同态映射，因f?2?2??f?2??f?2? 【答案：A】
第七章图论
1．下列说法不对的是（ ）
A．简单图不含平行边和环
B．每个图中，度数为奇数的节点数为偶数 C．有向图中节点的入度等于出度
1D．完全图的边数为n?n?1?
2【答案：C】
2．下列说法不对的是（ ）
A．每个图中节点的度数之和等于边数的两倍
B．有向图的所有节点入度之和等于所有节点的出度之和 C．每一个环，度数增加2
D．一个图的图形表示是唯一的 【答案：D】．
3．下列说法不对的是（ ）
A．两个图同构要求他们的节点和边分别存在一一对应的关系，且保持关联 B．图同构的充分条件是节点数目相同、边数相等，度数相同的节点数相等 C．补图是相对同阶完全图而言的图，阶数一样但变为补充进来的新边。 D．一个完全图的任何两个顶点都有边连接 【答案：B】
4．下列说法不对的是（ ）
A．零图含零个节点 B．边数为零的图为零图 C．平凡图只有一个节点
D．环或自回路可以作为有向边，也可以作为无向边 【答案：A】
5．下列各图是简单图的是( )。
(1) (2) (3) (4)
【答案：（3）】
6．设无向图G有12条边，已知G中3度顶点有6个，其余顶点的度数都小于3，则该图至少有( )个顶点。 A．6 B．8 C．9 D．12
21
【答案：C】
7．称图G′=
8．下列说法不对的是（ ）
A．路是各边首尾相连的通道，可由节点与边来交替表达 B．迹是没有重边的路
C．通路除首尾节点以外不会有重复的节点 D．圈是通路，有很多重复的节点 【答案：D】
9．下列说法不对的是（ ）
A．不连通图得连通度为0
B．存在割点的连通图的连通度为1
C．n个节点的图，若存在路则一定存在长度少于n?1的路
D．完全图Kn的连通度为n?1
【答案：C】
10．下列四个有6个结点的图( )是连通图。
(1) (2) (3) (4)
【答案：（3）】
11．下列说法不对的是（ ）
A．零图的矩阵表示为零矩阵
B．r个节点的连通图的完全关联矩阵的秩为r?1
C．无向简单图的邻接矩阵图是对称的，连通矩阵也是对称的 D．有向简单图的邻接矩阵图也是对称的 【答案：D】
12．下列说法不对的是（ ）
A．强分图可能是一个孤立点
B．强连通图当且仅当有一条至少包含每一个节点一次的通路 C．图的可达性不是等价关系
D．图的最小度不少于边连通度，边连通度不少于点连通度 【答案：B】
13．有向图中结点之间的可达关系是( ) A．自反的，对称的 B．自反的，传递的 C．自反的，反对称的 D．反自反的，对称的 【答案：B】
14．下列说法不对的是（ ）
A．欧拉图可以一笔画成，图要一笔画成则一定要是欧拉图
22
B．欧拉路经过每条边一次且仅有一次，经过的节点可多次 C．汉密尔顿路经过每个节点一次且仅一次，经过的边可多次
D．当且仅当简单图的闭包是汉密顿图时，这个简单图是汉密顿图 【答案：A】
15．下列说法不对的是（ ）
A．无向图为欧拉路则其奇数度节点可以是一个
B．一个图是欧拉图当且仅当它连通且均为偶数度节点
C．当一个图每一对节点的度数之和都大于或等于节点数减一，就有汉密尔顿路 D．若一个图G??V,E?,S?V,S??，G含有汉密尔顿路，则W?G?S??S 【答案：A】
16．下列为欧拉图的是( )
【答案：（4）】 17．．在下列关于图论的命题中，为真的命题是( ) A．完全二部图Kn, m (n ?1, m ?1)是欧拉图 B．欧拉图一定是哈密尔顿图
C．无向完全图Kn（n?3）都是欧拉图 D．无向完全图Kn（n?3）都是哈密尔顿图 【答案：D 】
18．在下列关于图论的命题中，为假的命题是( ) A．完全二部图Kn, m (n , m为非零正偶数)是欧拉图 B．哈密尔顿图一定是欧拉图
C．有向完全图Kn（n?2）都是欧拉图
D．无向完全图Kn（n?3且为奇数）都是欧拉图 【答案：B 】
19．在下列关于图论的命题中，为假的命题是( ) A．n =m且大于1时，完全二部图Kn, m 是哈密尔顿图 B．强连通的有向图都是哈密尔顿图
C．完全二部图Kn, m (n , m为非零正偶数)的欧拉回路含mn条边 D．无向完全图K2n（n?2）至少加n条边才能成为欧拉图 【答案：B 】
23
20．下列说法不对的是（ ）
A．一个有限平面图的次数之和等于边数的两倍
B．平面图G的节点数为v，面数为r，边数为e，则有v-e+r=2
C．G是一个v个节点，e条边的连通简单平面图，则v?3?e?3v?6 D．一个图是平面图，当且仅当他不含有与K3,3或K5在2度节点内同构子图 【答案：B】
21．下列各图为平面图的是（ ）
(1) (2) (3) (4)
【答案：（3） 】
22．设G为任意的连通的平面图，且G有n个顶点，m条边，r个面，则平面图的欧拉公式为( )
A．n – m + r = 2 B．m – n + r = 2 C．n + m – r =2 D．r + n + m = 2 【答案：A】
23．下列不能作为一棵树的度数列的一组数是( ) A．1,1,2,2,3,3,4,4 B．1,1,1,1,2,2,3,3 C．1,1,1,2,2,2,2,3 D．1,1,1,1,2,2,2,3,3 【答案：A】
24．在下列关于图论的命题中，为假的命题是( ) A．6阶连通无向图至少有6棵生成树
B．n阶m条边的无向连通图，对应它的生成树，至少有m-n+1条基本回路 C．高为h的正则二叉树至少有h+1片树叶
D．波兰符号法的运算规则是每个运算符与它前面紧邻的两个数进行运算 【答案：D 】
25．下列四个图中与其余三个图不同构的图是( )
（1） （2） （3） （4） 【答案：（3）】
26．给定无孤立点无向图G的边集：{（1，2），（1，3），（2，3），（2，4），（2，5），（3，4），（3，5）}，找出图G的一棵生成树为( ) A．{（1，2），（1，3），（2，4），（3，5）}
24