《图论及其应用3章习题答案.docx》由会员分享，可在线阅读，更多相关《图论及其应用3章习题答案.docx（6页珍藏版）》请在三一文库上搜索。
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)证实：假设62,那么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 1 ,
4、所以 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中必然含有一组极小割边,这与T中不含极小割边相矛盾, 那么T中不含G的极小边割.(2)假设e为T中的一条边,根据(1)得T+e中仍不含G的极小割边,这与T e包含G的唯一的极小边割相矛盾,那么 e为G的不在T中的边,得证.