图论测试

图论知到章节测试答案智慧树2023年最新长安大学绪论单元测试1.下列选项中正确的是（）.参考答案:图论的研究对象是图;图论中图是顶点集合上的一种二元关系;图的结构是图论的重要研究方向之一;图论中的图由若干给定的顶点及连接某些顶点对的边所构成2.著名的哥尼斯堡七桥问题最初由哪位数学家给出解答（）.参考答案:欧拉3.在任意6个人的聚会上，总有3个人互相认识，或者3个人互不认识.（）参考答案:对4.图论中著名的中国邮递员问题是由中国管梅谷教授提出的.（）参考答案:对5.图论与数学的其他分支形成的交叉研究方向有（）.参考答案:随机图论;代数图论;模糊图论;拓扑图论第一章测试1.四个顶点的非同构简单图有（）.参考答案:11个2.序列称为图序列，如果d是某一个简单图的度序列. 则下列不是图序列的是（）.参考答案:(7,6,5,4,3,2,2);(6,6,5,4,3,3,1)3.设图G有21条边，12个3度顶点，其余顶点的度均为2，则图G的顶点数为（）.参考答案:154.下列哪些矩阵是本题中所给图的邻接矩阵？（）参考答案:;5.本题中所给的两个图G与H不同构.（）参考答案:错第二章测试1.边数比顶点数少1的简单图一定是树.（）参考答案:错2.六个顶点的非同构的树有（）.参考答案:6个3.本题中所给图的非同构生成树的个数等于（）.参考答案:3个4.设G是五个顶点的标号完全图（即给G的每个顶点标号），则G的不同的生成树（注意“不同”是指标号不同，不是不同构）的个数等于（）.参考答案:1255.若G是单圈图（即G是仅含一个圈的连通图）, 则G的边数一定等于它的顶点数.（）参考答案:对第三章测试1.若图G的每条边是割边, 则G是森林.（）参考答案:对2.若H是连通图G的子图, 则H的连通度不超过G的连通度.（）参考答案:错3.若图G没有偶圈, 则G的每个块或是2个顶点的完全图或是奇圈.（）参考答案:对4.设G是有n个顶点m条边的k -边连通图, 则下列一定成立的是（）.参考答案:5.图G的连通度、边连通度和最小度分别为（）.参考答案:3, 4, 4第四章测试1.设M和N是简单图G的两个不同的完美匹配，则由M与N的对称差在G中的边导出子图的每个连通分支必为（）.参考答案:偶数个顶点的圈2.一棵树T可以有两个或者两个以上的完美匹配.（）参考答案:错3.2n个顶点的完全图中不同的完美匹配个数为（）.参考答案:(2n-1)!4.如果每个小伙子恰好认识k个姑娘，而每个姑娘也恰好认识k个小伙子(k >0)，则每个小伙子都能与自己认识的姑娘结婚.（）参考答案:对5.本题中所示图没有完美匹配.（）参考答案:错第五章测试1.本题中所示图能一笔画成（即笔不离纸，线不重复）.（）参考答案:错2.下列哪些是非空连通图G有Euler迹的充分条件（）？参考答案:G没有奇度顶点;G有2个奇度顶点3.如果非空连通图G恰有2个奇度顶点，则G的Euler迹一定是从其中一个奇度顶点出发，终止于另一个奇度顶点.（）参考答案:对4.本题中所示图是Hamilton图.（）参考答案:错5.完全二部图（m, n均大于0）是Hamilton图的充分必要条件是（）.参考答案:m = n第六章测试1.对于控制数为1的n个顶点的图，其控制集中顶点的度为n-1.（）参考答案:对2.下列命题中正确的是（）.参考答案:顶点子集F是图G的点覆盖集当且仅当V(G)\F是G的独立集;一个图的独立数和点覆盖数的和等于它的顶点数目3.下列哪个选项中的集合分别是该图的最大匹配、最小边覆盖集（）.参考答案:4.以下选项中正确的是（）.参考答案:Q是G的极大团的充分必要条件是Q是G的补图中的极大独立集;任意6个人的聚会上, 总有3人互相认识或互不认识5.若I是独立集, 则它是极大独立集的充分必要条件是I是极小控制集.（）参考答案:错第七章测试1.Petersen图的边色数等于（）.参考答案:42.3-正则Hamilton图的边色数为（）.参考答案:33.设H是图G的子图，则H的边色数不超过G的边色数.（）参考答案:对4.Petersen图的色数等于（）.参考答案:35.设G是n个顶点的圈，则G的色多项式 P(G,k) 等于（）.参考答案:第八章测试1.可平面图有可能存在子图是不可平面图.（）参考答案:错2.Petersen图是可平面图.（）参考答案:错3.若地图上每两个地区都相邻，则最多能有几个地区（）.参考答案:4个4.正八面体的顶点数、边数和面数分别为（）.参考答案:6,12,85.从Petersen图中需至少删除几条边才能得到一个可平面子图（）.参考答案:2条第九章测试1.设G是3个顶点的圈，则G的积和多项式为.（）参考答案:对2.完全二部图的谱为（）.参考答案:-3,0,0,0,0,33.五个顶点的完全图的谱为（）.参考答案:4,-1,-1,-1,-14.设G是n（n大于或等于3）个顶点的路，则G的边色数和彩虹连通数分别为（）.参考答案:2, n-15.本题中顶点赋权图的最小权点覆盖集的权等于（）.参考答案:10。

