图论1-3藏习题解答.doc

《图论1-3藏习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学号：201521020441姓名：张倩习题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的两个图是同构的。5.证明：四个顶点的非同构简单图有11个。证明：设四个顶点中边的个数为m，则有：m=0:m=1：m=2：m=3：m=4：m=5：m=6：因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情

2、况可以看出四个顶点的非同构简单图有11个。11.证明：序列（7,6,5,4,3,3,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）不是图序列。12.证明：若δ≥2，则G包含圈。证明只就连通图证明即可。设V(G)=｛v1,v2,…,vn｝,对于G中的路v1v2…vk,若vk与v1邻接，则构成一个圈。若vi1vi2…vin

3、是一条路，由于d³2，因此，对vin，存在点vik与之邻接，则vik¼vinvik构成一个圈。17.证明：若G不连通，则连通。证明对,若u与v属于G的不同连通分支，显然u与v在中连通；若u与v属于g的同一连通分支，设w为G的另一个连通分支中的一个顶点，则u与w，v与w分别在中连通，因此，u与v在中连通。18.证明：若,则.证明：若为的割边，则，若为的非割边，则，所以，若，则有.习题21.证明：每棵恰有两个1度顶点的树均是路。证明：设树T为任意一个恰有两个1度顶点的树，则T是连通的，且无圈，令V1、V2为度为1的顶点，由于其他的顶点度数均为0或者2，且T中无圈，则从V1到

4、V2有且只有一条连通路。所以，每棵恰有两个1度顶点的树均是路。得证。9.证明：顶点度数为偶数的连通图本身可构成一个包含所有边的回路。证明：证明：由于G是连通非平凡的且每个顶点度数为偶数，所以G中至少存在圈C1,从G中去掉C1中的边，得到G的生成子图G1,若G1没有边，则G的边集合能划分为圈。否则，G1的每个非平凡分支是度数为偶数的连通图，于是又可以抽取一个圈。E(G)反复这样抽取，最终划分为若干圈。设G1是G的边划分中的一个圈。若G仅由此圈组成，则G显然是回路。否则，由于G连通，所以，必然存在圈C2,它和C1有公共顶点。于是，C1∪C2是一条含有C1与C2的边的欧拉回路

5、，如此拼接下去，得到包含G的所有边的一条回路.16.Kruskal算法能否用来求：赋权连通图中的最大权值的树？赋权图中的最小权的最大森林？如果可以，怎样实现？解：（1）不能，Kruskal算法得到的任何生成树一定是最小生成树。（2）可以，步骤如下：步骤一：选择边e1，是的尽可能小；步骤二：若已选定边，则从选取，使为无圈图是满足a的尽可能小的权；步骤三：当步骤二不能继续执行时停止；习题31.证明：是连通图G的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意及,G中的路必含.证明：充分性:是的割边，故至少含有两个连通分支，设是其中一个连通分支的顶点集，是其余分支的顶

6、点集，对，因为中的不连通，而在中与连通，所以在每一条路上，中的必含。必要性：取，由假设中所有路均含有边，从而在中不存在从与到的路，这表明不连通，所以e是割边。3.设G是阶大于2的连通图，证明下列命题等价：(1)G是块(2)G无环且任意一个点和任意一条边都位于同一个圈上；(3)G无环且任意三个不同点都位于同一条路上。(1)→(2)：是块，任取的一点，一边，在边插入一点，使得成为两条边，由此得到新图，显然的是阶数大于3的块，由定理，中的u,v位于同一个圈上，于是中u与边都位于同一个圈上。(2)→(3)：无环，且任意一点和任意一条边都位于同一个圈上，任取的点u，边e，若在上，

7、则三个不同点位于同一个闭路，即位于同一条路，如不在上，由定理，的两点在同一个闭路上，在边插入一个点v，由此得到新图，显然的是阶数大于3的块，则两条边的三个不同点在同一条路上。(3)→(1)：连通，若不是块，则中存在着割点，划分为不同的子集块,,,无环，，点在每一条的路上，则与已知矛盾，是块。7.证明：若v是简单图G的一个割点，则v不是补图的割点。证明：是单图的割点，则有两个连通分支。现任取,如果不在的同一分支中，令是与处于不同分支的点，那么，与在的补图中连通。若在的同一分支中，则它们在的补图中邻接。所以，若是的割点，则不是补图的割点。12