文档介绍：第二章图的连通性
连通图:任二顶点间有路相连。
例

可见在连通图中,连通的程度也是有高有低。
本章的目的就是定义一种参数来度量连通图连通程度的高低。
§ 割边、割点与连通度
一、割点:
定义设 v ∈V (G) ,如果 w(G − v) > w(G) ,则称 v 为 G 的一个割点。(该定义与某些
著作有所不同,主要是在有环边的顶点是否算作割点上有区别)。
例

定理如果点 v 是图 G 的一个割点,则边集 E(G)可划分为两个非空子集 E1 和 E2 ,使得
G[E1 ] 和 G[E2 ]恰好有一个公共顶点 v。
推论对连通图 G,顶点 v 是 G 的割点当且仅当 G − v 不连通。
以上两个结论的证明留作习题。
定理设 v 是树 T 的顶点,则 v 是 T 的割点当且仅当 d(v) > 1。
证明:必要性:设 v 是 T 的割点,下面用反证法证明 d(v) > 1。
若 d(v) = 0 ,则T ≅ K1 ,显然 v 不是割点。
若 d(v) = 1,则T − v 是有ν(T − v) −1 条边的无圈图,故是树。从而 w(T − v) = 1 = w(T ) 。
因此 v 不是割点。
以上均与条件矛盾。
充分性:设 d(v) > 1,则 v 至少有两个邻点 u,w。路 uvw 是 T 中一条(u, w) 路。因 T 是树,
uvw 是 T 中唯一的(u, w) 路,从而 w(T − v) > 1 = w(T ) 。故 v 是割点。证毕。
推论每个非平凡无环连通图至少有两个顶点不是割点。
证明:设 T 是 G 的生成树,则 T 至少有两个叶子 u,v,由上一定理知,u,v 都不是 T 的割点,
即 w(T − u) = w(T ) = 1。由于T − u 是图 G − u 的生成树,故
w(G − u) = w(T − u) = w(T ) = 1 = w(G) ,
1
因此 u 不是 G 的割点。同理 v 也不是 G 的割点。证毕。
二、顶点割集:
定义对图 G,若 V(G)的子集V ′使得 w(G −V ′) > w(G) ,则称V ′为图 G 的一个顶点
割集。含有 k 个顶点的顶点割集称为 k-顶点割集。
注:(1)割点是 1-顶点割集。
(2)完全图没有顶点割集。
三、连通度: κ(G) = min{|V ′||V ′是 G 的顶点割集} 。完全图的连通度定义为
κ(Kν) =ν−1。空图的连通度定义为 0。
注:(1)使得|V ′|= κ(G) 的顶点割集V ′称为 G 的最小顶点割集。
(2)若κ(G) ≥ k ,则称 G 为 k 连通的。
(3)若 G 不连通,则κ(G) = 0 。
(4)若 G 是平凡图,则κ(G) = 0 。
(4)所有非平凡连通图都是 1 连通的。
例:

四、割边
定义设 e ∈ E(G) ,如果 w(G − e) > w(G) ,则称 e 为 G 的一条割边。
定理边 e 是 G 的割边当且仅当 e 不在 G