《图论及其应用答案电子科大》由会员分享，可在线阅读，更多相关《图论及其应用答案电子科大（2页珍藏版）》请在装配图网上搜索。
1、习题三：证明：e是连通图G的割边当且仅当V(G)可划分为两个子集V1和V2,使对任意u CW及v V2, G中的路(u, v)必含e.证明：充分性：e是G的割边，故G- e至少含有两个连通分支，设M是其中一个连通分支的顶点集，%是其余分支的顶点集，对 u V1, v V2 ,因为G中的u,v不连通，而在G中u与v连通，所以e在每一条(u, v)路上，G中的(u,v)必含e。必要性：取u Vi,v V2,由假设G中所有(u, v)路均含有边e,从而在G- e中不存在从u与到v的路，这表明G不连通，所以e是割边。3.设G是阶大于2的连通图，证明下列命题等价：( 1) G是块( 2) G无环且任意一
2、个点和任意一条边都位于同一个圈上；( 3) G无环且任意三个不同点都位于同一条路上。(1) - (2):G是块，任取G的一点u, 一边e,在e边插入一点v,使得e成为两条边，由此得到新图 G1,显然G的是阶数大于3的块，由定理，G中白u,v位于同一个圈上，于是G中u 与边e都位于同一个圈上。(2) - (3):G无环，且任意一点和任意一条边都位于同一个圈上， 任取G勺点u,边e,若u在e上， 则三个不同点位于同一个闭路，即位于同一条路，如 u不在e上，由定理，e的两点在 同一个闭路上，在e边插入一个点v,由此得到新图Gi,显然Gi的是阶数大于3的块， 则两条边的三个不同点在同一条路上。(3)
3、- (1):G连通，若G不是块，则G中存在着割点u,划分为不同的子集块 Vi, V V1, %无环，x w,y v2,点u在每一条(x, y)的路上，则与已知矛盾，G是块。7.证明：若v是简单图G的一个割点，则v不是补图G的 割点。证明：v是单图G的割点，则G- v有两个连通分支。现任取x,y V(G - v),如果x,y不 在G- v的同一分支中，令u是与x,y处于不同分支的点，那么，x,(fy在G- v的补图中 连通。若x,y在G- v的同一分支中，则它们在 G- v的补图中邻接。所以，若v是G的 割点，则v不是补图的割点。12 .对图320给出的图G1和G2求其连通度和边连 通度，给出相应的最小点割和最小边割。解：G12 最小点割 6,8(G1) 2 最小边割 (6,5) ， (8,5) G25最小点割6,7,8,9,10(G2) 5最小边割 (2,7) (1,6) 13 .设H是连通图G的子图，举例说明：有可能 k(H)k(G).解：通常常H) ?(?)
图论及其应用答案电子科大