电子科技大学研究生试卷（测试时间：至，共__2_小时）课程名称图论及其使用教师学时60 学分教学方式讲授考核日期_2012__年___月____日成绩 考核方式：（学生填写）一、填空题（填表题每空1分，其余每题2分，共30分)1．n 阶k 正则图G 的边数()m G =______2nk； 2．3个顶点的不同构的简单图共有___4___个；3．边数为m 的简单图G 的不同生成子图的个数有__2___m 个；4. 图111(,)G n m =和图222(,)G n m =的积图12G G ⨯的边数为1221____n m n m +；5. 在下图1G 中，点a 到点b 的最短路长度为__13__；6. 设简单图G 的邻接矩阵为A ，且23112012*********102001202A ⎛⎫⎪⎪⎪= ⎪ ⎪⎪⎝⎭，则图G 的边数为__6__； 7. 设G 是n 阶简单图，且不含完全子图3K ，则其边数一定不会超过2___4n ⎢⎥⎢⎥⎣⎦；8．3K 的生成树的棵数为__3__;9. 任意图G 的点连通度()k G 、边连通度()G λ、最小度()G δ之间的关系为__()()()____k G G G λδ≤≤；10. 对下列图，试填下表（是⨯⨯类图的打〝√ 〞，否则打〝⨯〞）。

① ② ③学号姓名学院……………………密……………封……………线……………以……………内……………答……………题……………无……………效……………………4 5 6 6 4 1 1 2 7 243 ab G 1能一笔画的图 Hamilton 图 偶图 可平面图 ① ⨯ √ ⨯ √ ② ⨯ ⨯ ⨯ √ ③⨯√√ √二、单项选择(每题2分，共10分)1．下面命题正确的是(B )对于序列(7,5,4,3,3,2)，下列说法正确的是：(A) 是简单图的度序列；(B) 是非简单图的度序列; (C) 不是任意图的度序列; (D)是图的唯一度序列.2．对于有向图，下列说法不正确的是(D)(A) 有向图D 中任意一顶点v 只能处于D 的某一个强连通分支中； (B) 有向图D 中顶点v 可能处于D 的不同的单向分支中;(C) 强连通图中的所有顶点必然处于强连通图的某一有向回路中; (D)有向连通图中顶点间的单向连通关系是等价关系。

数据结构——图选择题整理1.设完全图Kn,有n个结点(n≥2),m条边，当()时，K,中存在欧拉回路。

A.m为奇数B.n为偶数C.n为奇数D.m为偶数解析:答案C完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。

n 个端点的完全图有n个端点以及n(n-1)/2条边，因此完全图Kn的每个结点的度都为n-1，所以若存在欧拉回路则n-1必为偶数。

n必为奇数。

选C。

2、若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）A、强连通图B、连通图C、有回路D、一棵树解析：选B对于A，强连通图的概念是在有向图中的。

对于B，连通图证明任意两个顶点之间一定能够相连，因此一定可以到达。

对于C，有环图不一定是连通图不一定任意两个顶点均能到达。

对于D，树是可以，但是不是树也可以，题目中说的太肯定了，不能选，比如下图就不是树，但可以完成题目中要求的功能。

2、对于一个有n个顶点的图：若是连通无向图，其边的个数至少为（）；若是强连通有向图，其边的个数至少为（）A、n-1,nB、n-1,n(n-1)C、n,nD、n,n(n-1)解析：选A对于连通无向图，至少需要n-1条边。

对于强连通有向图，只要能形成一个大环就可以从任意一点到另一点。

