C．不包含在G的任一简单回路中 D．不包含在G的某一回路中
14．设无向图G中有5条边，已知G中度为2的结点有2个，其余结点的度为3，则G中共有( C )个结点。 A．6 B．6 C．4 D．10
15．图G与G?的结点和边分别存在一一对应的关系是G与G?同构的( B ) A．充分条件 B．必要条件
C．充要条件 D．既不是充分条件也不是必要条件
16、设D??V,E?为有向图，则有( A )
A．E?V?V B．E?V?V C．V?V?E D．V?V?E 17、含有5个结点、3条边的不同构的简单图有( C )个 A．2 B．3 C．4 D．5 18、设G为有n个结点的简单图，则有( A )
A．??G??n B．??G??n C．??G??n D．??G??n
19、设G?n,m?，且G中每个结点的度数不是k就是k?1，则G中度为k的结点的个数
是( D )
nA． B．n?n?1? C．nk D．n?k?1??2m
220、给定下列序列，( B )可以构成无向简单图的结点度数序列。
A．?1,1,2,2,3? B．?1,1,2,2,2? C．?0,1,3,3,3? D．?1,3,4,4,5?
21、n个结点可构造的简单无向图（含同构图）的个数是(D ) A．2 B．2 C．n D．2nn2n?n?1?22（完全图的边集的子集数目）
22、K4中含有3条边的不同构生成子图有( 3 )个 A．1 B．3 C．4 D．2
23、若简单图G与其补图G同构，称G为自同构。则含有5个结点的不同构的无向自补图的个数为 (C)
5
A．0 B．1 C．2 D．3
24、设G??V,E?为无向图，u,v?V，若u,v连通，则 (D)
A．d?u,v??0 B．d?u,v??0 C．d?u,v??0 Dd?u,v??0． 25、任何无向图中结点间的连通关系是 (B)关系 A．偏序 B．等价 C．相容 D．拟序
26、设D??V,E?为有向图，E???a,b?,?b,c?,?a,d?,?d,e?,?f,e??，
V??a,b,c,d,e,f?,则D??V,E?是 ( C)
A．强连通图 B．单向连通图 C．弱连通图 D．不连通图 27、设V?1,D??V,E?是强连通图，当且仅当 (D)
A．D中至少有一条通路 B．D中有通过每个结点至少有一条通路 C．D中至少有一条回路 D．D中有通过每个结点至少有一条回路 28、无向图G中边e是G的割边的充要条件是 (C)
A．e不包含在G的某一回路中 B．e是重边 C．e不包含在G的任一简单回路中 D．e不是重边 29、在有n个结点的连通图中，其边数(B)
A．最多有n?1条 B．至少有n?1条 C．最多有n条 D．至少有n条 30、欧拉回路是 (B)
A．既是基本回路也是简单回路 B．简单回路 C．既非基本回路也非简单回路 D．路径 31、哈密顿回路是 (A)
A．既是基本回路也是简单回路 B．简单回路 C．既非基本回路也非简单回路 D．路径 32、设G??n,m?是欧拉图，则n,m有关系 (D) A．n?m B．n,m的奇偶性必相同 C．n,m的奇偶性必相反 D．n,m的奇偶性既可相同也可相反
33、下列命题中， (D)是正确的
A．欧拉图是哈密顿图 B．哈密顿图是欧拉图 C．平面图是树 D．树是平面图 34、5阶无向完全图的边数为(B)
A．5 B．10 C．15 D．20 35、n个结点的无向完全图的边数为(D)
1A．n?n?1? B．n2 C．2n D．n?n?1?
236、下列三元数组为图的结点数、边数和面数，则 (C)不能构成连通平面图 A．(4,4,2) B．?4,5,3? C．?9,6,6? D．?7,8,3?
6
37、一个无向图有4个结点，其中3个度数为2，3，3，则第4个结点度数不可能是 (B)
A．0 B．1 C．2 D．4
38、连通简单无向图有17条边，则该图至少有 (C)个结点 A．5 B．6 C．7 D．8 （因
n?n?1?2?17）
39、已知有向图如右所示，其可达矩阵P??pij?6?6中，(C)?1 A．p15 B．p25 C．p35 D．p45 40、二部图K2,3是 (D)
142563A．欧拉图 B．哈密顿图 C．非平面图 D．平面图
同步测试卷11:特殊图与应用
一．填空：
1．一个连通无向图G是欧拉图，当且仅当G中所有结点的度数为 偶数 。 2．在一个连通无向图G是欧拉图中，当且仅当结点vi和vj的度为 奇数 ，其余结点的度均为 偶数 ，结点vi和vj之间才存在欧拉路径。
3．设G=
的边集M为G的一个 匹配 。
4．无向图G有生成树的充要条件是G 连通 。
5．如果T是无向图G的一棵生成树，则T中的边称为 树枝 _，属于G但不属
于T的边称为T的_连枝（弦）_。
6．在根树中，从根到结点v的距离称为该结点的 层次 ，从根到叶结点的最大
距离称为树的 高度 。
7．设G是(n,m)无向简单连通，用避回路法求G的一棵生成树，必须在G中选
择n?1条边且不构成回路。
8．设G是(n,m)无向简单连通，用破回路法求G的一棵生成树，必须在G中去
掉m?n?1。
9．连通图G是一棵树，当且仅当G中每一条边均为_割边_。
10．无向图G是由k?k?2?棵树组成的森林，至少要添加k?1条边才能使G成为一棵树。
11．设A是根树T的邻接矩阵，则矩阵A中行全为0所对应的结点为_树叶__，
列全为0所对应的结点为_树根_。 12．设A是一棵k元树的邻接矩阵，则矩阵A的所有行中1的个数最多为k个。
7
13．设G是个连通无向图，e是G中的一条边，如果边e包含在G的任何一棵
生成树中，则e必为G的一条_割边 ，不包含在G的任何生成树中的边一定是_自环 。 14．设T是具有n个结点的一棵完全二元树，则T中树叶数为
n?1。 2n?1，内结点数2为
15、连通图G是一棵树，当且仅当每条边 为割边
16、无向图G具有生成树，当且仅当G是连通的。若G为?n,m?连通图，要确定G的一棵生成树必删去G的m?n?1条边（称m?n?1为G的环秩） 17、无向图G是由k?k?2?棵树组成的森林，至少要添加k?1条边才能使G成为一棵树。
18、设G??V,E?是无向连通图，e?E，若e在G的任何生成树中，则e为G的一条割边，若e不在G的任何生成树中，则e为G的一个环 19、设T是高为k的二元树，则T的最大结点数为2k?1?1
20、一个简单有向图是根树，它的邻接矩阵必满足主对角线上元素全为0；矩阵中有一列元素全为0，其它各列中都恰有一个1。
21、一个简单树是根树，它的邻接矩阵中全0列所对应的结点为树根；全0行所对应的结点为树叶。
22、一棵有ni个i度分支点?i?2,3,?,k?，则它有n3?2n4????k?2?nk?2片树叶。
二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。
2. 欧拉路径一定是简单路径。 （ √ ） 2． 哈密顿路径一定是简单路径。 （ × ）
3、 若有向图G是强连通图，则G一定是个欧拉图。 （ × ） 4. 若有向图G是欧拉图，则G必是个强连通图。.( √ )
5. 如果能将无向图G画在平面上，若边与边之间有交叉，则G必为非平面图。.( × ) 6． 一个连通赋权图的最小生成树不是唯一的。.( √ )
7. 若G是个连通图，且e是G的割边，则边e必包含在G的每棵生成树中。( √ ) 8． 设图G是有n个结点、n?1条边的无向图，则G一定是树。( × )
9． 设G=(n,m)是个无向图，若去掉任何一条边G的支有所增加，则G必为树。( × )
10． 设G=(n,m)是个无向图，若G无回路且m?n?1，则G必为根树。( √ )
8