图的基本概念.ppt

10.3 图的连通性 定义10.3.1 设图G=(V, E)，u, v∈V，若G中存在一条以 u与 v为端点的路P，则称 u到 v是可达的。 当G为有向图时，若G中存在一条以 u为起点 v为终点的有向路P，则称从 u到 v是可达的。 规定u到u自身是可达的。 在无向图G =(V, E)中，顶点之间的可达关系是V上的一个等价关系 R。R 诱导出V 的一个划分，π ={V1,V2,?,Vw}，称子集Vi (i =1, 2,?, w)的点导出子图G(Vi)为G的一个连通分支，并称w为G的连通分支数，记为w(G)。 在有向图G 中，从顶点到顶点的可达关系不是V上的等价关系。可达关系只满足自反和传递性质，而不满足对称性。有向图的连通性要比无向图复杂。 定义10.3.2 若图G中只有一个连通分支，则称G是连通图。 定义10.3.3 设图G=(V, E)，若存在边e，使得 w(G-e) w(G)，则称 e为G的割边； 若存在顶点v，使得w(G-v) w(G)，则称v为G的割点。 G为极小连通图等价于G的边都是割边。 引理10.3.1 设图G = (V, E)为连通图，C为G中的圈，e = (u, v)为圈C上的边，则G的子图G-e仍是连通的。 证 若不然，子图G-e不连通，则边e的端点u与v应在G-e的两个不同分支上，即在G-e的中没有从顶点 u 到 v 的路，但是，e = (u, v)为圈C上的边，因此G-e 的子图C-e中必有从顶点 u到 v的路，也即在G-e 的中有从顶点 u到 v的路，矛盾。 定理10.3.1 设图G=(V, E)为连通图，则边e为G的割边?存在G的顶点u和v，使得G中所有包含顶点u和v的路必过边e。 证 必要性：设顶点u和v为割边e的端点，则G中所有包含顶点u和v的路必过边e。若不然，在G中存在一条包含顶点u和v的路P不经过e，则P与e就组成G中的一个圈，由引理10.3.1知G-e仍是连通的，与e为G的割边矛盾。 充分性：假如e不是G的割边，即G-e连通，于是在G-e中存在一条以顶点u和v为端点的路P，而路P就是G中包含顶点u和v而不经过边e的路，矛盾。 定理10.3.2设图G = (V, E)，边e = (u, v) ∈ E，则下列命题等价： (1) e为图G的割边； (2) e不在图G的任意一个圈上； (3) 在G的子图G-e中顶点u到v不可达； (4) 顶点u与v在G-e的两个不同的连通分支上。 定理10.3.3 设图G=(V, E)为连通图，则顶点v为G的割点?存在两个顶点u和w，使得G中所有包含顶点u和w的路必过顶点v。 定理10.3.4 设G=(V, E)是图，顶点v是G 的一个二度点，则顶点v为G的割点?v不在图G的任意一个圈上。 一个有向图G略去其中每条弧的方向后所得的无向图G0称为G的基础图。 定义10.3.5 设G为有向图，若G的任意两个顶点都是可互达的，则称G为强连通的； 若G的任意两个顶点之间都至少是可达的，则称G为单向连通的； 若G的其基础图是连通的，则称G为弱连通的。 注意，如果G为强连通的，则G是单向连通的，反之未必成立；同样，若G是单向连通的，则G必为弱连通的，反之也未必成立。 定理10.3.5 设G为有向图，则G为强连通的? G中存在一个包含所有顶点的闭途径。 证明 必要性：若G为强连通的，则G中任意两个顶点都可互达，故我们可以得到G中一条包含所有顶点的闭途径。 充分性：若G中存在一个包含所有顶点的闭途径，则显然，G中任意两个顶点都可互达。 定义10.3.6 设G为有向图，则称G的具有强连通性质的极大子图为G的强分图； 称G的具有单向连通性质的极大子图为G的单向分图； 称G的具有弱连通性质的极大子图为G的弱分图。 例10.3.3 在图10.3.3中，由点集{1, 2, 3}, {4}, {5}, {6}, {7}分别导出的有向图G的子图都是G的强分图；由顶点集{1, 2, 3, 4, 5}, {4, 5, 7}, {5, 6}分别导出的G的子图都是G的单向分图；而由顶点集 {1, 2, 3, 4, 5, 6, 7}导出的G的子图是G的弱分图。 定理10.3.6 设G为有向图，则G的任意一个顶点都恰好在G的一个强分图中； G的任意一个顶点和任意一条弧都至少在G的一个单向分图中； G的任意一个顶点和任意一条弧都恰好在G的一个弱分图中。 证 显然，G的任意一个顶点都在G的强分图中。若顶点v在G的两个强分图G1和G2中，则由强分图的定义知，G1和G2中的顶点与顶点v都可以互达，即G1与G2中的顶点都可以互达，与G1和G2是G的两个不同强分图矛盾。 * * (a) (b) . e e v