3、设有无向图G=(V,E)和G'=(V',E')，若G’是G的生成树，则下列不正确的是（）a.G'为G的连通分量b.G'为G的无环子图c.G'为G的极小连通子图且V'=VA、a和bB、只有cC、b和cD、只有a解析：选D极大连通子图简称连通分量，生成树是极小连通子图。

故a不对，c对。

生成树无环，故b对4.带权有向图G用邻接矩阵存储，则vi的入度等于邻接矩阵中（）A、第i行非∞的元素个数B、第i列非∞的元素个数C、第i行非∞且非0的元素个数D、第i列非∞且非0的元素个数解析：选D带权有向图的邻接矩阵中，非0和∞的数字表示两点间边的权值。

图 论 部 分 自 测 题2012年11月14日一、内容提要1、基本概念：图：无向图，有向图，关联，邻接，零图，平凡图，环（自回路），平行边，结点度数（度数、入度、出度），简单图，多重图，正则图，完全图，子图（子图、真子图、生成子图），图的同构.路：回路，通路（初级通路，简单通路），通路的长度，闭通路（圈也即初级回路，简单回路），结点之间的连通性与可达性，无向图的连通性，有向图的连通性（弱连通、单向连通、强连通）。

邻接矩阵，可达矩阵，关联矩阵.树，森林，生成树，生成树的权，最小生成树，破圈法，避圈法.有向树，根树，有序树，根树高度，带权树，最优二叉树，求最优二叉树的方法，前辍码，求前辍码的方法.二叉排序树。

