图论及其应用第3章.ppt

《图论及其应用第3章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章图的连通度G3G4G2：删去任意一条边后仍连通，但删去点u后便不连通；u考察：G3和G4删去任意一条边或任意一个点后仍连通，但从直观上看G4的连通程度比G3高。那么如何来衡量一个图的连通程度呢？G1：删去任意一条边后便不连通§3.1割边、割点和块定义1设e是图G的一条边，若ω(G-e)＞ω(G),则称e为G的割边。例(1)若G连通，则割边是指删去后使G不连通的边,故非平凡树的每条边均为割边。(2)图3-2中，边e1和e2为割边，而其余边均不为割边。u1e1.e2u2u3u4图3-2定理1e是图G的割边当且仅当e不在G

2、的任何圈中。证明因定理的结论若在G的含e的连通分支中成立，则必在G中成立，所以我们不妨就假定G连通。必要性设e=uv是图G的割边,若e含在圈C中，令P=C-e。易知P是G-e中一条（u,v）路。任取G-e中两个不同点x和y，因G连通，故G中存在(x,y)路Γ。若Γ不含e，则Γ也是G-e中一条(x,y)路；若Γ含e，用P替换e后也可得到G-e中一条(x,y)路，以上表明G-e连通，这与e是割边矛盾，所以e不在G的任何圈中。充分性设e=uv，若e不是G的割边，则G-e仍连通，从而在G-e中存在(u,v)路P，这样P+e便是G中

3、含e的圈,这与假设“e不在G的任何圈中矛盾”。所以e是G的割边推论设e是连通图G的任意一条边，若e含在G的某圈中，则G-e仍连通。定义2图G=(V,E)的顶点v称为割点，如果E可划分为两个非空子集E1和E2，使得G[E1]和G[E2]恰有一个公共顶点v。u1e1.e2u2u3u4图3-2例图3-2中,点u1,u2,u3和u4是割点,其余点均不为割点。说明：(1)若ω(G-v)＞ω(G),则v必为G的割点；定理2设v是树的顶点，则v是G的割点当且仅当d(v)>1。定理3设v是无环连通图G的一个顶点，则v是G的割点当且仅当V(

4、G-v)可划分为两个非空顶点子集V1与V2，使x∈V1，y∈V2，点v都在每一条(x,y)路上。(2)若G无环且非平凡，则v是G的割点当且仅当ω(G-v)＞ω(G)(3)若无环图G连通，则割点是指删去该点使G不连通的点。证明必要性因v是G的割点，故G-v至少含两个连通分支，设V1是其中一个连通分支的顶点集，V2为其余分支的顶点集。对x∈V1，y∈V2，因在G-v中x与y不连通，而在G中x与y连通（因G连通）所以v在每一条(x,y)路上。充分性取x∈V1，y∈V2，由假设G中所有(x,y)路均含点v，从而在G-v中不存在从x

5、到y的路，这表明G-v不连通，所以v是割点。定义3没有割点的连通图称为块。若图G的子图B是块，且G中没有真包含B的子图也是块，则称B是G的块。例图G如图（a）所示，G的所有块如图（b）所示。(a)(b)由定义3可推知：若e是图G的割边或e是一个环，则G[{e}]是G的块；G的仅含一个点的块或是孤立点,或是环导出的子图；至少两个点的块无环，至少三个点的块无割边。定理4设图G的阶至少为3，则G是块当且仅当G无环并且任意两点都位于同一个圈上。证明充分性此时G显然连通。若G不是块，则G中存在割点v，于是由定理3，V(G-v)可划分

6、为两个非空顶点子集V1与V2，使x∈V1，y∈V2，并且点v在每一条(x,y)路上。这表明x与y不可能位于同一个圈上,这与假设矛盾,所以G是块。必要性G无环是显然的。下证G中任意两点都位于同一个圈上。我们对任意两点u和v的距离d(u,v)用归纳法。当d(u,v)=1时，因G是至少三个点的块，故边uv不是割边。由定理1，边uv位于某一圈中，于是u和v也位于此圈中。设对满足d(u,v)

7、归纳假设知u与w位于同一个圈C中。若v也在C中，则已得到证明。下设v不在C中。因G是块，无割点，故G-w仍连通，于是存在一条(u,v)路Q。设点x是Q与C的最后一个公共点（因u本身就是Q与C的公共点，故这样的x存在）。这样，x将C划分为两条(u,x)路P1和P2，不妨设w在P2上，如下图所示。xuwvCP2P1Q于是P1，Q的x到v段，边wv以及P2的u到w段共同构成一个圈C*且u与v均在C*上。推论设G的阶至少为3，则G是块当且仅当G无孤立点且任意两条边都在同一个圈上。证明设G无孤立点且任意两条边都在同一个圈上。此时G无

8、环且任意两个点也在同一个圈上，由定理4知G是块。定理5点v是图G的割点当且仅当v至少属于G的两个不同的块。反之，设G是块。任取G中两条边e1和e2。在e1和e2的边上各插入一个新的顶点v1和v2，使e1和e2均成为两条边，记这样得到的图为G′。显然G′是阶大于4的块，由定理4，G′中v1和v2位于同一个