图论讲义2连通性.pdfVIP

第二章 图的连通性 连通图：任二顶点间有路相连。 例 可见在连通图中，连通的程度也是有高有低。 本章的目的就是定义一种参数来度量连通图连通程度的高低。 §2.1 割边、割点与连通度 一、割点： 定义 2.1.1 设v ∈V(G) ，如果w(G −v) w(G) ，则称v 为 G 的一个割点。（该定义与某些 著作有所不同，主要是在有环边的顶点是否算作割点上有区别）。 例 定理 2.1.1 如果点 v 是图 G 的一个割点，则边集E(G)可划分为两个非空子集E 和E ，使得 1 2 G[E ] 和 G[E ] 恰好有一个公共顶点 v 。 1 2 推论 2.1.1 对连通图 G，顶点v 是 G 的割点当且仅当G −v 不连通。 以上两个结论的证明留作习题。 定理 2.1.2 设 v 是树 T 的顶点，则v 是 T 的割点当且仅当d (v) 1。 证明：必要性：设 v 是 T 的割点，下面用反证法证明d (v) 1。 若d (v) 0 ，则T ≅K 1 ，显然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 是割点。证毕。 推论 2.1.2 每个非平凡无环连通图至少有两个顶点不是割点。 证明：设 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 的割点。证毕。 二、顶点割集： ′ ′ ′ 定义 2.1.2 对图 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 连通的。 例： 四、割边 定义 2.1.3 设e ∈E (G) ，如果w(G −e) w(G) ，则称 e 为 G 的一条割边。 定理 2.1.3 边 e 是 G 的割边当且仅当e 不在 G 的任何圈中。 证明：证其逆否命题：e 不是割边当且仅当 e 含在 G 的某个圈中。 必要性：设 e = xy 不是割边。假定 e 含在 G 的某个连通分支G 中，则G −e 仍连通。故在 1 1 G −e 中有(x , y ) 路 P ，P + e 便构成 G 中一个含有e 的圈。 1