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

1、定义定义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 w，称子集称子集Vi(i=1,2,w w)的点导的

2、点导出子图出子图G(Vi)为为G的一个连通分支，并称的一个连通分支，并称w w为为G的连的连通分支数，记为通分支数，记为w w(G)。在有向图在有向图G 中，从顶点到顶点的可达关系不是中，从顶点到顶点的可达关系不是V上的等价关系。可达关系只满足自反和传递性质，上的等价关系。可达关系只满足自反和传递性质，而不满足对称性。有向图的连通性要比无向图复而不满足对称性。有向图的连通性要比无向图复杂。杂。定义定义10.3.2 若图若图G中只有一个连通分支，则称中只有一个连通分支，则称G是是连通图。连通图。(a)(b).eev定义定义10.3.3 设图设图G=(V,E)，若存在边，若存在边e，使得，使得 w

3、 w(G-e)w w(G)，则称则称 e为为G的的割边割边；若存在顶点若存在顶点v，使得，使得w w(G-v)w 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 的路，但是

4、，的路，但是，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中存在一条包含顶点中存在一

5、条包含顶点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的

6、任意一个圈上；的任意一个圈上；(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略去其中每条弧的方

7、向后所得的无略去其中每条弧的方向后所得的无向图向图G0称为称为G的基础图。的基础图。345图图G21图图G的基础图的基础图34521定义定义10.3.5 设设G为有向图，若为有向图，若G的任意两个顶点都的任意两个顶点都是可互达的，则称是可互达的，则称G为强连通的；为强连通的；若若G的任意两个顶点之间都至少是可达的，则称的任意两个顶点之间都至少是可达的，则称G为单向连通的；为单向连通的；若若G的其基础图是连通的，则称的其基础图是连通的，则称G为弱连通的为弱连通的。a强连通强连通b单向连通单向连通c弱连通弱连通1234 注意，如果注意，如果G为强连通的，则为强连通的，则G是单向连通的，反是单向连通

8、的，反之未必成立；同样，若之未必成立；同样，若G是单向连通的，则是单向连通的，则G必为必为弱连通的，反之也未必成立弱连通的，反之也未必成立。定理定理10.3.5 设设G为有向图，则为有向图，则G为强连通的为强连通的 G中中存在一个包含所有顶点的闭途径存在一个包含所有顶点的闭途径。证明证明 必要性：必要性：若若G为强连通的，则为强连通的，则G中任意两个顶点都可互中任意两个顶点都可互达，故我们可以得到达，故我们可以得到G中一条包含所有顶点的闭途径。中一条包含所有顶点的闭途径。充分性：若充分性：若G中存在一个包含所有顶点的闭途径，则显然，中存在一个包含所有顶点的闭途径，则显然，G中任意两个顶点都可互

9、达中任意两个顶点都可互达。定义定义10.3.6 设设G为有向图，则称为有向图，则称G的具有强连通性的具有强连通性质的极大子图为质的极大子图为G的强分图；的强分图；称称G的具有单向连通性质的极大子图为的具有单向连通性质的极大子图为G的单向分的单向分图；图；称称G的具有弱连通性质的极大子图为的具有弱连通性质的极大子图为G的弱分图。的弱分图。例例10.3.310.3.3 在图在图10.3.310.3.3中，由点集中，由点集1,2,3,4,5,6,7分别导出的有向图分别导出的有向图G的子图都是的子图都是G的强分图；的强分图；由顶点集由顶点集1,2,3,4,5,4,5,7,5,6分别导出的分别导出的G的

10、子图都是的子图都是G的单向分图；而由顶点集的单向分图；而由顶点集 1,2,3,4,5,6,7导出的导出的G的子图是的子图是G的弱分图。的弱分图。图图10.3.31234567定理定理10.3.6 设设G为有向图，则为有向图，则G的任意一个顶点都的任意一个顶点都恰好恰好在在G的一个强分图中；的一个强分图中；G的任意一个顶点和任意一条弧都的任意一个顶点和任意一条弧都至少至少在在G的一个的一个单向分图中；单向分图中；G的任意一个顶点和任意一条弧都的任意一个顶点和任意一条弧都恰好恰好在在G的一个的一个弱分图中。弱分图中。证证 显然，显然，G的任意一个顶点都在的任意一个顶点都在G的强分图中。若顶点的强分图中。若顶点v在在G的两个强分图的两个强分图G1和和G2中，则由强分图的定义知，中，则由强分图的定义知，G1和和G2中的顶点与顶点中的顶点与顶点v都可以互达，即都可以互达，即G1与与G2中的顶点都可以中的顶点都可以互达，与互达，与G1和和G2是是G的两个不同强分图矛盾。的两个不同强分图矛盾。