离散数学七.ppt

7.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) 若通路(回路)中所有边各异, 则称为简单通路(简单回路), 否则称为复杂通路(复杂回路). 通路与回路(续) 说明: 表示方法 ① 用顶点和边的交替序列(定义), 如?=v0e1v1e2…elvl ② 用边的序列, 如?=e1e2…el ③ 简单图中, 用顶点的序列, 如?=v0v1…vl ④ 非简单图中,可用混合表示法,如?=v0v1e2v2e5v3v4v5 环是长度为1的圈, 两条平行边构成长度为2的圈. 在无向简单图中, 所有圈的长度?3; 在有向简单图中, 所有圈的长度?2. 通路与回路(续) 在两种意义下计算的圈个数 ① 定义意义下 在无向图中, 一个长度为l(l?3)的圈看作2l个不同的圈. 如v0v1v2v0 , v1v2v0v1 , v2v0v1v2, v0v2v1v0 , v1v0v2v1 , v2v1v0v2看作6个不同的圈. 在有向图中, 一个长度为l(l?3)的圈看作l个不同的圈. ② 同构意义下 所有长度相同的圈都是同构的, 因而是1个圈. 通路与回路(续) 定理 在n阶图G中，若从顶点vi到vj（vi?vj）存在通 路，则从vi到vj存在长度小于等于n?1的通路. 推论 在n阶图G中，若从顶点vi到vj（vi?vj）存在通 路，则从vi到vj存在长度小于等于n?1的初级通路. 定理 在一个n阶图G中，若存在vi到自身的回路，则 一定存在vi到自身长度小于等于n的回路. 推论 在一个n阶图G中，若存在vi到自身的简单回 路，则一定存在长度小于等于n的初级回路. 无向图的连通性 设无向图G=V,E, u与v连通: 若u与v之间有通路. 规定u与自身总连通. 连通关系 R={u,v| u,v ?V且u?v}是V上的等价关系 连通图:任意两点都连通的图. 平凡图是连通图. 连通分支: V关于连通关系R的等价类的导出子图 设V/R={V1,V2,…,Vk}, G[V1], G[V2], …,G[Vk]是G的连通分支, 其个数记作p(G)=k. G是连通图? p(G)=1 短程线与距离 u与v之间的短程线: u与v之间长度最短的通路 (u与v连通) u与v之间的距离d(u,v): u与v之间短程线的长度 若u与v不连通, 规定d(u,v)=∞. 性质： d(u,v)?0, 且d(u,v)=0 ? u=v d(u,v)=d(v,u) d(u,v)+d(v,w)?d(u,w) 点割集 记 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}为点割集, 则称v为割点. 点割集(续) 例 {v1,v4}, {v6}是点割集, v6是割点. {v2,v5}是点割集吗？ 边割集 定义 设无向图G=V,E, E ??E, 若p(G?E ?)p(G)且?E ???E ?, p(G?E ??)=p(G), 则称E ?为G的边割集. 若{e}为边割集, 则称e 为割边或桥. 在上一页的图中，{e1,e2}，{e1,e3,e5,e6}，{e8}等是边割集， e8是桥，{e7,e9,e5,e6}是边割集吗？ 几点说明： Kn无点割集 n阶零图既无点割集，也无边割集. 若G连通，E ?为边割集，则p(G?E ?)=2 若G连通，V ?为点割集，则p(G?V ?)?2 有向图的连通性 设有向图D=V,E u可达v: u到v有通路. 规定u到自身总是可达的. 可达具有自反性和传递性 D弱连通(连通): 基图为无向连通图 D单向连通: ?u,v?V，u可达v 或