资源描述
习题七1对图7.7中的两个图，各作出两个顶点割。（a）（b）图7.7解： 对图7.7增加加节点标记如下图所示， 则(a)的两个顶点割为： V11=a,b ； V12=c,d (b)的两个顶点割为： V21=u,v ； V12=y 2求图7.7中两个图的和. 解：如上两个图，有 k(G1)=(G1)=2, k(G2)=1, (G2)=2 3试作出一个连通图, 使之满足：解：做连通图G如下，于是有 ： 4求证, 若是边连通的, 则.证明：设G是k边连通的，由定义有(G)k. 又由定理7.1.2知(G) ，因此有 k(G) 即 k ，从而 5求证, 若是阶简单图, 且, 则.分析：由G是简单图，且，可知G中的(G)只能等于 p-1或p-2；如(G)= p-1,则G是一个完全图，根据书中规定，有k(G)=p-1=(G)；如(G)= p-2,则从G中任取V（G）的子集V1，其中|V1|=3，则V(G)-V1的点导出子图是连通的，否则在V1中存在一个顶点v，与其他两个顶点都不连通。则在G中，顶点v最多与G中其他p-3个顶点邻接，所以d(v)p-3，与(G)= p-2矛盾。这说明了在G中，去掉任意p-3个顶点后G还是连通的，按照点连通度的定义有k(G)k-3，又根据定义7.1.1，有k(G)=k-2。证明：因为G是简单图 ,所以d(v)p-1,vV(G),已知(G)p-2（）若(G)= p-1,则G=Kp（完全图），故k(G)=p-1=(G)。（）若(G)= p-2, 则 GKp,设u,v不邻接，但对任意的wV(G),有 uw,vw E(G).于是，对任意的V1V(G), | V1|=p-3 ,G-V1必连通. 因此必有k(G) p-2=(G),但k(G) (G)。 故k(G) =(G)。 6找出一个阶简单图, 使, 但. 解：7设为正则简单图, 求证.分析：G是一个正则简单图，所以(G)=3，根据定理7.1.1有，所以只能等于0，1，2，3这四种情况。下面的证明中分别讨论了这四种情况下的关系。证明：(1)若=0，则G不连通,所以(G)=K(G).(2) 设 K(G)=1,且u 是G中的一个割点，G-u不连通,由于d(u)=3,从而至少存在一个分支仅一边与u相连,显然这边是G的割边,故(G)，所以(G)=K(G) () 设K(G)=2,且v1,v2为G的一个顶点割。G1=G-v1连通,则v2是G1的割点且v2在G1中的度小于等于，类似于(2)知在G1中存在一割边e2(关联v2)使得G1-e2不连通另一方面由于(G)=K(G)=2故G-e2连通由于G1-e2= (G-e2)-v1，故v1是G-e2的割点，且v1在G-e2中的度小于等于，于是类似于(2)知，在G-e2中存在一割边e1，即(G-e2)-e1=G-e1,e2不连通，故(G)=2.所以(G)=K(G). () 设k(G) =3,于是， 有3 =k（G） (G)=3 ,知8证明：一个图是边连通的当且仅当的任意两个顶点由至少两条边不重的通路所连通.分析：这个题的证明关键是理解边连通的定义。证明：（必要性）因为G是边连通的，所以G没有割边。设u，v是G中任意两个顶点，由G的连通性知u，v之间存在一条路径P1，若还存在从u到v的与P1边不重的路径P2，设C=P1P2，则C中含u,v的回路，若从u到v的任意另外路径和P1都有一条（或几条）公共边，也就是存在边e在从u到v的任何路径中，则从G中删除e，G就不连通了，于是e成了G中一割边，矛盾。（充分性）假设G不是一个2-边连通的，则G中有割边，设e=(u,v)为G中一割边，由已知条件可知，u与v处于同一简单回路C中，于是e处在C中，因而从G中删除e后G仍然连通，这与G中无割边矛盾。vV1V2uG9举例说明：若在连通图中, 是一条通路, 则不一定包含一条与内部不相交的通路。 解 如右图G，易知G是2连通的， 若取P为uv1v2v， 则G中不存在Q了。10证明：若中无长度为偶数的回路, 则的每个块或者是, 或者是长度为奇数的回路.分析：块是G的一个连通的极大不可分子图，按照不可分图的定义，有G的每个块应该是没有割点的。因此，如果能证明G的某个块如果既不是，也不是长度为奇数的回路，再由已知条件G中无长度为偶数的回路，则可得出G的这个块肯定存在割点，则可导出矛盾。本题使用反证法。证明： 设K是G的一个块，若k既不是 K2也不是奇回路，则k至少有三个顶点，且存在割边e=uv,于是u,v中必有一个是割点，此与k是块相矛盾。 11证明：不是块的连通图至少有两个块, 其中每个块恰含一个割点.分析：一个图不是块，按照块的定义，这个图肯定含有割点v，对图分块的时候也应该以割点为标准进行，而且分得的块中必定含这个割点，否则所得到的子图一定不是极大不可分子图，从而不会是一个块。证明：由块的定义知，若图G不是块且连通，则G有割点，依次在有割点的地方将G分解成块，一个割点可分成两块，每个块中含G中的一个割点。如下图G。易知 u,v是割点，G可分成四个块K1 K4 。其中每个块恰含一个割点。 12证明：图中块的数目等于 其中, 表示包含的块的数目.分析：一个图G的非割点只能分布在G的一个块中，即=1（当v是G的非割点时），且每个块至少包含一个割点。因此下面就从G的割点入手进行证明。证明中使用了归纳法。证明：先考虑G是连通的情况（），对G中的割点数n用归纳法。由于对G的非割点v，b(v)=1，即b(v)-1 =0，故对n=0时，G的块数为1结论成立。假设G中的割点数nk（k0）时，结论成立。对n=k+1的情况，任取G的一个割点a，可将G分解为连通子图Gi，使得a在Gi中不是割点，a又是Gi的公共点。这样，每一个Gi，有且仅有一个块含有a，若这些Gi共有r个，则b(a)=r，又显然Gi的块也是G的块，且Gi的割点数k。故由归纳法假设Gi的块的块数为1，这里是Gi中含v的块的块数，注意到Gi中异于a的v，b(v)= ，而a在每一个Gi中均为非割点，故。于是Gi的块数为1将所有Gi的块全部加起来，则得到G的块数为：r=r=1+(r-1) =1由归纳法可知，当G连通时，结论成立。当G不连通时，对每个连通分支上述结论显然成立。因此有图中块的数目等于13 给出一个求图的块的好算法。分析：设G是一个具有p个顶点，q条边，w个连通分支的图。求图G的块可先求图G的任一生成森林F，且对每一边eF，求F+e中的唯一回路，设这些回路C1，C2，Cq-p+w都已求得，（这些都有好算法）。在此基础上，我们注意到，两个回路（或一个回路与一个块）若有多于1个公共点，则它们属于同一块。此外，由割边的定义知，G的任一割边不含于任何回路中，且它们都是G的块。基于这些道理，可得如下求图G的块的好算法。解：求图的块的算法：（1）令s=1，t=1，n=q-p+w（2）若n0，输入C1，C2，Cn；否则，转第4步。（3）若且对i=s+t，n-1，令，转第4步；否则，t=t+1，转第5步。（4）若sn，令t=1，转第3步；否则，算法停止（这时C1，C2，Cn与E（G）- C1，C2，Cn中的每一边都是G的块）（5）若s+tn转第3步；否则，s=s+1，转第4步。本算法除了求回路有已知的好算法外，计算量主要在第3步，比较的顶点寻找它们的公共点的运算中，这些运算不超出p2*(q-p+w)次，故是好算法。14证明：是连通的。分析：只要证明不存在少于个顶点的顶点割集。设是一个的任一顶点子集，可分和两种情形证明。证明：(1) 当时，根据定理7.3.1的证明，不是的顶点割集，当然更不是在上加些边的的顶点割集。(2) 当时，设是的顶点割集，属于的不同分支。考察顶点集合和 这里加法取模若或中有一个含的顶点少于个，则在中存在从到的路。与为顶点割集矛盾。若和中都有的个顶点，则：j 若或中，有一个(不妨说)中的个顶点不是相继连成段，则中存在从到的路。与为顶点割集矛盾。k 若与中，的个顶点都是相继连成一段的。若与中至少有一个没有被分成两段，则立即与为顶点割集矛盾；若被分成两段：含的记，含的记，且也被分为两段：含的记，含的记。这样，被分为两段：含的 和含的。这两段都是连通的，且含段的中间点(或最靠近中间的一点)与含段的类似点满足：故与有边相连，在中有路()，与为顶点割集矛盾。综上所述，是连通的。15证明：.分析：根据定理7.3.1，图是m-连通图，因此有 又根据的构造，可知 ，再由定理7.1.1可证。 证明：由定理7.3.1知： 已知：k 16试画出、和分析：根据书上第54页构造的方法可构造出、和。(i) : r = 2 ,p=8,对任意 i,j V(), i- jr 或者则如下图：(ii) 图：r =2,p=8,则在中添加连接顶点i 与 i+p/2(mod p)的边，其中1ip/2,15; 2 6; 3 7; 4 0. 则图如下：(iii) 图: r=2,在图上添加连接顶点0与（p-1）/2和(p+1）/2的边，以及顶点 i 与 i +（p+1）/2(mod p) 的边，其中1 i （p-1）/2.04; 0 5; 1 6; 2 7; 38.则图如下：
展开阅读全文