mohammed

1 5.2 通路、回路、图的连通性  简单通(回)路, 初级通(回)路, 复杂通(回)路  无向图的连通性 无向连通图, 连通分支  有向连通图 弱连通图, 单向连通图, 强连通图  点割集与割点  边割集与割边(桥).

2 通路与回路 定义 给定图G=<V,E>（无向或有向的），G中顶点与边的交 替序列=v0e1v1e2…elvl， (1) 若i(1il), vi1, vi是ei的端点(对于有向图, 要求vi1是始点, vi是终点), 则称为通路, v0是通路的起点, vl是通路的终点, l为通路的长度. 又若v0=vl，则称为回路. (2) 若通路(回路)中所有顶点(对于回路, 除v0=vl)各异，则称为 初级通路(初级回路).初级通路又称作路径, 初级回路又称 作圈. (3) 若通路(回路)中所有边各异, 则称为简单通路(简单回路), 否则称为复杂通路(复杂回路)..

通路与回路实例 3.

4 通路与回路(续) 说明:  表示方法 ① 用顶点和边的交替序列(定义), 如=v0e1v1e2…elvl ② 用边的序列, 如=e1e2…el ③ 简单图中, 用顶点的序列, 如=v0v1…vl ④ 非简单图中,可用混合表示法,如=v0v1e2v2e5v3v4v5  环是长度为1的圈, 两条平行边构成长度为2的圈.  在无向简单图中, 所有圈的长度3; 在有向简单图 中, 所有圈的长度2..

5 通路与回路(续)  在两种意义下计算圈的个数 ① 定义意义下 在无向图中, 一个长度为l(l3)的圈看作2l个不同的 圈. 如v0v1v2v0 , v1v2v0v1 , v2v0v1v2, v0v2v1v0 , v1v0v2v1 , v2v1v0v2看作6个不同的圈. 在有向图中, 一个长度为l(l3)的圈看作l个不同的 圈. ② 同构意义下 所有长度相同的圈都是同构的, 因而是1个圈..

6 通路与回路(续) 定理 在n阶图G中，若从顶点u到v（uv）存在通 路，则从u到v存在长度小于等于n1的通路. 推论 在n阶图G中，若从顶点u到v（uv）存在通 路，则从u到v存在长度小于等于n1的初级通路. 定理 在一个n阶图G中，若存在v到自身的回路，则 一定存在v到自身长度小于等于n的回路. 推论 在一个n阶图G中，若存在v到自身的简单回 路，则存在v到自身长度小于等于n的初级回路..

7 无向图的连通性 设无向图G=<V,E>, u与v连通: 若u与v之间有通路. 规定u与自身总连通. 连通关系 R=是V上的等价关系 连通图:任意两点都连通的图. 平凡图是连通图. 连通分支: V关于连通关系R的等价类的导出子图 设V/R=, G[V1], G[V2], …,G[Vk]是G的连 通分支, 其个数记作p(G)=k. G是连通图 p(G)=1 例.

8 点割集 记 Gv: 从G中删除v及关联的边 GV : 从G中删除V 中所有的顶点及关联的边 Ge : 从G中删除e GE: 从G中删除E中所有边 定义 设无向图G=<V,E>, V V, 若p(GV )>p(G)且 V V , p(GV )=p(G), 则称V 为G的点割集. 若为点割集, 则称v为割点..

9 点割集实例 例 找出点割集..

10 边割集 定义 设无向图G=<V,E>, E E, 若p(GE )>p(G)且E E , p(GE )=p(G), 则称E 为G的边割集. 若为边割集, 则称e 为割边或桥. 说明：Kn无点割集 n阶零图既无点割集，也无边割集. 若G连通，E 为边割集，则p(GE )=2 若G连通，V 为点割集，则p(GV )2.

11 边割集实例 例 找出边割集..

12 有向图的连通性 设有向图D=<V,E> u可达v: u到v有通路. 规定u到自身总是可达的. 可达具有自反性和传递性 D弱连通(连通): 基图为无向连通图 D单向连通: u,vV，u可达v 或v可达u D强连通: u,vV，u与v相互可达 强连通单向连通弱连通.

