图论复习题(20210415210650)

1、图论复习题(二)图论复习题、选择题1设图G= , v V,则下列结论成立的是 (C ).A. deg(v)=2 EB. deg(v)二 EC. deg(v) 2E PPT 23D . deg(v) Ev Vv V定理1 图G= (V, E)中，所有点的次之和为边数的两倍2. 设无向图G的邻接矩阵为0 11 01 01000 10 0 10 10 10则G的边数为(B ).A .6B .53、设完全图Kn有n个结点(n 2), m条边，当(C)时，心中存 在欧拉回路.A. m为奇数 B . n为偶数C. n为奇数 D . m为偶数n 1必为偶数解释：Kn每个结点的度都为n- 1所以若存在欧拉回路

2、则必为奇数。4. 欧拉回路是(B )A.路径 B.简单回路PPT 40 C.既是基本回路也是简单回路D.既非基本回路也非简单回路 5 .哈密尔顿回路是(C )A.路径 B.简单回路 C.既是基本回路也是简单回路D.既非基本回路也非简单回路PPT 40:哈密尔顿回路要求走遍所有的点，即是基本回路的点不重复，也可以是简单回路的边不重复。6. 设G是简单有向图，可达矩阵P（G）刻划下列关系中的是（C ）A、点与边 B、边与点C、点与点 D、边与边7. 下列哪一种图不一定是树（C）。A.无简单回路的连通图B. 有n个顶点n-1条边的连通图C.每对顶点间都有通路的图D.连通但删去一条边便不连通的图8在有

3、n个结点的连通图中，其边数（B）A.最多有n-1条 B.至少有n-1条 C.最多有n条 D.至少有n 条9.下列图为树的是(C)。AG1a,b,c,d, a,a ,a,bc,dB、G2a,b,c,d, a, b ,b,d,c,dCG3a,b,c,d, a,b ,a,d,c, aDG4a,b,c,d, a, b ,a,cd,d10、下面的图7-22是（C)0A.完全图；B.平面图；C.哈密顿图；D.欧拉图。二、填空题1. 无向完全图K6有15条边。6 X（ 6-1 ） /2=152. 设连通无向图Gt k个奇顶点，要使G变成欧拉图，在G中至少要加 k/2条边 解：任何图中的奇点的个数为偶数在每对