2、主要定理：Th 1 每个图G=<υ，E>中，结点总度数等于边数的两倍，∑∈ννdeg(υ)=2|E|.Th 2 在任何图中，度数为奇数的结点个数为偶数.以上常称为握手定理及推论.Th 3 在有向图中所有结点的入度之和等于所有结点的出度之和Th 4 n 个结点的无向完全图K n 的边数为).1(21-n n有向完全图_________________Th 5 在有n 个结点的简单图中，如果从结点υi 到结点υj 存在一条路，则从结点υi 到结点υj 必存在一条长度小于等于n-1的路.推论 在有n 个结点的图中，若从结点υi 到结点υj 存在一条中路，则必存在一条从υi 到υj 而长度小于n 的基本通路.Th 7 在有n 个结点的简单图中，若υi 到自身存在回路，则从υi 到自身存在长度小于等于n 的回路.推论 在有n 个结点的图中，若υi 到自身存在回路，则从υi 到自身存在长度小于等于n 的闭通路(基本回路).Th 10 设A(G)是图G 的邻接矩阵，则(A(G))L 中的第i 行j 列元素)(L ij a 等于G 中联结υi与υj 的长度为L 的路的数目.Th 20 (n,m)无向图G 是树，当且仅当G 连通且m=n-1.Th 21 (n,m)无向图G 是树，当且仅当G 中无回路且m=n-1.Th 22 连通无向图G 是树，当且仅当G 中任何一对结点间恰有一条基本通路.Th 23 无向图G 为树，当且仅当G 中无回路且对G 中任两点υi ,υj 间加一条边(υi , υj )则形成唯一的初级回路.Th 24 设T 为结点数为n(n ≥2)的无向树，则T 中至少有两片叶子.Th 30 任一棵二叉树的树叶可对应一个前辍码；任一个前辍码都对应一棵二叉树.二 自测题Ⅰ1、 单项选择题（35题）1、 仅由孤立点组成的图称为( 1 )(1)零图； (2)平凡图；(3)完全图； (4)多重图.2、 仅由一个孤立点组成的图称为( 2 )(1)零图； (2)平凡图；(3)多重图； (4)子图.3、 在任何图G=<υ,E>中，结点总度数与边数的关系为( 3 ) (1)V v v ∈)deg(=2|E|; (2)V v v∈)deg(=|E|;(3)∑∈=V v E v |;|2)deg( (4)∑∈=Vv E v .||)deg( 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)/26、 设G=<υ，E>为无向图，|υ|=7，|E|=23，则G 一定是( 4 )(1)完全图； (2)零图；(3)简单图； (4)多重图.7、 下面哪一个图是简单图( 1 )(1)G 1=<｛υ1,υ2,υ3,υ4｝,｛<υ1,υ2>,<υ2,υ1>,<υ3,υ4>,<υ2,υ3>｝>;(2)G 2=<｛υ1,υ2,υ3,υ4｝,｛<υ1,υ2>,<υ2,υ2>,<υ3,υ2>,<υ3,υ1>｝>;(3)G 3=<｛υ1,υ2,υ3,υ4｝,｛(υ1,υ2),(υ3,υ1),(υ3,υ4),(υ2,υ1)｝>;(4)G 4=<｛υ1,υ2,υ3,υ4｝,｛(υ1,υ2),(υ1,υ3),(υ3,υ3)｝>.8、 图G 和G ’的结点和边分别存在一一对应关系是G ≅G ’(同构)的( 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中有N k 个k 度结点，则N k 为( 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中至少有一条路；(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)=(m ij)nxm是无向图G=<υ,E>的关联矩阵，υi∈υ是G中的孤立点，则( 1 ) (1)υi对应的一行元素全为0；(2)υi对应的一行元素全为1(3)υi对应的一列元素全为0；(4)υi对应的一列元素全为1.23、M(G)=(m ij)nxm是有向图G=<υ,E>的关联矩阵，若m ij=1，则在图G中( 1 )(1)υi是e j的起点； (2)υi是e i的起点；(3)υi是e i的终点； (4)υi是e i的终点.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;(3)m-n+1; (4)m-n-1.29、具有4个结点的非同构的无向树的数目为( 1 )(1)2; (2)3;(3)4; (4)5.30、具有6个结点的非构的无向树的数目为( 3 )(1)4; (2)5;(3)7; (4)8.31、一棵树有2个2度结点，1个3度结点，3个4度结点，则其1度结点数为(4) (1)5; (2)7;(3)8; (4)9.32、一个树有2个4度结点，3个3度结点，其余的结点都是叶子，则叶子数为( 1 )(1)9; (2)8;(3)7; (4)10.33、设有33盏灯，拟用一个电源，则至少需要有五插头的接线板数为( 2 )(1)7; (2)8;(3)9; (4)14.34、下面给出的符号串集合中，哪一个是前辍码( 1 )(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、下面给出的符号串集合中，哪一个不是前辍码( 4 )(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=<υ,E>和G’=<υ’,E’>，若，则G’为G的真子图，若，则G’为G的生成子图.5、在任何图G=<υ,E>中，结点υ的度数为，图G的最大度∆(G)= ，图G的最小度δ(G)= .6、 在任何图G=<υ,E>中，结点度数的总和∑∈Vv v )deg(= ；奇度结点必有 个.7、 设图G 有6个结点，若各结点的度数分别为：1,4,4,3,5,5，则G 有条边，根据8、 设无向图G=<υ,E>中，|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=<υ,E>与G ’=<υ’,E ’>,G ≅G ’当且仅当 且 .答案：[υ和υ’，E 和E ’存在一一对应关系；保持关联关系.]13、 三个结点可构成 ，个不同构的简单无向图， 个简单有向图.14、 在无向图G 中，结点间点的连通关系满足 性， 性和 性，是 关系.15、 设G=<υ,E>为无向连通图，若|υ|=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=<υ,E>的邻接矩阵，结点υi ∈υ的出度为 ，入度为 ，(A(G))k 中的第i 行第j 列的元素a ij (k)为 .21、 G 为无向图，M(G)为其关联矩阵，则M(G)中每一列有 个1，每一行中元素的和数是 ，全0元素行对应的结点为 .22、 G 为有向图，M(G)为其关联矩阵，则M(G)中每一列中的非零元素为 ，孤立点对应行的元素 .23、 设图G=<υ,E>,υ=｛υ1,υ2,υ3,υ4｝的邻接矩阵A(G)=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0001001111011010 ,则 υ 1的入度 ，υ4的出度 ,从υ2到υ4长度为2的路有 条. 一个 图称为树，树叶为 ，树的分枝点为 .24、 若对T 是 ，则称T 为图G 的生成树，树T 中的边称为 ，称为弦. 答案：25、 无向图G 具有生成树，当且仅当 ，若G 为(n,m)连通图，要确定G 的一棵生成树必删去G 的 条边.26、 设G 为n 个结点的连通图，G 的生成树T 的权为 ，若T ，则称T 为最小生成树.27、 一棵树有2个2度分枝点，1个3度分枝点，3个4度分枝点，则有 片叶子.28、 设G=<υ,E>是无向连通图，e ∈E ，若e 在G 的任何生成树中，则e 为G的 ，若e 不在G 的任何生成树中，则e 为G 的 .29、 一个有向树T 称为根树，若 ，其中 称为树根， 称为树叶.30、 5个结点可以构成棵非同构的无向树，又可构成棵非同构的根树.31、设T为根树，若，则称T为m叉树；若，则称T为m叉完全树；若，则称T为m叉正则树.32、设T为二叉树，树叶带权分别为w1,…,w t，其通路长为L(w i)，则T的树权w(t)= ，若，则称T为最优树.33、设A为一个序列集合，若，则称A为前辍码.3、判断题（正确填T,错误填N）（共24题）1、仅由一个孤立点构成的图称为平凡图.（）2、仅由一个孤立点构成的图称为零图. （）3、仅由n(n≥2)个孤立点构成的图称为平凡图. （）4、任一图G=<υ,E>的最大度∆(G)必小于G的结点数.（）5、简单图G的最大度∆(G)必小于其结点数. （）6、设图G和图G’，G≅G’当且仅当G和G’的结点和边分别存在一一对应关系.7、在n(n≥2)个结点的简单图G中，若n个奇数，则G与其补图_G的奇度结点数一定相同.8、在n(n≥2)个结点的简单图G中，若n个奇数，则G与其补图_G的奇度结点数不一定相同.9、任何具有相同结点数和边数的图都同构. （）10、在无向图中，结点间的连通关系是等价关系. （）11、若图G是连通的，则G的补图_G必是连通图. （）12、若图G不是连通的，则G的补图_G也是不连通的（）13、在有向图中，结点间的可达关系满足自反性和传递性（）14、在有向图中，结点间的可达关系是等价关系. （）15、图G的邻接矩阵A(G)中第i行里值为1的元素个数是结点 Ui的入度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、简答题（共12题）1）｛6,6,5,4,3,2,1｝是否可以是一图的结点度数的序列？为什么？解：2）设G为有6个结点的图，若各结点的度数分别为：1,2,2,3,5,5，那么图G有n条边？根据什么？解：3）已知图G的邻接矩阵A如下，试画出图G.A=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0001010000000010100000010解：给出G 的邻接矩阵；求各结点的出、入度；求从结点G 出发长度为3的所有回路.解：(1)G 的邻接矩阵A(G)=(2)结点的入度和出度：a b c d d入度出度(3)从B 出发长度为3的回路有 条：4）求图G=<V,E>的关联矩阵，其中V=｛υ1，υ2，υ3，υ4，υ5｝E=｛<υ2,υ1>,<υ2,υ3>,<υ2,υ4>,<υ2,υ5>,<υ3,υ2>,<υ3,υ1>,<υ5,υ1>,<4,υ5>｝.解：M=5）已知图G 和G ’的关联矩阵分别为M 和M ’，试给出其图形表示.M=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡100010001101011010110101，M ’=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡------100010001101011010110101 解：6) 设无向图G 中有12条边，已知G 中有3度结点个，其余结点的度数均小于问G 中至少有多少个结点？为什么？7) 如果图G 中度数为奇数的结点个数为0或2，则G 一定可一笔画出吗？说明理由.8) 若图G 有n 个结点，n-1条边，G 一定是一棵树吗？为什么？解：9) 由给定权按Huffman 算法构成如下的最优树.1 2 4 6 9 12 15 18 24 461、 填空题1） n ≠0,m=0;n=1,m=0 2）关联一条无(有)向边；不与任何结点邻接]3）每一对结点间都有边相连；n(n-1)/24） G ’是G 的子图，υ’⊂或E ’⊂E;υ’=E ’⊆E5）结点υ关联的边数;max ｛deg(υ)｝|υ∈υ];min ｛deg(υ)|υ∈υ6） 2|E|；偶数 7）11；任图中结点总度数为边数的2倍8） 9；∑∈Vv v )deg(=2|E| 9） n-1;m-k;n;m-110）不存在；任图中结点总度数为偶数11）由G 中所有结点和所有能使G 成为完全图的添加边组成的图12）υ和υ’，E 和E ’存在一一对应关系；保持关联关系13） 4；16 14）自反；对称；传递；等价15） 1 16）自反性，传递性17）对任一对结点均相互可达；略去G 中边的方向是无向连通18）强连通；单向连通 19）出度；入度20） A(G)中第i 行值为1的元素个数；A(G)中第i 列值为1的元素个数；从υj 到υj 长度为k 的路数21） 2； 对应结点的度数； 孤立点22） 1，-1；全为0 23） 3；1；124）无回路的连通无向；树中度数为1的结点；树中度数大于1的结点25）图G 的生成子图；树枝；图G 中的不在T 中的边26）G 是连通的；m-n+1 27） T 的所有权之和；为G 的所有生成树中权最小者28） 9 29）一条割边；一个环30）T 恰有一个结点的入度为0，其余结点的入度为1；入度为0的结点；出度为0的结点 31）3；932）T 的每个结点的出度小于等于m ；T 的每个结点的出度恰等于m 或零；T 的所有叶子的层次相同33）∑=ti 1wiL(wi)；在所有带权w1,…wt 的二叉树中w(T)最小34）没有一个序列是另一个序列的前辍35） kn/2 36) 4 37) 12、 判断题1）T 2） N 3） N 4） N 5） Y 6） N 7）Y 8） N 9） N 10） Y 11）Y12） N 13） Y 14） N 15）N 16） N 17） N 18）Y 19） N 20）N 21） N22） N 23）N 24） Y3、 简答题1） 不可以.因为任何图的结点数之总和等于边数的2倍，即为偶数，而此序列各数之和为奇数.故不可为任何图的结点度数序列.2） G 有9条边.根据定理：任何图中结点度数总和为边数的2倍.3） 4） 5） 6）G 中至少有9个结点.因为G 中有12条边，根据定理，G 中所有结点的总度数为边数的二倍即24，又已知有6个3度结点，共18度，所以其余各结点度之和为6，且每点可能的度数为0,1,2.若都是2度的尚须3个结点，故G 中至少有9个结点.7） 不一定.因为图G 若能一笔，必存在欧拉回路或欧拉路，要求G 必是连通的.8）不一定.因为树必须是连通的且m=n-1的图，其中n 为结点数，m 为边数.。

