(50)--5.6 有向图的连通性.ppt

有向图的连通性例例：列举以下有向图的各种通路和回路。：列举以下有向图的各种通路和回路。v4v3v2e1e2e3e4e5e6v1 1：v3e4v4e6v2e5v4e6v2 通路，长度通路，长度4 4 2：v3e4v4e6v2e5v4 简单通路，长度简单通路，长度3 3 3：v3e4v4 初级通路，简单通路，长度初级通路，简单通路，长度1 1 4：v2e3v2e5v4e6v2 简单回路，长度简单回路，长度3 3 5：v2e5v4e6v2 初级回路，简单回路，长度初级回路，简单回路，长度2 2d=2 d=有向图中，一般情况下，有向图中，一般情况下，d d1、通路与回路设 D=是一个简单有向图，n如果略去D中所有有向边的方向后，所得的无向图是连通图，则称D是弱连通的；n如果对D中任何一对结点，至少有一结点可达另一结点，则称D是单向连通的；n如果D中任何一对结点之间都是相互可达的，则称D是强连通的。2、有向图的连通性D3v1v2v3v4D1v1v2v3v4D4v1v2v3v4D2v1v2v3v4非连通图弱连通图单向连通图弱连通图强连通图单向连通图弱连通图2、有向图的连通性简单有向图 D 是强连通图当且仅当D 中存在一条经过每个结点至少一次的回路。证明：n(充分性)如果D中有一个回路，它至少包含每个结点一次，则D中任意两个结点都是相互可达的，故D是强连通图。n(必要性)如果有向图D是强连通的，则任两个结点都是相互可达的，故必可作一回路经过图中所有结点。若不然则必有一回路不包含某一结点v，因此，v与回路上的各结点就不是相互可达，这与强连通条件矛盾。3、有向连通图的判定n有向图D是单向连通图的充要条件是D中存在一条经过所有结点至少一次的通路。n若D中至少有两个以上结点为全入度或全出度时，有向图D仅仅弱连通。D3v1v2v3v4D4v1v2v3v4D2v1v2v3v4弱连通图单向连通图强连通图3、有向连通图的判定设D=是一个简单有向图，n称D的极大强连通子图称为D的强连通分支；n称D的极大单向连通子图为D的单连通分支；n称D的极大弱连通子图为D的弱连通分支。极大性：任意增加一个结点或 一条边就不再强单向弱连通了。4、连通分支v1,v2,v3,v4，v5,v6,v7导出的子图是弱连通分支;v1,v2,v3，v1,v2,v4，v5,v6,v7 导出的子图是单向连通分支;v1，v2，v3，v4，v5,v6,v7 导出的子图是强连通分支。v1v2v3v4v5v6v7图D4、连通分支THANKYOU