4、奇点处多加一条边形成了多重边，G图就成了欧拉图连通无向图有k个奇顶点 有k/2对奇顶点 .有多少对奇点就加多少条边n(n-1)3、n阶无向完全图Kn的边数是(2 )，每个结点的度数是(n-1)证明：V 1个顶点的图有0条边2个顶点的图有1条边2 (2 1)满12当3个顶点以上时假如n=k-1 k=3时2v k-1个顶点的图有U严占 1条边2k个顶点的图有咛牛与条边 k-1个顶点的图与k个顶点的图产生的边数为22丄3k1)(-k)k 12222而又v k-1个顶点的图的边数加上这条边k-1恰好为3k21) (k 1)k(k 1)2当n=k时满足条件一个具有N个顶点的无向完全图的边数为 n(n-1

5、)丿24、n个结点的有向完全图边数是(n(n-1),每个结点的度数是(2n-2 )。解：仿用握手定理假设把每个顶点看成一个人A点到B点相当于A主动向B伸手每个点要与n-1个点握手因为是有向的，所以A向B伸手和B向A伸手有区别 总共握手次数是n(n-1)所以总共边数是n(n-1)0 10 15、设有向图G= , V V!，V2，V3，V4的邻接矩阵A10 11110 010 0 0 则V1的入度deg （V1） = 3, V4的出度deg他）=1,6、 一棵无向树的顶点数为n,则其边数为n-1，其结点度数之和 是2（n-1）。所有的次之和为边数的两倍7、一个无向图有生成树的充分必要条件是 （此图

6、为连通图）。8设T= 1，则T中至少存在（2 ）片树叶。9、 任何连通无向图G至少有（1 ）棵生成树，当且仅当G是（树）, G的生成树只有一棵。10、设T是一棵树，则T是一个连通且（无圈）的图。11、 设无向图G有18条边且每个顶点的度数都是 3,则图G有（12 ） 个顶点。解：t 18条边的次之和为d（v） 2 E 36，v V且每个顶点的度数都是3顶点数为36/3=12。如图：12、任一有向图中，度数为奇数的结点有（偶数）个。PPT 2313、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度顶点为（9）。如图：1114、设G是由5个顶点组成的完全图，则从G中删去(6)条边可以得到

7、树。解：/ 5个顶点组成的完全图边数为5 (5-1) 102又T树有5个顶点二树的边数应为4二完全图应删除10-4=6条边可以得到树。15、已知图G是相邻矩阵为 则G勺边数为(B )。A.5;B.4 ;C.600100000111000001001疋01010VIJV3二、计算题1.设 G=, V= V1, V2, V3, V4, V5, E=（V1,V3）,（V2,V3）,(V2,V4), (V3,V4), (V3,V5), (V4,V5)，试(1)给出G的图形表示；写出其邻接矩阵;求出每个结点的度数;解:0 0 10 00 0 110 G(gj)55(3)、每个结点的度数分别为V1 1、V

8、22、V3 4、V4 3、V5 22.图 G=，其中 V= a, b, c, d, e, E= (a, b), (a, c), (a, e), (b2、 1、 2、 3、 6、d), (b, e), (c, e), (c, d), (d, e) ，对应边的权值依次为1、4及5,试(1)画出G的图形;(2)写出G的邻接矩阵;(3)求出G权最小的生成树及其权值.解:G (gij )5 52+1+1+3=8。四、问答题1、设无向图G= |E|=12。已知有6个3度顶点，其他顶点 的度数均小于3。问G中至少有多少个顶点？解：有6个3度顶点二它们的度数之和为6X 3=18.又t所有点的度数之和为d(v)

9、 2 E 24 ,v V二度数均小于3的其余顶点的度数之和为24-18=6.其余顶点的度数均为2时，G的顶点最少二其余顶点有6/2=3个二G中至少有6+3=9个顶点2、判断下列图是否为欧拉图？说明理由，存在是否哈密尔顿回路。解：(1) 、是欧拉图。理由：欧拉图判断条件：图中所有节度点均为偶数(2) 、不存在哈密尔顿回路。理由：哈密顿图是基本回路(点不能重复)。哈密顿图遍历顶点。3、下列各组数中，哪些能构成无向图 的度数列？哪些能构成无向 简单图的度数列？(2) 2, 2, 2, 2, 2V(3) 3, 3, 3, 3(4 )1 , 2 , 3 ,VV,5(3)(5)(5) 1, 3, 3, 3

10、“解：1、构成图的度数列的条件：度数(次)之和 d(v) 2E为偶数，并且奇点有偶数个。v VT、(2)、(3)、(5)的度数(次)之和分别为 8、10、12、15、10又T奇点的个数分别为4、0、4、3、4(4)不符合。也不满足无向简单图。 (1),，(3), 都能构成无向图的度数列2、(5)虽然能构成无向图的度数列，但不能构成无向简单图的度数列。若G是无向简单图，设 G中顶点为 a b、c、d且d(a)=1、d(b)=d(c)=d(d)=3 显然，a只能与b、c、d其中一个顶点相邻，若设a与b相邻，则除b可以是3 度顶点，c、d都不能是3度顶点，这是矛盾的。所以(5)中的度数列不能构成不

11、是无向简单图。4、1哥尼斯堡的居民能否通过建一座新桥来找一条可接受的路线？如果可以，该怎么作？2哥尼斯堡的居民能否通过建两座新桥来找一条可接受的路线？如果可以，该怎么作？103哥尼斯堡的居民能否通过拆一座桥来找一条可接受的路线？如果可以，该怎么作?4哥尼斯堡的居民能否通过拆两座桥来找一条可接受的路线?如果可以，该怎么作?解：七桥示意图的每个节点度为奇数它不是欧拉图，不能遍历边连通无向图G有n个奇点成为欧拉图的充要条件:在G中至少要添加或删掉n/2条边 假设桥为图中的边，解答如下：(1)、(2).图中有4个奇点要使其变为欧拉回路，即可以在( 1)不满足条件，路线不被接受，7(2)(3)、(4).

12、图中有4个奇点要使其变为欧拉回路，即可以在( 3)不满足条件，路线不被接受,五.画图画出一个无向欧拉图，使它具有:(1)偶数个顶点，偶数条边;(2)(3)奇数个顶点，奇数条边;偶数个顶点，奇数条边;(4)奇数个顶点，偶数条边12 *rr画出一个有向欧拉图，要求:期序走,黙为起点(4)(4339G中添加4/2=2条边(2)的建议则被接受9/7G中删掉4/2=2条边的建议则被接受按数字顺序走遍所有的边，点可以重复 蓝点是起点。(1)偶数个顶点，偶数条边；(2)奇数个顶点，奇数条边;(3) 偶数个顶点，奇数条边；(4) 奇数个顶点，偶数条边。3.根据如下的相邻矩阵，画出它所对应的图 GA(G)0 10 1110 1110 10 111110 1111101110 11110104、已知无向图G有12条边，6个3度顶点，其余顶点的 度数均小于3,问图G至少有几个顶点？并画出符合 条件的图形？解：T无向图G的|E|=12图G的度数之和为 d(v) 2E 24v V又T 6个3度顶点这6个3度顶点的度数之和为6X 3=1