图论及其应用1-3章习题答案(电子科大) (1)

《图论及其应用1-3章习题答案(电子科大) (1)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学号：201321010808姓名：马涛习题14．证明图1-28中的两图是同构的证明将图1-28的两图顶点标号为如下的(a)与(b)图作映射f:f(vi)®ui(1£i£10)容易证明，对"vivjÎE((a)),有f(vivj)=uiujÎE((b))(1£i£10,1£j£10)由图的同构定义知，图1-27的两个图是同构的。6．设G是具有m条边的n阶简单图。证明：m=当且仅当G是完全图。证明必要性若G为非完全图，则$vÎV(G),有d(v)

2、！充分性若G为完全图，则2m=åd(v)=n(n-1)Þm=。9.证明：若k正则偶图具有二分类V=V1∪V2，则

3、V1

4、=

5、V2

6、。证明由于G为k正则偶图，所以，k

7、V1

8、=m=k

9、V2

10、Þ½V1½=½V2½。12.证明：若δ≥2，则G包含圈。证明只就连通图证明即可。设V(G)=｛v1,v2,…,vn｝,对于G中的路v1v2…vk,若vk与v1邻接，则构成一个圈。若vi1vi2…vin是一条路，由于d³2，因此，对vin，存在点vik与之邻接，则vik¼vinvik构成一个圈。17.证明：若G不连通，则连通。证明对,若u与v属于G的

11、不同连通分支，显然u与v在中连通；若u与v属于g的同一连通分支，设w为G的另一个连通分支中的一个顶点，则u与w，v与w分别在中连通，因此，u与v在中连通。习题2证明：每棵恰有两个1度顶点的树均是路。证明：设树T为任意一个恰有两个1度顶点的树，则T是连通的，且无圈，令V1、V2为度为1的顶点，由于其他的顶点度数均为0或者2，且T中无圈，则从V1到V2有且只有一条连通路。所以，每棵恰有两个1度顶点的树均是路。得证。证明：正整数序列是一棵树的度序列当且仅当。证明：设正整数序列是一棵树T的度序列，则满足，E为T的边数，又有边数和顶点的关系，

12、所以证明：若e是的边，则。若e为Kn的一条边，由Kn中的边的对称性以及每棵生成树的边数为n-1，Kn的所有生成树的总边数为：，所以，每条边所对应的生成树的棵数为：，所以，Kn-e对应的生成树的棵数为：Kruskal算法能否用来求：赋权连通图中的最大权值的树？赋权图中的最小权的最大森林？如果可以，怎样实现？解：（1）不能，Kruskal算法得到的任何生成树一定是最小生成树。（2）可以，步骤如下：步骤一：选择边e1，是的尽可能小；步骤二：若已选定边，则从选取，使为无圈图是满足a的尽可能小的权；步骤三：当步骤二不能继续执行时停止；习题33

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

14、此得到新图，显然的是阶数大于3的块，则两条边的三个不同点在同一条路上。(3)→(1):连通，若不是块，则中存在着割点，划分为不同的子集块,,,无环，，点在每一条的路上，则与已知矛盾，是块。设H是连通图G的子图，举例说明：有可能k(H)>k(G).解：通常.eH整个图为，割点左边的图为的的子图，，则.设T是简单连通图G的生成树，称为G的余树，图G的极小边割是指其任何真子集均不是边割的边割。证明：不含G的极小边割。包含G的唯一的极小边割，其中e为G的不在中的边。证明：（1）设含有G的极小边割S，则T中不含极小边割S，由于T是简单连通图G

15、的生成树，则T中必然含有一组极小割边，这与T中不含极小割边相矛盾，则中不含G的极小边割。（2）假设e为中的一条边，根据（1）得+e中仍不含G的极小割边，这与包含G的唯一的极小边割相矛盾，则e为G的不在中的边，得证。