第十章 图的基本概念ppt课件

.,10.3图的连通性,定义10.3.1设图G=(V,E)，u,vV，若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是连通图。,(a),(b),.,e,e,v,.,定义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的基础图。,3,4,5,图G,2,1,图G的基础图,3,4,5,2,1,.,定义10.3.5设G为有向图，若G的任意两个顶点都是可互达的，则称G为强连通的；若G的任意两个顶点之间都至少是可达的，则称G为单向连通的；若G的其基础图是连通的，则称G为弱连通的。,a强连通,b单向连通,c弱连通,1,2,3,4,.,注意，如果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.3,1,2,3,4,5,6,7,.,定理10.3.6设G为有向图，则G的任意一个顶点都恰好在G的一个强分图中；G的任意一个顶点和任意一条弧都至少在G的一个单向分图中；G的任意一个顶点和任意一条弧都恰好在G的一个弱分图中。证显然，G的任意一个顶