图论习题二答案图论习题二答案图论是数学中的一个分支，研究的是图的性质和图之间的关系。

在图论中，有很多经典的习题可以帮助我们更好地理解和应用图的概念。

本文将探讨一些图论习题二的答案，帮助读者更好地理解和掌握图论的知识。

1. 习题：给定一个无向图G=(V,E)，其中V={1,2,3,4,5,6}，E={(1,2),(1,3),(2,3),(2,4),(3,4),(4,5),(4,6)}，求图G的邻接矩阵和关联矩阵。

答案：邻接矩阵是一个n×n的矩阵，其中n是图的顶点数。

对于无向图G，邻接矩阵的元素a[i][j]表示顶点i和顶点j之间是否存在边。

如果存在边，则a[i][j]=1，否则a[i][j]=0。

对于给定的图G，邻接矩阵为：0 1 1 0 0 01 0 1 1 0 01 1 0 1 0 00 1 1 0 1 10 0 0 1 0 00 0 0 1 0 0关联矩阵是一个n×m的矩阵，其中n是图的顶点数，m是图的边数。

对于无向图G，关联矩阵的元素b[i][j]表示顶点i和边j之间的关系。

如果顶点i是边j 的起点，则b[i][j]=-1；如果顶点i是边j的终点，则b[i][j]=1；否则b[i][j]=0。

