图论-树自测题.doc

图 论 部 分 自 测 题一、内容提要基本概念：图，无向图，有向图，关联，邻接，零图，平凡图，环（自回路），结点度数（度数、入度、出度），简单图，多重图，正则图，完全图，子图（子图、真子图、生成子图），图的同构.路，回路，通路（初级通路，简单通路），通路的长度，闭通路（圈也即初级回路，简单回路），结点之间的连通性与可达性，无向图的连通性，有向图的连通性（弱连通、单向连通、强连通）。邻接矩阵，可达矩阵，关联矩阵.树，森林，生成树，生成树的权，最小生成树，破圈法，避圈法.有向树，根树，有序树，根树高度，带权树，最优二叉树，求最优二叉树的方法，前辍码，求前辍码的方法.主要定理：Th1 每个图G=中，结点总度数等于边数的两倍，deg()=2|E|.Th2 在任何图中，度数为奇数的结点个数为偶数.定理1，2常称为握手定理及推论.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(n2)的无向树，则T中至少有两片叶子.Th30 任一棵二叉树的树叶可对应一个前辍码；任一个前辍码都对应一棵二叉树.二 自测题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(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的最大度，则有( )(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; (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,f,E=,是( ) (1)强连通图； (2)单侧连通图； (3)弱连通图； (4)不连通图. 18、 设=a,b,c,d，则与下面哪个边集能构成强连通图( )(1)E1=,;(2)E2=,;(3)E3=,;(4)E4=,.19、 设|=n(n-1),G=是强连通图，当且仅当( )(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对应的一列元素全为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、 下面哪一种图不一定是树( )(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)10. 33、 设有33盏灯，拟用一个电源，则至少需要有五插头的接线板数为( ) (1)7; (2)8; (3)9; (4)14. 34、 下面给出的符号串集合中，哪一个是前辍码( )(1)1,01,001,000;(2)1,11,101,001,0011;(3)b,c,aa,bc,aba;(4)b,c,a,aa,ac,abb.35、 下面给出的符号串集合中，哪一个不是前辍码( )(1)0,10,110,1111;(2)01,001,000,1;(3)b,c,aa,ac,aba,abc;(4)0011,001,101,11,1. 2、 填空题（34题）1、 设G为(n,m)图,当 时，称G为零图,当 时，称G为平凡图.答案：2、 在一个图中，若两个结点 ，则称这两点为邻接点，若一个结点 ，则该点称为孤立点.答案：3、 图G为简单无向图，若 ，则G为完全图.无向完全图Kn有 条边. 答案：4、 如图G=和G=，若 ，则G为G的真子图，若 ，则G为G的生成子图. 答案： 5、 在任何图G=中，结点的度数为 ，图G的最大度(G)= ，图G的最小度(G)= . 答案：6、 在任何图G=中，结点度数的总和= ；奇度结点必有 个. 答案： 7、 设图G有6个结点，若各结点的度数分别为：1,4,4,3,5,5，则G有 条边，根据 . 答案：8、 设无向图G=中，|E|=12，若G中有6个3度结点，其余结点度数均小于3，则G中至少有 个结点，根据 . 答案： 9、 设G是(n,m)简单图，是G中度数为k的结点，e是G中一条边，由G-中有 个结点， 条边，G-e中有 条边.答案：10、 在有10个结点的图中(存在不存在) 结点总度数为45的图，因为 . 答案：11、 给定图G，则G的补图为 .答案：12、 设图G=与G=,GG当且仅当 且 .答案：和，E和E存在一一对应关系；保持关联关系.13、 三个结点可构成 ，个不同构的简单无向图， 个简单有向图.答案：14、 在无向图G中，结点间点的连通关系满足 性， 性和 性，是 关系. 答案：15、 设G=为无向连通图，若|=100，|E|=100，则从G中能找到 条回路. 答案：16、 在有向图G中，结点间的可达关系满足性质 .答案：17、 在G为简单有向图，若 ，则G为强连通图，若 ；则G为弱连通图.答案：18、 G是有向图，当且仅当G中有一条要至少通过每个结点一次的回路，G为 图；当且仅当G中有一条通过每个结点的路时，G为 图. 答案：19、 有向图G的邻接矩阵A(G)中，第i行中值为1的元素数目为结点i的 ，第j行中值为1的元素数目为结点j的 . 答案：20、 A(G)为图G=的邻接矩阵，结点i的出度为 ，入度为 ，(A(G)k中的第i行第j列的元素aij(k)为 .答案：21、 G为无向图，M(G)为其关联矩阵，则M(G)中每一列有 个1，每一行中元素的和数是 ，全0元素行对应的结点为 .答案：22、 G为有向图，M(G)为其关联矩阵，则M(G)中每一列中的非零元素为 ，孤立点对应行的元素 . 答案：23、 设图G=,=1,2,3,4的邻接矩阵A(G)= ,则1的入度 ，4的出度 ,从2到4长度为2的路有 条. 答案：24、 一个 图称为树，树叶为 ，树的分枝点为 .答案：25、 若对T是 ，则称T为图G的生成树，树T中的边称为 ， 称为弦. 答案：26、 无向图G具有生成树，当且仅当 ，若G为(n,m)连通图，要确定G的一棵生成树必删去G的 条边. 答案：27、 设G为n个结点的连通图，G的生成树T的权为 ，若T ，则称T为最小生成树. 答案：28、 一棵树有2个2度分枝点，1个3度分枝点，3个4度分枝点，则有 片叶子. 答案：29、 设G=是无向连通图，eE，若e在G的任何生成树中，则e为G的 ，若e不在G的任何生成树中，则e为G的 . 答案：30、 一个有向树T称为根树，若 ，其中 称为树根， 称为树叶. 答案：31、 5个结点可以构成 棵非同构的无向树，又可构成 棵非同构的根树. 答案：32、 设T为根树，若 ，则称T为m叉树；若 ，则称T为m叉完全树；若 ，则称T为m叉正则树. 答案：33、 设T为二叉树，树叶带权分别为w1,wt，其通路长为L(wi)，则T的树权w(t)= ，若 ，则称T为最优树. 答案：34、 设A为一个序列集合，若 ，则称A为前辍码.答案：3、 判断题（正确填T,错误填N）（共24题）1、 仅由一个孤立点构成的图称为平凡图.（ ）2、 仅由一个孤立点构成的图称为零图. （ ）3、 仅由n(n2)个孤立点构成的图称为平凡图. （ ）4、 任一图G=的最大度(G)必小于G的结点数. （ ）5、 简单图G的最大度(G)必小于其结点数. （ ）6、 设图G和图G，GG当且仅当G和G的结点和边分别存在一一对应关系. （ ）7、 在n(n2)个结点的简单图G中，若n个奇数，则G与其补图的奇度结点数一定相同. （ ）8、 在n(n2)个结点的简单图G中，若n个奇数，则G与其补图的奇度结点数不一定相同. （ ）9、 任何具有相同结点数和边数的图都同构. （ ）10、 在无向图中，结点间的连通关系是等价关系. （ ）11、 若图G是连通的，则G的补图必是连通图. （ ）12、 若图G不是连通的，则G的补图也是不连通的. （ ）13、在有向图中，结点间的可达关系满足自反性和传递性. （ ）14、在有向图中，结点间的可达关系是等价关系. （ ）15、 图G的邻接矩阵A(G)中第i行里值为1的元素个数是结点1的入度. （ ）16、设图G为有向图，A(G)是其邻接矩阵，则A(G)是对称的. （ ）17、 图G的关联矩阵M(G)中每一列至少有两个非零元素. （ ）18、图G的可达矩阵P(G)是刻划G中结点到结点的可达关系. （ ）19、G的可达矩阵P(G)是刻划G中的结点到边的可达关系. （ ）20、设图G是有n个结点，n-1条边的无向图，则G为一棵树. （ ）21、 任何树T都至少有两片叶子. （ ）22、 设图G是无向连通图，G的生成子图T称为G的生成树. （ ）23、 0000,0010,010,011,111,01,10是一个前辍码. （ ）24、 000,001,01,10,11是一个前辍码. （ ）4、 简答题（共15题）1 6,6,5,4,3,2,1是否可以是一图的结点度数的序列？为什么？解：2 设G为有6个结点的图，若各结点的度数分别为：1,2,2,3,5,5，那么图G有n条边？根据什么？解：3 试画出所有5个结点，3条边的简单无何图及其对应的补图(不同构).解：4 设无向图G中有12条边，已知G中有3度结点个，其余结点的度数均小于问G中至少有多少个结点？为什么？解：.5 设有七人a,b,c,d,e,f,g.已知a会讲英语，b会计是汉语和英语，c