图论第一次作业_第1页
图论第一次作业_第2页
图论第一次作业_第3页
图论第一次作业_第4页
免费预览已结束,剩余1页可下载查看

下载本文档

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

文档简介

1、.习题一:l 4. 证明下面两图同构。证明:作映射f : vi ui (i=1,2.10) 容易证明,对vi v j E (a),有f (v i vj,),=,ui,uj,E,(b) (1 i 10, 1j 10 ) 由图的同构定义知,图(a)与(b)是同构的。l 5.证明:四个顶点的非同构简单图有11个。证明:设四个顶点中边的个数为m,则有:m=0:m=1 :m=2:m=3:m=4:m=5:m=6:因为四个顶点的简单图最多就是具有6条边,上面所列出的情形是在不同边的条件下的不同构的情形,则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。l 11.证明:序列(7,6,5,4,3,3,

2、2)和(6,6,5,4,3,3,1)不是图序列。证明:由于7个顶点的简单图的最大度不会超过6,因此序列(7,6,5,4,3,3,2)不是图序列;(6,6,5,4,3,3,1)是图序列非负整数组是图序列的充要条件是:是图序列(5,4,3,2,2,0)是图序列,然而(5,4,3,2,2,0)不是图序列,所以(6,6,5,4,3,3,1)不是图序列。l 12.证明:若2,则G包含圈。证明:下面仅对连通图的下的条件下进行证明,不连通的情形可以通过分成若干个连通的情形来证明。设VG=V1,V2,V3,Vn,对于G中的路V1,V2,V3,Vn若Vk与V1邻接,则构成一个圈。若Vi1,Vi2,Vi3,Vin

3、是一条路,由于2,因此,对于Vin,存在Vik与之邻接,则Vik,,VinVik构成一个圈。l 17.证明:若G不连通,则G连通。证明:对于任意的u,v(G),若u与v属于G的不同连通分支,显然u与v在G中连通;若u与v属于g的同一连通分支,设w为G的另一个连通分支中的一个顶点,则u与w,v与w分别在G中连通,因此,u与v在G中连通。l 18.证明:若eE(G),则wGwG-ewG+1.证明:若e为G的割边,则wG-e= wG+1,若e为G的非割边,则wG-e=wG,所以,若eE(G),则有wGwG-ewG+1.习题二:1.证明:非平凡树的最长路的起点和终点均是1度的。证明设P=v1v2vk是

4、非平凡树T中一条最长路,若d(v1)2则v1与vk在T中的邻接点只能有一个,否则,若v1与除了P中顶点之外的其他顶点相连,则P可以继续延长,这与P是最长路是相矛盾的。若v1与P上的某顶点相连,则就构成了圈,这与数相矛盾,推出P不是最长路。即说明v1与vk是树叶,则v1与vk均是一度的。所以非平凡树的最长路的起点和终点均是1度的。9.证明:顶点度数为偶数的连通图本身可构成一个包含所有边的闭迹。证明:证明:由于G是连通非平凡的且每个顶点度数为偶数,所以G中至少存在圈C1,从G中去掉C1中的边,得到G的生成子图G1,若G1没有边,则G的边集合能划分为圈。否则,G1的每个非平凡分支是度数为偶数的连通图

5、,于是又可以抽取一个圈。反复这样抽取,E(G)最终划分为若干圈。设C1是G的边划分中的一个圈。若G仅由此圈组成,则G显然是闭迹。否则,由于G连通,所以,必然存在圈C2,它和C1有公共顶点。于是,C1C2是一条含有C1与C2的边的欧拉闭迹,如此拼接下去,得到包含G的所有边的一条闭迹.16.Kruskal算法能否用来求:(1)赋权连通图中的最大权的树?(2)赋权图中的最小权的最大森林?如果可以,怎样实现?答:1、不能,由Kruskal算法得到的任何生成树一定是最小生成树。2、能a.选择边e1使其权值最小 b.若已经选定边e1 e2 e3 ek,则从E-e1,e2,e3ek,选择边ek+1 cGe1

6、,e2,e3ek为无圈图,且可以不连通 dek+1的权值w(eK+1)尽可能小 e当a、b、c不能进行时,停止。习题三:1.证明:e是连通图G的割边当且仅当V(G)可划分为两个子集V1和V2,使对任意uV1及vV2, G中的路(u,v)必含e.证明:必要性: e是G的割边,故G-e至少含有两个连通分支,设V1是其中一个连通分支的顶点集,V2是其余分支的顶点集,对,因为G-e中的u,v不连通,而在G中u与v连通,所以e在每一条(u,v)路上,G中的(u,v)必含e。充分性:取,由假设G中所有(u,v)路均含有边e,从而在G-e中不存在从u与到v的路,这表明G-e不连通,所以e是割边。3.设G是阶

7、大于2的连通图,证明下列命题等价:(1) G是块(2) G无环且任意一个点和任意一条边都位于同一个圈上;(3) G无环且任意三个不同点都位于同一条路上。(1)(2): G是块,任取G的一点u,一边e,在e边插入一点v,使得e成为两条边,由此得到新图G1,显然G1的是阶数大于2的块,由定理4,G1中的u,v位于同一个圈上,于是G中u与边e都位于同一个圈上。 (2)(3):G无环,且任意一点和任意一条边都位于同一个圈上,任取G的点u,边e,若u不在e上,则三个不同点位于同一个圈,即位于同一条路,如u在e上,由定理e的两点在同一个圈上,在e边插入一个点v,使得e成为2条边,由此得到新图G1,显然G1

8、的是阶数大于2的块,则两条边的三个不同点在同一条路上。 (3)(1):G连通,若G不是块,则G中存在着割点u,划分为不同的子集块V1, V2, V1, V2无环,点u在每一条(x,y)的路上,由于x,y的任意性,则三个不同点不能位于同一条路上,则与已知矛盾,G是块。7.证明:若v是简单图G的一个割点,则v不是补图G的割点。证明:v是单图G的割点,则G-v至少两个连通分支。现任取x,yV(G-v), 如果x,y在G-v的同一分支中,令u是与x,y处于不同分支的点,那么,通过u,可说明,x,与y在G-v的补图中连通。若x,y在G-v的不同分支中,则它们在G-v的补图中邻接。所以,若v是G的割点,则v不是其补图的割点。12.对图320给出的图G1和G2,求其连通度和边连通度,给出相应的最小点割和最小边割。解: 最小点割 6,8 最小

温馨提示

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

评论

0/150

提交评论