ImageVerifierCode 换一换
格式:DOCX , 页数:13 ,大小:570.92KB ,
资源ID:14967879      下载积分:5 金币
快捷下载
登录下载
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。 如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝    微信支付   
验证码:   换一换

加入VIP,免费下载
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.bingdoc.com/d-14967879.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录   QQ登录  

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文(图论复习题.docx)为本站会员(b****1)主动上传,冰点文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知冰点文库(发送邮件至service@bingdoc.com或直接QQ联系客服),我们立即给予删除!

图论复习题.docx

1、图论复习题一、选择题1设图G= , v V,则下列结论成立的是(C ).A . deg(v)=2 E B . deg(v)二 EC. deg(v) 2 E PPT 23 D. deg(v) Ev V v V定理1 图G=(V, E)中,所有点的次之和为边数的两倍2.设无向图G的邻接矩阵为0 10 0 10 10 10则G的边数为(B ).A . 6 B. 53、设完全图Kn有n个结点(n 2) , m条边,当(C)时,Kn中存在 欧拉回路.解释:Kn每个结点的度都为n 1所以若存在欧拉回路则n1必为偶数。n必 为奇数。4.欧拉回路是(B )A.路径 B.简单回路PPT 40 C.既是基本回路也

2、是简单回路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.在有 n 个结点的连通图中,其边数( B)A. 最多有 n-1 条 B. 至

3、少有 n-1 条 C. 最多有 n 条 D. 至少有 n9.下列图为树的是(C)。A、G1a,b,c,d,a,a ,a,b ,c,dB、G2a,b,c,d,a,b ,b,d, c,dC、G3a,b,c,d, a,b ,a,d, c,aD、G4a,b,c,d,a,b ,a,c ,d,d10、面的图 7-22 是( C)。A.完全图;B.平面图;C.哈密顿图;D.欧拉图。二、填空题1无向完全图K6有 15 条边。6 X( 6-1 ) /2=152.设连通无向图G有 k个奇顶点,要使G变成欧拉图,在G中至少要加 k/2 条边。解:任何图中的奇点的个数为偶数在每对奇点处多加一条边形成了多重边, G图就

4、成了欧拉图。T连通无向图G有k个奇顶点有k/2对奇顶点.有多少对奇点就加多少条边n(n-1)3、 n阶无向完全图Kn的边数是( 2 ),每个结点的度数是(n-1)证明:/ 1个顶点的图有o条边2个顶点的图有1条边满足1 2( 2 2当3个顶点以上时 假如n=k-1 k=3时/ k-1个顶点的图有(k 1)(k 2) - 3k 1条边2 2 2k个顶点的图有坐9 匚兰条边2 2 22 2* 3k “、 * k、 | 彳( 1) ( ) k 12 2 2 2 k-1个顶点的图与k个顶点的图产生的边数为而又 k-1个顶点的图的边数加上这条边 k-1恰好为k22k(k1)二一个具有N个顶点的无向完全图

5、的边数为n(n -1)2(2n-2 )解:仿用握手定理假设把每个顶点看成一个人A点到B点相当于A主动向B伸手每个点要与n-1个点握手。因为是有向的,所以A向B伸手和B向A伸手有区别总共握手次数是n(n-1) 所以总共边数是n(n-1)01015、设有向图G= , VV1,V2,V3,V4的邻接矩阵A101111001000则V1的入度deg (v1)= 3,V4 的出度 deg(V4) = 136、 一棵无向树的顶点数为n,则其边数为 n-1 ,其结点度数之和是2(n-1)。所有的次之和为边数的两倍7、 一个无向图有生成树的充分必要条件是(此图为连通图)。8设T= 1,则T中至少存在(2 )片

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

7、5-1) 102又V树有5个顶点二树的边数应为4 完全图应删除10-4=6条边可以得到树1 0 00 1 10 0 00 0 10 1 0二、计算题1 .设 G=, V= V1, V2, V3, V4, V5 , E=(V1, V3),(V2, V3), (V2, V4), ( V3, V4),(V3, V5),(V4,V5),试(1)给出G的图形表示; (2) 写出其邻接矩阵;(3)求出每个结点的度数;VI Y2700100叫00110G (gj)5 5 11011解: (1)V4(2) j c0110100110(3)、每个结点的度数分别为V1 1、VP2、VI4、V43、VN22图 G=

8、,其中 V= a, b, c, d, e, E= (a, b), (a, c).(a, e), ( b, d), ( b, e), ( c, e), ( c, d), ( d, e) ,对应边的权值依次为2、1、2、3、6、1、4及5,试(3)求出G权最小的生成树及其权值.四、问答题1、设无向图G= |E|=12。已知有6个3度顶点,其他顶点 的度数均小于3。问G中至少有多少个顶点?解:有6个3度顶点二它们的度数之和为6X 3=18.又T所有点的度数之和为 d(v) 2E 24 ,v V二度数均小于3的其余顶点的度数之和为24-18=6.其余顶点的度数均为2时,G的顶点最少二其余顶点有6/2=

9、3个二G中至少有6+3=9个顶点2、判断下列图是否为欧拉图?说明理由,存在是否哈密尔顿回路解:(1)、是欧拉图。理由:欧拉图判断条件:图中所有节度点均为偶数(2)、不存在哈密尔顿回路。理由:哈密顿图是基本回路(点不能重复)。哈密顿图遍历顶点3、下列各组数中,哪些能构成无向图 的度数列?哪些能构成无向 简单图的度数列?(1)1, 1, 1, 2, 3(2)2, 2, 2, 2, 2(3)3, 3, 3, 3(4)1, 2, 3, 4, 5(5)1, 3, 3, 3解:1、构成图的度数列的条件: 度数(次)之和 d(v) 2E为偶数,并且奇点有偶数个。v VT、(2)、(3)、(5)的度数(次)之

10、和分别为 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)中的度数列不能构成不 是无向简单图。4、1 哥尼斯堡的居民能否通过建一座新桥来找一条可接受的路 线?如果可以,该怎么作?2哥尼斯堡的居民能否通过建两座新桥来找一

11、条可接受的路 线?如果可以,该怎么作?3哥尼斯堡的居民能否通过拆一座桥来找一条可接受的路 线?如果可以,该怎么作? 4 哥尼斯堡的居民能否通过拆两座桥来找一条可接受的路线?如果可以,该怎么作?解:七桥示意图的每个节点度为奇数.它不是欧拉图,不能遍历边连通无向图G有n个奇点成为欧拉图的充要条件:在G中至少要添加或删掉n/2条边假设桥为图中的边,解答如下: (1)、(2)度数均小于3,问图G至少有几个顶点?并画出符合条件的图形?解:T无向图G的|E|=12图G的度数之和为 d(v) 2E 24v V图G至少有6+3=9个顶点。顶点的个数分别是1、3、2、1,求G的边数,试画出满足条件的图形?解:由题可知,7个顶点的度数之和为 1 x 2+3X 3+2X 4+1X 5=24 所有次之和为边数的两倍二G图的边数为24/2=12

copyright@ 2008-2023 冰点文库 网站版权所有

经营许可证编号:鄂ICP备19020893号-2