对于给定的图G，关联矩阵为：-1 -1 0 0 0 01 0 -1 -1 0 00 1 1 0 0 00 0 0 1 -1 -10 0 0 0 1 00 0 0 0 0 12. 习题：给定一个有向图G=(V,E)，其中V={1,2,3,4,5}，E={(1,2),(1,3),(2,3),(2,4),(3,4),(4,1),(5,4)}，求图G的邻接表和深度优先搜索遍历结果。

答案：邻接表是一种图的表示方法，用于存储图中每个顶点的邻接顶点。

对于有向图G，邻接表中的每个元素表示该顶点的出边。

对于给定的图G，邻接表为：1: 2, 32: 3, 43: 44: 15: 4深度优先搜索（DFS）是一种图的遍历算法，用于遍历图中的所有顶点。

NOIP初赛中图论相关的试题1．有6个城市，任何两个城市之间有一条道路连接，6个城市之间两两之间的距离如下表表示，则城市1到城市6的最短距离为____________。

(NOIP 2008)城市1 城市2 城市3 城市4 城市5 城市6城市1 0 2 3 1 12 15城市2 2 0 2 5 3 12城市3 3 2 0 3 6 5城市4 1 5 3 0 7 9城市5 12 3 6 7 0 2城市6 15 12 5 9 2 0【答案】7。

可以用Dijkstra算法求最短路径，1→2→5→6。

2. 平面上有五个点A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。

以这五点作为完全图G 的顶点，每两点之间的直线距离是图G 中对应边的权值。

以下哪条边不是图G 的最小生成树中的边（）。

