连通度).ppt

§3.1 割边、割点和块 定理1 e是图G的割边当且仅当e不在G的任何圈中。 推论 设e是连通图G的任意一条边，若e含在G的某圈中，则G-e仍连通。 例 图G如图（a）所示，G的所有块如图（b）所示。 定理4 设图G的阶至少为3，则G是块当且仅当G无环并且任意两点都位于同一个圈上。 推论 设G的阶至少为3，则G是块当且仅当G无孤立点且任意两条边都在同一个圈上。 §3.2 连通度 定理7 设G是具有 m条边的n阶连通图，则 κ≤ * * 电子科技大学应用数学学院 张先迪 第三章 图的连通度 G3 G4 G2 ：删去任意一条边后仍连通，但删去点u后便不连通； u 考察： G3和G4删去任意一条边或任意一个点后仍连通，但从直观上看G4的连通 程度比G3高。那么如何来衡量一个图的连通程度呢？本节将讨论这个问题。 G1：删去任意一条边后便不连通 定义1 设e是图G的一条边，若ω(G-e)＞ω(G), 则称e为G的割边。 例 (1) 若G连通，则割边是指删去后使G不连通的边,故非平凡树的每条边均为割边。 (2) 图3-2中，边e1和e2为割边，而其余边均不为割边。 u1 e1 . e2 u2 u3 u4 图3-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中含e的圈,这与假设“e不在G的任何圈中矛盾”。所以e是G的割边 定义2 图G = (V, E) 的顶点v 称为割点，如果 E 可划分为两个非空子集 E1 和 E2，使得G[E1] 和 G[E2] 恰有一个公共顶点v。 u1 e1 . e2 u2 u3 u4 图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(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到y的路，这表明G-v不连通，所以v是割点。 定义3 没有割点的连通图称为块。若图G的子图B是块，且G中没有真包含B的子图也是块，则称B是G的块。 (a) (b) 由定义3可推知：若e是图G的割边或e是一个环，则G[{e}]是G的块；G的仅含一个点的块或是孤立点,或是环导出的子图；至少两个点的块无环，至少三个点的块无割边。 证明 充分性 此时G显然连通。若G不是