《图论-自测题13-12-10》由会员分享，可在线阅读，更多相关《图论-自测题13-12-10（13页珍藏版）》请在金锄头文库上搜索。
1、 图 论 部 分 自 测 题 2012年11月14日一、内容提要1、基本概念：图：无向图，有向图，关联，邻接，零图，平凡图，环（自回路），平行边，结点度数（度数、入度、出度），简单图，多重图，正则图，完全图，子图（子图、真子图、生成子图），图的同构.路：回路，通路（初级通路，简单通路），通路的长度，闭通路（圈也即初级回路，简单回路），结点之间的连通性与可达性，无向图的连通性，有向图的连通性（弱连通、单向连通、强连通）。邻接矩阵，可达矩阵，关联矩阵.树，森林，生成树，生成树的权，最小生成树，破圈法，避圈法.有向树，根树，有序树，根树高度，带权树，最优二叉树，求最优二叉树的方法，前辍码，求前辍码的
2、方法.二叉排序树。2、主要定理：Th1 每个图G=中，结点总度数等于边数的两倍，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的回路.推论
3、 在有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(n2)的无向树，则T中至少有两片叶子.Th30 任一棵二叉树的
4、树叶可对应一个前辍码；任一个前辍码都对应一棵二叉树.二 自测题1、 单项选择题（35题）1、 仅由孤立点组成的图称为( )(1)零图； (2)平凡图；(3)完全图； (4)多重图.2、 仅由一个孤立点组成的图称为( )(1)零图； (2)平凡图；(3)多重图； (4)子图.3、 在任何图G=中，结点总度数与边数的关系为( )(1)=2|E|; (2)=|E|;(3) (4)4、 在任何图G中必有偶数个( )(1)度数为偶数度的结点；(2)度数为奇数度的结点； (3)入度为奇数的结点；(4)出度为奇数的结点. 5、 设G为有n个结点的无向完全图，则G的边数为( )(1)n(n-1); (2)n(
5、n+1); (3)n(n-1)/2; (4)(n-1)/26、 设G=为无向图，|=7，|E|=23，则G一定是( )(1)完全图； (2)零图；(3)简单图； (4)多重图.7、 下面哪一个图是简单图( )(1)G1=1,2,3,4,;(2)G2=1,2,3,4,;(3)G3=;(4)G4=.8、 图G和G的结点和边分别存在一一对应关系是GG(同构)的( )(1)充分条件； (2)必要条件； (3)充分必要条件； (4)既不充分也不必要条件.9、 含5个结点，3条边的简单图有( )（1）2个； (2)3个； (3)4个； (4)5个.10、 设G=为简单图，|=n,(G)为G的最大度，则有(
6、 )(1) (G)n; (4)(G)n.11、 设图G=为任意图，则有( )(1)E; (2)E;(3)E; (4)=E.12、 给定下列序列，哪一个可构成无向简单图的结点度数序列( )(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为( ) (1)n/2; (2)n(n+1); (3)nk; (4)n(k+1)-2m. 14、 完全图K4的所有非同构的生成子图中，有几个是3条边的( )(1)1; (2)3;(3)4; (
7、4)2.15、 设G=为无向图，u,，若u,连通，则( )(1)d(u,)0; (2)d(u,)=0;(3)d(u,)0; (4)d(u,)0.16、 任何无向图G中结点的连通关系是( )(1)偏序关系； (2)等价关系； (3)既是偏序关系又是等价关系；(4)既不是偏序关系又不是等价关系.17、 有向图G=，其中=a,b,c,d,e,fE=,是( ) (1)强连通图； (2)单侧连通图； (3)弱连通图； (4)不连通图. 18、 设=a,b,c,d，则与下面哪个边集能构成强连通图( )(1)E1=,;(2)E2=,;(3)E3=,;(4)E4=,.19、 设|=n(n-1),G=是强连通图
8、，当且仅当( )(1)G中至少有一条路；(2)G中至少有一条回路；(3)G中有通过每个结点至少一次的路；(4)G中有通过每个结点至少一次的回路.20、 在有n个结点的连通图G中，其边数( )(1)最多有n-1条； (2)至少有n-1条； (3)最多有n条； (4)至少有n条.21、 设A(G)是有向图E=的邻接矩阵，其中第i行中值为1的元素数目为( ) (1)给点i的入度； (2)给点i的出度； (3)给点i的度数； (4)给点j的度数. 22、 M(G)=(mij)nxm是无向图G=的关联矩阵，i是G中的孤立点，则( ) (1)i对应的一行元素全为0；(2)i对应的一行元素全为1 (3)i对
9、应的一列元素全为0；(4)i对应的一列元素全为1. 23、 M(G)=(mij)nxm是有向图G=的关联矩阵，若mij=1，则在图G中( ) (1)i是ej的起点； (2)i是ei的起点； (3)i是ei的终点； (4)i是ei的终点. 24、 若G是有n个结点的连通图，则其完全关联矩阵的秩为( )(1)n; (2)n-1;(3)n+1; (4)n2.25、 G=是简单有向图，可达矩阵P(G)刻划下列哪种关系( )(1)点与点； (2)点与边；(3)边与点； (4)边与边.26、邻接矩阵具有对称性的图一定是( )(1)有向图; (2)无向图;(3)混合图; (4)简单图.27、 下面哪一种图不
10、一定是树( )(1)无回路的连通图；(2)有n个结点n-1条边的连通图；(3)每对结点间都有通路的图；(4)连通但删去一条边则不连通的图.28、 设G=为连通图，则要确定G的一棵生成树必删去G中的边数为( ) (1)n-m-1; (2)n-m+1; (3)m-n+1; (4)m-n-1.29、 具有4个结点的非同构的无向树的数目为( )(1)2; (2)3;(3)4; (4)5.30、 具有6个结点的非构的无向树的数目为( )(1)4; (2)5;(3)7; (4)8.31、 一棵树有2个2度结点，1个3度结点，3个4度结点，则其1度结点数为( ) (1)5; (2)7; (3)8; (4)9. 32、 一个树有2个4度结点，3个3度结点，其余的结点都是叶子，则叶子数为( ) (1)9; (2)8; (3)7; (4)1
