文档介绍：1 第二章图的连通性连通图:任二顶点间有路相连。例可见在连通图中,连通的程度也是有高有低。本章的目的就是定义一种参数来度量连通图连通程度的高低。§ 割边、割点与连通度一、割点: 定义 设)(GVv?, 如果)()(GwvGw??, 则称 v为G 的一个割点。( 该定义与某些著作有所不同,主要是在有环边的顶点是否算作割点上有区别)。例定理 如果点 v 是图 G 的一个割点, 则边集 E (G) 可划分为两个非空子集 1E 和2E , 使得][ 1EG 和][ 2EG 恰好有一个公共顶点 v。推论 对连通图 G ,顶点 v是G 的割点当且仅当 vG?不连通。以上两个结论的证明留作习题。定理 设v 是树 T 的顶点,则 v是T 的割点当且仅当 1)(?vd 。证明:必要性:设 v是T 的割点,下面用反证法证明 1)(?vd 。若0)(?vd ,则 1KT?,显然 v 不是割点。若1)(?vd ,则vT?是有1)(??vT?条边的无圈图, 故是树。从而)(1)(TwvTw???。因此 v 不是割点。以上均与条件矛盾。充分性:设 1)(?vd ,则 v 至少有两个邻点 u,w 。路 uvw 是T 中一条),(wu 路。因 T 是树, uvw 是T 中唯一的),(wu 路,从而)(1)(TwvTw???。故 v 是割点。证毕。推论 每个非平凡无环连通图至少有两个顶点不是割点。证明:设T是G 的生成树,则T 至少有两个叶子 u,v, 由上一定理知,u,v 都不是 T 的割点, 2 即1)()(???TwuTw 。由于 uT?是图uG?的生成树,故)(1)()()(GwTwuTwuGw??????, 因此 u 不是 G 的割点。同理 v 也不是 G 的割点。证毕。二、顶点割集: 定义 对图 G ,若 V(G) 的子集 V ?使得)()(GwVGw???,则称 V ?为图 G 的一个顶点割集。含有 k 个顶点的顶点割集称为 k- 顶点割集。注:(1 )割点是 1 -顶点割集。(2 )完全图没有顶点割集。三、连通度:VVG ???|| min{| )(?是G 的顶点割集} 。完全图的连通度定义为 1)(?????K ,空图的连通度定义为 0。注: (1) 使得)(||GV???的顶点割集 V ?称为 G 的最小顶点割集。(2 )若kG?)(?,则称 G为k 连通的。(3 )若 G 不连通,则 0)(?G?。(4 )若 G 是平凡图,则 0)(?G?。(4 )所有非平凡连通图都是 1 连通的。例: 四、割边定义 设)(GEe?,如果)()(GweGw??,则称 e为G 的一条割边。定理 边e是G 的割边当且仅当 e 不在 G 的任何圈中。证明:证其逆否命题: e 不是割边当且仅当 e 含在 G 的某个圈中。必要性:设e= xy 不是割边。假定 e 位于 G 的某个连通分支 1G 中,则eG? 1 仍连通。故在 eG? 1 中有),(yx 路P,P+e 便构成 1G 中一个含有 e 的圈。充分性:设 e 含在 G 的某个圈 C 中,而 C 含于某连通分支 1G 中,则 eG? 1 仍连通。故)()(GweGw??,这说明 e 不是割边。证毕。定理 一个连通图是