图 论 部 分 自 测 题
2012年11月14日
一、内容提要
1、基本概念：
图：无向图，有向图，关联，邻接，零图，平凡图，环（自回
路），平行边，结点度数（度数、入度、出度），简单图，多重图，正则图，完全图，子图（子图、真子图、生成子图），图的同构. 路：回路，通路（初级通路，简单通路），通路的长度，闭通路（圈也即初级回路，简单回路），结点之间的连通性与可达性，无向图的连通性，有向图的连通性（弱连通、单向连通、强连通）。
邻接矩阵，可达矩阵，关联矩阵.
树，森林，生成树，生成树的权，最小生成树，破圈法，避圈法.有向树，根树，有序树，根树高度，带权树，最优二叉树，求最优二叉树的方法，前辍码，求前辍码的方法.二叉排序树。 2、主要定理：
Th1 每个图G=<，E>中，结点总度数等于边数的两倍， deg(直通春晚第三场)=2|E|.
Th2 在任何图中，度数为奇数的结点个数为偶数.
以上常称为握手定理及推论.
Th3 在有向图中所有结点的入度之和等于所有结点的出度之和
Th4 n个结点的无向完全图Kn的边数为
有向完全图_________________
Th5 在有n个结点的简单图中，如果从结点i到结点j存在一条路，则从结点i到结点j必存在一条长度小于等于n-1的路. 推论 在有n个结点的图中，若从结点i到结点j存在一条中路，则必存在一条从i到j而长度小于n的基本通路.
Th7 在有n个结点的简单图中，若i到自身存在回路，则从i到自身存在长度小于等于n的回路.
推论 在有n个结点的图中，若i到自身存在回路，则从i到自身存在长度小于等于n的闭通路(基本回路).
Th10 设A(G)是图G的邻接矩阵，则(A(G))L中的第i行j列元素等于G中联结i与j的长度为L的路的数目.
Th20 (n,m)无向图G是树，当且仅当G连通且m=n-1.
Th21 (n,m)无向图G是树，当且仅当G中无回路且m=n-1.
Th22 连通无向图G是树，当且仅当G中任何一对结点间恰有一条基本通路.
Th23 无向图G为树，当且仅当G中无回路且对G中任两点i, j间加一条边(i, j)则形成唯一的初级回路.
Th24 设T为结点数为n(n≥2)的无向树，则T中至少有两片叶子.
Th30 任一棵二叉树的树叶可对应一个前辍码；任一个前辍码都对应一棵二叉树.
二 自测题
Ⅰ1、 单项选择题（35题）
1、 仅由孤立点组成的图称为( 1 )
(1)零图； (2)平凡图；
(3)完全图； (4)多重图.
2、 仅由一个孤立点组成的图称为( 2 )
(1)零图； (2)平凡图；
(3)多重图； (4)子图.
3、 在任何图G=<,E>中，结点总度数与边数的关系为( 3 )
(1) =2|E|; (2) =|E|;
(3) (4)
4、 在任何图G中必有偶数个( 2 )
传染病信息报告管理规范(1)度数为偶数度的结点；(2)度数为奇数度的结点；
(3)入度为奇数的结点；(4)出度为奇数的结点.
5、 设G为有n个结点的无向完全图，则G的边数为(3 )
(1)n(n-1); (2)n(n+1);
(3)n(n-1)/2; (4)(n-1)/2
6、 设G=<，E>为无向图，||=7，|E|=23，则G一定是( 4 )
(1)完全图； (2)零图；
(3)简单图； (4)多重图.
7、 下面哪一个图是简单图( 1 )
(1)G1=<｛1, 2, 3, 4｝,｛<1, 2>,<2, 1>,<3, 4>,<2, 3>｝>;
(2)G2=<｛端粒和端粒酶1, 2, 3, 4｝,｛<1, 2>,<2, 2>,<3, 2>,<3, 1>｝>;
(3)G3=<｛1, 2, 3, 4｝,｛(1, 2),( 3, 1),( 3, 4),( 2, 1)｝>;
(4)G4=<｛1, 2, 3, 4｝,｛(1, 2),( 1, 3),( 3, 3)｝>.
8、 图G和G’的结点和边分别存在一一对应关系是GG’(同构)的( 2 )
(1)充分条件； (2)必要条件；
(3)充分必要条件； (4)既不充分也不必要条件.
9、 含5个结点，3条边的简单图有( 3 )
（1）2个； (2)3个；
(3)4个； (4)5个.
10、 设G=<,E>为简单图，||=n, (G)为G的最大度，则有( 1 )
(1) (G)<n; (2) (G)≤n;
(3) (G)>n; (4) (G)≥n.
11、 设图G=<,E>为任意图，则有(1 )
(1)E×; (2)E×;
(3)×E; (4)×=E.
12、 给定下列序列，哪一个可构成无向简单图的结点度数序列( 2 )
(1)(1,1,2,2,3); (2)(1,1,2,2,2);
(3)(0,1,3,3,3); (4)(1,3,4,4,5).
13、 设图C为(n,m)图，且G的每个结点的度数不是k就是k+1，若G
中有Nk二十四画品个k度结点，则Nk为( 4 )
(1)n/2; (2)n(n+1);
(3)n·k; (4)n(k+1)-2m.
14、 完全图K4的所有非同构的生成子图中，有几个是3条边的( 2 )
(1)1; (2)3;
(3)4; (4)2.
15、 设G=<,E>为无向图，u, ，若u,连通，则( 4)
(1)d(u,)>0; (2)d(u,)=0;
(3)d(u,)<0; (4)d(u,)≥0.
16、 任何无向图G中结点的连通关系是( 2 )
(1)偏序关系； (2)等价关系；
(3)既是偏序关系又是等价关系；
(4)既不是偏序关系又不是等价关系.
17、 有向图G=<,E>，其中=｛a,b,c,d,e,f｝
E=｛<a,b>,<b,c>,<a,d>,<d,e>,<f,e>｝是( 3 )
(1)强连通图； (2)单侧连通图；
(3)弱连通图； (4)不连通图.
18、 设=｛a,b,c,d｝，则与下面哪个边集能构成强连通图( 1 )
(1)E1=｛<a,d>,<b,a>,<b,d>,<c,d>,<d,c>｝;
(2)E2=｛<a,d>,<b,a>,<b,c>,<b,d>,<d,c>｝;
(3)E3=｛<a,c>,<b,a>,<b,c>,<d,a>,<d,c>｝;
(4)E4=｛<a,b>,<a,c>,<a,d>,<b,d>,<c,d>｝.
19、 设||=n(n-1),G=<,E>是强连通图，当且仅当( 4)
(1)G中至少有一条路；codysafe
(2)G中至少有一条回路；
(3)G中有通过每个结点至少一次的路；
(4)G中有通过每个结点至少一次的回路.
20、 在有n个结点的连通图G中，其边数( 2 )
(1)最多有n-1条； (2)至少有n-1条；
(3)最多有n条； (4)至少有n条.
21、 设A(G)是有向图E=<,E>的邻接矩阵，其中第i行中值为1的元素数目为( 2 )
(1)给点i的入度； (2)给点i的出度；
(3)给点i的度数； (4)给点j的度数.
22、 M(G)=(mij)nxm是无向图G=<,E>的关联矩阵， i是G中的孤立点，则( 1 )
(1) i对应的一行元素全为0；(2) i对应的一行元素全为1
(3) i对应的一列元素全为0；(4) i对应的一列元素全为1.
23、 M(G)=(mij)nxm是有向图G=<,E>的关联矩阵，若mij=1，则在图G中( 1 )
(1) i是ej的起点； (2) i是ei的起点；
(3) i是ei的终点； (4) i是ei的终点执法公信力.
24、 若G是有n个结点的连通图，则其完全关联矩阵的秩为( 2 )
(1)n; (2)n-1;
(3)n+1; (4)n2.
25、 G=<,E>是简单有向图，可达矩阵P(G)刻划下列哪种关系( 1 )
(1)点与点； (2)点与边；
(3)边与点； (4)边与边.
26、邻接矩阵具有对称性的图一定是( 2 )
(1)有向图; (2)无向图;
(3)混合图; (4)简单图.
27、 下面哪一种图不一定是树( 3 )
(1)无回路的连通图；
(2)有n个结点n-1条边的连通图；
(3)每对结点间都有通路的图；
(4)连通但删去一条边则不连通的图.
28、 设G=<,E>为<n,m>连通图，则要确定G的一棵生成树必删去G中的边数为(3)
(1)n-m-1; (2)n-m+1;
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议