电子科技大学 图论 第二次作业d 杨春

《电子科技大学 图论 第二次作业d 杨春》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、郁成201221260232通信抗干扰第四章4.34.4证明:作映射f:↔(i=1,2….10)容易证明，对"ÎE((a)),有f()=ÎE((b))(1£i£10,1£j£10)由图的同构定义知，图(a)与(b)是同构的。4.10证明：设W=v1v2…..vk-1vk是G中的一条最长路。由于δ≥2，所以vk必然有相异于vk-1的邻接顶点。又W是G中最长路,所以，这样的邻接点必然是v1,v2,….,vk-2中之一。设该点为vm，则vmvm+1….vkvm为G中圈。4.11证明：如果u,v属于G的同一分支，设w是与u,v处于不同分支中的点，则在

2、G的补图中，u与w,v与w分别邻接，于是，u与v在G的补图中是连通的。如果u与v在G的两个不同分支中，则在G的补图中必然邻接，因此，也连通。4.12证明：由于删掉了G中的一条边，连通性可能被破坏，因此w(G)≤w(G-e)必然成立。连接一条边的有两个顶点，若该边为割边，则w(G-e)=w(G)+1，若不是割边，则连通性没被破坏w(G-e)=w(G)。4.15解：对（1）（2）均可用Kruskal算法，具体对（1）：a．将Kruskal算法中的“小”字换成“大”字b.重新规定图的权为这样就可以直接使用Kruskal算法。对（2）：只需对G的每一

3、分支试行Kruskal算法即可。5.1证明：若不然，其中有一个不是一度或是两个均不是一度顶点，那顶点处必然存在邻接点，使得这条路不会不存在圈，那这条路必然不是最长路，与条件矛盾。5.2证明：从任何点出发，因为所有点的度数均为偶数，将它们两两划分为一组，沿着一条边进入该点，就必然存在着另一条不同的边离开该点，因此顶点度数为偶数的连通图本身可构成一个包含所有边的闭迹。5.7解：对（1）（2）均可用Kruskal算法，具体对（1）：a．将Kruskal算法中的“小”字换成“大”字b.重新规定图的权为这样就可以直接使用Kruskal算法。对（2）：只

4、需对G的每一分支试行Kruskal算法即可。5.8证明：必要性：因e是G的隔边，故G-e至少含有两个连通分支，设V1为其中一个分支的顶点集，V2是其余分支的顶点集。对因在G-e中u与v不连通，而在G中u与v连通（因G连通），故e在每一条（u，v）路上。充分性：取，假设G中所有（u，v）路均含有边e，从而在G-e中不存在从u到v的路，这表明G-e不连通，故e为割边。5.10证明：若G为块，则G无环显然成立。由定理4可知，G为块当且仅当G无环且任意两点都位于同一圈上，可得G中任意一点及其任意一边均位于同一圈上，及由（1）可得（2）。在G的任意一条

5、边上任取两点，然后在边外再任取一点，由（2）可知，这任意3点必均位于同一圈上，又G为块，故这任意的3点位于同一路上。然后用反证法可以得到（3）5.19证明：设G连通，若v是简单图G的割点，则G-v至少两个连通分支，即G-v不连通。由定理7知连通，又,故连通，所以v不是补图的割点。5.12证明：若不然，其中有一个不是一度或是两个均不是一度顶点，那顶点处必然存在邻接点，使得这条路不会不存在圈，那这条路必然不是最长路，与条件矛盾。5.1解：由图可知G1连通度为2（1,3），边连通度为2（14,34）；G2连通度为3（2,6,5），边连通度为3（12

6、,16,15）。