《7.2 通路、回路与图的连通性》由会员分享，可在线阅读，更多相关《7.2 通路、回路与图的连通性（4页珍藏版）》请在金锄头文库上搜索。
1、山东政法学院教案模版授课时间 第十五周 第 1 次课授课章节 7.2 通路、回路与图的连通性 任课教师及职称唐新华讲师教学方法与手段板书和电子课件结合 课时安排 2 课时使用教材和主要参考书1、教材：耿素云等，离散数学，清华大学出版社，20082.参考书左孝琳、李为槛、刘永才，离散数学（上海科技文献版）2006教学与目的要求：掌握路、回路、连通图的概念；掌握有向图的连通图、弱连通图的概念会判断一个图是强连通图或弱连通图。教学重点、难点:重点：通路与回路的定义，相互关系及其分类，掌握通路与回路的各种不同的表示方法；无向图的连通性，连通分支等概念 ； 无向图的点连通度、边连通度等概念及其之间的关系
2、；点割集与割点；边割集桥难点：会判断一个图是强连通图或弱连通图，点割集与割点；边割集桥教学内容:7.2 通路、回路与图的连通性一、本节主要内容简单通(回) 路, 初级通( 回)路, 复杂通(回)路无向连通图, 连通分支弱连通图, 单向连通图, 强连通图点割集与割点边割集与割边(桥) 二、教学内容通路与回路 定义 给定图 G=（无向或有向的） ，设 G 中顶点与边的交替序列=v0e1v1e2elvl，(1) 若i(1il), vi1 和 vi 是 ei 的端点(对于有向图, 要求 vi1 是始点, vi 是终点), 则称为通路, v0 是通路的起点, vl 是通路的终点, l 为通路的长度. 又
3、若 v0=vl，则称为回路.(2) 若通路 (回路)中所有顶点( 对于回路, 除 v0=vl)各异，则称为初级通路 (初级回路).初级通路又称作路径, 初级回路又称作圈.(3) 若通路( 回路)中所有边各异 , 则称为简单通路(简单回路), 否则称为复杂通路( 复杂回路).山东政法学院教案模版通路与回路(续)说明:在无向图中，环是长度为 1 的圈, 两条平行边构成长度为 2 的圈.在有向图中，环是长度为 1 的圈, 两条方向相反边构成长度为 2 的圈.在无向简单图中, 所有圈的长度3; 在有向简单图中, 所有圈的长度2. 通路与回路(续) 定理 在 n 阶图 G 中，若从顶点 vi 到 vj（
4、vi vj）存在通路，则从 vi 到 vj 存在长度小于等于 n1 的通路.推论 在 n 阶图 G 中，若从顶点 vi 到 vj（vi vj）存在通路，则从 vi 到 vj 存在长度小于等于 n1 的初级通路.定理 在一个 n 阶图 G 中，若存在 vi 到自身的回路，则一定存在 vi 到自身长度小于等于 n 的回路.推论 在一个 n 阶图 G 中，若存在 vi 到自身的简单回路，则一定存在长度小于等于 n 的初级回路. 无向图的连通性 设无向图 G=,u 与 v 连通: 若 u 与 v 之间有通路 . 规定 u 与自身总连通.连通关系 R=| u,v V 且 uv是 V 上的等价关系连通图:
5、 平凡图, 或者任意两点都连通的图连通分支: V 关于 R 的等价类的导出子图设 V/R=V1,V2,Vk, GV1, GV2, ,GVk是 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=vd(u,v)=d(v,u)（对称性）d(u,v)+d(v,w)d(u,w) （三角不等式)点割集 记 Gv: 从 G 中删除 v
6、及关联的边GV: 从 G 中删除 V中所有的顶点及关联的边Ge : 从 G 中删除 eGE: 从 G 中删除 E中所有边定义 设无向图 G=, 如果存在顶点子集 VV, 使 p(GV)p(G)，而且删除 V的任何真子集 V后（ VV） ，p(G V)=p(G), 则称 V为 G 的点割集. 若v为点割集, 则称 v 为割点.点割集(续)山东政法学院教案模版例 v1,v4, v6是点割集, v6 是割点. v2,v5是点割集吗？ 边割集定义 设无向图 G=, EE, 若 p(GE)p(G)且EE, p(GE)=p(G), 则称 E为 G 的边割集 . 若e 为边割集, 则称 e为割边或桥.在上一
7、页的图中，e1,e2，e1,e3,e5,e6，e8 等是边割集，e8 是桥，e7,e9,e5,e6是边割集吗？几点说明：Kn 无点割集n 阶零图既无点割集，也无边割集.若 G 连通，E 为边割集，则 p(GE)=2若 G 连通，V为点割集，则 p(GV)2 有向图的连通性 设有向图 D=u 可达 v: u 到 v 有通路. 规定 u 到自身总是可达的.可达具有自反性和传递性D 弱连通(连通): 基图为无向连通图D 单向连通: u,vV，u 可达 v 或 v 可达 u D 强连通: u,vV，u 与 v 相互可达强连通单向连通弱连通 有向图的连通性(续)例 下图(1)强连通, (2)单连通, (3) 弱连通有向图的短程线与距离u 到 v 的短程线: u 到 v 长度最短的通路 (u 可达 v)u 与 v 之间的距离 d: u 到 v 的短程线的长度若 u 不可达 v, 规定 d=.性质：d0, 且 d=0 u=v山东政法学院教案模版d+d d 注意: 没有对称性复习思考题、作业题：在一个 n 阶图 G 中，若存在 vi 到自身的回路，则一定存在 vi 到自身长度小于等于 n 的回路.下次课预习要点：无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的可达矩阵 无向图的关联矩阵实施情况及教学效果分析:院系部审核意见:院系部负责人签字年 月 日