(NOIP 2005)A. ADB. BDC. CDD. DEE. EA【答案】D。

3. 在下图，从端点（）出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次。

【答案】E。

欧拉回路（一笔画），若图中所有点的度数为偶，则可以设任一点为起点，终点回到该点；若图中有奇点（只能有两个），则以其中一个奇点为起点，终点是另一个奇点。

4. 某大学计算机专业的必修课及期先修课程如下表所示：请判断下列课程安排哪个是不合理的（）A、C0,C6,C7,C1,C2,C3,C4,C5B、C0,C1,C2,C3,C4,C6,C7,C5C、C0,C1,C6,C7,C2,C3,C4,C5D、C0,C1,C6,C7,C5,C2,C3,C4E、C0,C1,C2,C3,C6,C7,C5,C4【答案】D5．已知a, b, c, d, e, f, g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。

能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“a b”开头写出你的安排方案：。

二、应用题题0：（1996年全国数学联赛）有n（n≥6）个人聚会，已知每个人至少认识其中的[n/2]个人，而对任意的[n/2]个人，或者其中有两个人相互认识，或者余下的n-[n/2]个人中有两个人相互认识。

证明这n个人中必有3个人互相认识。

注：[n/2]表示不超过n/2的最大整数。

证明将n个人用n个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G。