13 有向图的连通性(续) 定理(强连通判别法) D强连通当且仅当D中存在经 过每个顶点至少一次的回路 定理(单向连通判别法) D单向连通当且仅当D中存 在经过每个顶点至少一次的通路 例 强连通 单向连通 弱连通.

作业  习题5.18.

15 5.3 图的矩阵表示  无向图的关联矩阵  有向图的关联矩阵  有向图的邻接矩阵  有向图的可达矩阵.

16 无向图的关联矩阵 定义 设无向图G=<V,E>, V=, E=, 令mij为vi与ej的关联次数，称(mij)nm为G 的关联矩阵，记为M(G). 例 M(G)= 1 1 1 0 0 0 1 1 1 0 1 0 0 1 2 0 0 0 0 0            .

17 无向图的关联矩阵 平行边的列相同 行全为 为孤立点当且仅当第 5) ( 0 4) ( 2 3) ( 2,1 ,..., ) ( ) ( 2) ( , 1 i v m m n i d v m i j i ij i m j ij       定义 设无向图G=<V,E>, V=, E=, 令mij为vi与ej的关联次数，称(mij)nm为G 的关联矩阵，记为M(G). 性质 (1) 每一列恰好有两个1或一个2.

18 有向图的关联矩阵      为 的终点 ， 与 不关联 ， 的始点 为 j i j i j i ij e v e v e v m 1 0 , 1 定义 设无环有向图D=<V,E>, V=, E=, 令 则称(mij)nm为D的关联矩阵，记为M(D)..

有向图的关联矩阵(续) 性质 (1) 每一列恰好有一个1和一个-1 (2) 第i行1 的个数等于d+(vi), -1 的个数等于d-(vi) (3) 1的总个数等于-1的总个数, 且都等于m (4) 平行边对应的列相同 19 例 M(D)= 1 1 0 0 0 1 0 1 1 1 0 0 0 0 1 0 1 1 1 0                 .

20 的回路数 中长度为 的通路数 中长度为 1 4) ( 1 3) ( 2,1 ,..., ), ( 2) ( 2,1 ,..., ( ), 1) ( 1 1) ( , 1) ( 1 1) ( 1 1) ( D a D m a n j v d a n i v d a n i ii j i ij j n i ij i n j ij                     (1) ij a 定义 设有向图D=<V,E>, V=, E=, 令 为顶点vi邻接到顶点vj边的条数， 称( )mn为D的邻接矩阵, 记作A(D), 简记为A. 性质 (1) ij a 有向图的邻接矩阵.

有向图的邻接矩阵实例 21              0 1 0 1 1 0 0 1 0 1 0 2 0 0 0 1 A.

22 D中的通路及回路数 (l) ij a (l ) ii a    n i n j l ij a 1 1 ) (   n i l ii a 1 ) ( 定理 设A为n阶有向图D的邻接矩阵, 则Al(l1)中 元素 为D中vi到vj长度为 l 的通路数， 为vi到自身长度为 l 的回路数， 为D中长度为 l 的通路总数， 为D中长度为 l 的回路总数..

23 D中的通路及回路数(续) 例 问在有向图D中 (1) 长度为1, 2, 3, 4的通路各有多 少条？其中回路分别为多少条？ (2) 长度小于或等于4的通路为多 少条？其中有多少条回路？    n i n j l ij b 1 1 ) (   n i l ii b 1 ) ( 推论 设Bl=A+A2+…+Al(l1), 则Bl中元素 为D中长度小于或等于l 的通路数， 为D中长度小于或等于l 的回路数..

24 例(续) 长度 通路 回路                                                     1 0 0 4 0 1 0 4 1 0 0 5 0 0 0 1 0 1 0 3 1 0 0 3 0 1 0 4 0 0 0 1 1 0 0 2 0 1 0 2 1 0 0 3 0 0 0 1 0 1 0 1 1 0 0 1 0 1 0 2 0 0 0 1 4 3 2 A A A A 合计 50 8 1 8 1 2 11 3 3 14 1 4 17 3.