图论及其应用3章习题答案_第1页
图论及其应用3章习题答案_第2页
图论及其应用3章习题答案_第3页
图论及其应用3章习题答案_第4页
图论及其应用3章习题答案_第5页
免费预览已结束,剩余1页可下载查看

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、1.(题14):证实图1-28中的两图是同构的图 1-28证实 将图1-28的两图顶点标号为如下的(a)与(b)图V2V4V3VV9作映射f : f(v容易证实,对10 )i)Vi VjUi (1 i10)E(a),有 f(VM)Ui UjE(b)(1i 10, 1 j由图的同构定义知,图1-27的两个图是同构的.2.(题6)设G是具有m条边的n阶简单图.证实:n当且仅当G是2n-1d(v)n(n-1)2m n(n-1)完全图.证实 必要性 假设G为非完全图,那么 v V(G),有d(v)n(n-1)/2=;,与矛盾!m=充分性 假设G为完全图,那么2m= d(v) =n(n-1)3.(题9)

2、证实:假设k正那么偶图具有二分类V= ViUV2,Vi| = | w.证实由于G为k正那么偶图,所以,k Vi=m= k V2ViV24.(题12)证实:假设6>2,那么G包含圈证实 只就连通图证实即可.设 V(G)= Vl,V2,Vn,对于G中的路V1V2 Vk,假设Vk与V1邻接,那么构成一个圈.假设VilVi2-Win是一条路,由于 2,因此, 对Vin ,存在点Vik与之邻接,那么Vik Vin Vik构成一个圈.5.(题17)证实:假设G不连通,那么G连通.证实 对u,V V(G),假设u与V属于G的不同连通分支,显然u与V在G中 连通;假设u与v属于g的同一连通分支,设w为G

3、的另一个连通分支中的一个顶点,那么u与w, V与w分别在G中连通,因此,u与V在G中连通.习题二2、证实:每棵恰有两个 1度顶点的树均是路.证实:设树T为任意一个恰有两个 1度顶点的树,那么 T是连通的,且无圈,令 V1、V2为度为1的顶点,由于其他的顶点度数均为0或者2,且T中无圈,那么从 M到V2有且只有一条连通路.所以,每棵恰有两个1度顶点的树均是路.得证.n5、证实:正整数序列(d1,d2,.,dn)是一棵树的度序列当且仅当di 2(n 1).i 1 n证实:设正整数序列(d1,d2,.,dn)是一棵树T的度序列,那么满足di 2E , E为T的i 1n边数,又有边数和顶点的关系n E

4、 1 ,所以 di 2(n 1)i 114、证实:假设e是Kn的边,那么(Kn e) (n 2)nn3.假设e为Kn的一条边,由Kn中的边的对称性以及每棵生成树的边数为n-1 , Kn的所有生成树的总边数为:(n 1)nn 2,所以,每条边所对应的生成树的棵数为:(n 1)n2nn3,1 n(n 1)2所以,K n - e 对应的生成树的棵数为: n 2 n 3n 3(Kn e) n 2n (n 2)n16、Kruskal算法能否用来求:(1)赋权连通图中的最大权值的树(2)赋权图中的最小权的最大森林如果可以,怎样实现解:(1)不能,Kruskal算法得到的任何生成树一定是最小生成树.(2)可

5、以,步骤如下:步骤一:选择边el,是的(e1)尽可能小;步骤二:假设已选定边 e,e2,e,那么从E e,e2,ej选取e 1 ,使a Ge,e2,e为无圈图b、(e J是满足a的尽可能小的权;步骤三:当步骤二不能继续执行时停止;习题三3.设G是阶大于2的连通图,证实以下命题等价:(1) G是块(2) G无环且任意一个点和任意一条边都位于同一个圈上;(3) G无环且任意三个不同点都位于同一条路上.证实:(1) 一( 2):G是块,任取G的一点u, 一边e,在e边插入一点v,使得e成为两条边,由此得到新图Gl,显然Gl的是阶数大于3的块,由定理,G中的u,v位于同一个圈上,于是Gl中 u与边e都

6、位于同一个圈上.(2) 一 (3):无环,且任意一点和任意一条边都位于同一个圈上,任取的点u,边e,假设在上,那么三个不同点位于同一个闭路,即位于同一条路,如不在上,由定理,的两点在同一个闭路上,在边插入一个点 v,由此得到新图,显然的是阶数大于3的块,那么两条边的三个不同点在同一条路上.(3) 一 (1):连通,假设不是块,那么中存在着割点,划分为不同的子集块 ,无环,x Vi,y V2,点在每一条的路上,那么与矛盾,是块.13、设H是连通图G的子图,举例说明:有可能 k(H)> k(G).解:通常.整个图为,割点左边的图为的的子图,那么.15、设T嘉简单连通图G的生成树,T G E(T)称为G的余树,图G的极小边割是指其 II八 任何真子集均不是边割的边割.证实:(1) T不含G的极小边割.(2) T e包含G的唯一的极小边割,其中 e为G的不在T中的边.证实:(1)设T含有G的极小边割S,那么T中不含极小边割 S,由于T是简单连通图 G的生成树,那么T中必然含有一组极小

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论