由条件可知，G是具有n个顶点的简单图，并且有（1）对每个顶点x，)(xN G≥[n/2]；（2）对V的任一个子集S，只要S＝[n/2]，S中有两个顶点相邻或V-S中有两个顶点相邻。

需要证明G中有三个顶点两两相邻。

反证，若G中不存在三个两两相邻的顶点。

在G中取两个相邻的顶点x1和y1,记N G(x1)＝{y1,y2,……,y t}和N G(y1)={x1,x2,……,x k},则N G(x1)和N G(y1)不相交，并且N G(x1)（N G(y1)）中没有相邻的顶点对。

情况一；n=2r：此时[n/2]＝r，由（1）和上述假设，t=k=r且N G(y1)＝V-N G(x1)，但N G(x1)中没有相邻的顶点对，由（2），N G(y1)中有相邻的顶点对，矛盾。

情况二；n=2r+1: 此时[n /2]＝r ，由于N G (x 1)和N G (y 1)不相交，t ≥r,k ≥r,所以r+1≥t,r+1≥k 。

若t=r+1,则k=r ，即N G (y 1)=r ，N G (x 1)＝V-N G (y 1)，由（2），N G (x 1)或N G (y 1)中有相邻的顶点对，矛盾。

故k ≠r+1，同理t ≠r+1。

所以t=r,k=r 。

记w ∈V- N G (x 1) ∪N G (y 1),由（2），w 分别与N G (x 1)和N G (y 1)中一个顶点相邻，设wx i0∈E, wy j0∈E 。

若x i0y j0∈E ，则w ，x i0, y j0两两相邻，矛盾。

图论试题及答案解析图片一、选择题1. 图论中，图的基本元素是什么？A. 点和线B. 点和面C. 线和面D. 点和边答案：A2. 在无向图中，如果两个顶点之间存在一条边，则称这两个顶点是：A. 相邻的B. 相连的C. 相等的D. 相异的答案：A3. 在有向图中，如果从顶点A到顶点B有一条有向边，则称顶点A是顶点B的：A. 父顶点B. 子顶点C. 邻接顶点D. 非邻接顶点答案：B4. 一个图的度是指：A. 图中顶点的总数B. 图中边的总数C. 一个顶点的边数D. 图的连通性答案：C5. 一个图是连通的，当且仅当：A. 图中任意两个顶点都是相邻的B. 图中任意两个顶点都可以通过边相连C. 图中任意两个顶点都可以通过路径相连D. 图中任意两个顶点都可以通过子顶点相连答案：C二、填空题1. 在图论中，一个顶点的度数是该顶点的________。

答案：边数2. 如果一个图的任意两个顶点都可以通过边相连，则称该图为________。

答案：完全图3. 一个图中，如果存在一个顶点到其他所有顶点都有边相连，则称该顶点为________。

答案：中心顶点4. 图论中，最短路径问题是指在图中找到两个顶点之间的________。

答案：最短路径5. 如果一个图的任意两个顶点都可以通过有向路径相连，则称该图为________。

答案：强连通图三、简答题1. 请简述图论中的欧拉路径和哈密顿路径的定义。

答案：欧拉路径是指在图中经过每条边恰好一次的路径，而哈密顿路径是指在图中经过每个顶点恰好一次的路径。

2. 什么是图的着色问题？答案：图的着色问题是指将图中的顶点用不同的颜色进行标记，使得相邻的两个顶点颜色不同。

四、计算题1. 给定一个无向图G，顶点集为{A, B, C, D, E}，边集为{AB, BC, CD, DE, EA}，请画出该图，并计算其最小生成树的权重。

答案：首先画出图G的示意图，然后使用克鲁斯卡尔算法或普里姆算法计算最小生成树的权重。

1 设图G有12条边，G中有1度结点2个，2度结点2个，4度结点3个，其余结点度数不超过3．求G中至少有多少个结点？2 设有向简单图G的度数序列为(2,2,3,3）, 入度序列为(0,0,2,3),求G得出度序列 .3 设D是n阶有向简单完全图,则图D的边数为 .4设G是n阶无向简单完全图K n，则图G的边数为 .5 仅有一个孤立结点组成的图称为( )(A)零图(B)平凡图(C)补图(D)子图6设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有N k个k度顶点，N k+1个k+1度顶点，则N k = .7设图G如右图.已知路径(1) P1=(v1e5 v5e7 v2e2 v3 )(2) P2=(v5e6 v2e2 v3e3 v4e8 v2e7 v5)(3) P3=(v2e7 v5e6 v2)(4) P4=(v1e1 v2e2 v3e3 v4e8 v2e6 v5)判断路径类型，并求其长度.81）判断下图G1中的路径类型, 并求其长度. P1=(v3e5v4e7v1e4v3e3v2e1v1e4v3)P2=(v3e3v2e2v2e1v1e4v3)P3=(v3e3v2e1v1e4v3).2）判断下图G2中的路径类型, 并求其长度. P1=(v1e1v2e6v5e7v3e2v2e6v5e8v4)P2=(v1e5v5e7v3e2v2e6v5e8v4)P3=(v1e1v2e6v5e7v3e3v4).v1e1e5v2e65e7e4 e2e8v3 4e3v e v1 设图G 有12条边，G 中有1度结点2个，2度结点2个，4度结点3个，其余结点度数不超过3．求G 中至少有多少个结点？ 至少9个2 设有向简单图G 的度数序列为(2,2,3,3）, 入度序列为(0,0,2,3),求G 得出度序列 （2,2,5,6） .3 设D 是n 阶有向简单完全图,则图D 的边数为 )1(−n n .4 设G 是n 阶无向简单完全图K n ，则图G 的边数为 m =n (n -1)/2 .5 仅有一个孤立结点组成的图称为( B ) (A) 零图 (B)平凡图 (C)补图 (D)子图6设n 阶图G 中有m 条边，每个结点的度数不是k 的是k+1，若G 中有N k 个k 度顶点，N k+1个k+1度顶点，则N k = N k =(k+1)n-2m . 7设图G 如右图.已知路径 (1) P 1=(v 1e 5 v 5e 7 v 2e 2 v 3 ) (2) P 2=(v 5e 6 v 2e 2 v 3e 3 v 4e 8 v 2e 7 v 5) (3) P 3=(v 2e 7 v 5e 6 v 2)(4) P 4=(v 1e 1 v 2e 2 v 3e 3 v 4e 8 v 2e 6 v 5)判断路径类型，并求其长度. (1) 初级通路；3 (2) 简单回路；5 (3) 初级回路；2 (4) 简单通路. 5 81）判断下图G1中的路径类型, 并求其长度. P 1=(v 3e 5v 4e 7v 1e 4v 3e 3v 2e 1v 1e 4v 3) P 2=(v 3e 3v 2e 2v 2e 1v 1e 4v 3) P 3=(v 3e 3v 2e 1v 1e 4v 3).2）判断下图G2中的路径类型, 并求其长度. P 1=(v 1e 1v 2e 6v 5e 7v 3e 2v 2e 6v 5e 8v 4) P 2=(v 1e 5v 5e 7v 3e 2v 2e 6v 5e 8v 4) P 3=(v 1e 1v 2e 6v 5e 7v 3e 3v 4).解：在图G 1中，v 3e 5v 4e 7v 1e 4v 3e 3v 2e 1v 1e 4v 3是一条长度为6的回路，但既不是简单回路，也不是初级回路； v 3e 3v 2e 2v 2e 1v 1e 4v 3是一条长度为4的简单回路，但不是初级回路； v 3e 3v 2e 1v 1e 4v 3是一条长度为3的初级回路。