东北农业大学《离散数学》课件-第十一章（第十二周）.pdfVIP

第十一章 图的连通性 东北农业大学离散数学第十一章 本章各节间的关系概图 11.2 无向图的连通性 11.3 有向图的连通性 无向图 连通 有向图 连通 11.1 通路与回路 东北农业大学离散数学第十一章 图的连通性在计算机科学技术相关领域的应用 操作系统 回路 图的 通路 计算机网络 判断并发进程是否存在递归和死锁 连通性 回路 表示 网络 最短 优化 路径 东北农业大学离散数学第十一章 11.1 通路与回路 定义11.1 东北农业大学离散数学第十一章 11.1 通路与回路 基本回路：一条回路，除始点与终点相同外其余结点均不相同，则称该路 径为基本回路或者圈。 简单回路：一条回路经过的所有边均不相同，则称该回路为简单回路或闭 迹。 长度：路径P中所含的边数称为路径P的长度。 长度为奇数的圈称为奇圈，长度为偶数的圈称为偶圈。 注意：基本路径必定是简单路径，基本回路必定是简单回路，反之不一定 成立。 东北农业大学离散数学第十一章 11.1 通路与回路 表示法 • ①定义表示法 • ②只用边表示法 • ③只用顶点表示法（在简单图中） • ④混合表示法（顶点表示法基础上标示平行边） 环（长为1的圈）的长度为1，两条平行边构成的圈长度为2， 无向简单图中，圈长3，有向简单图中圈的长度2. 东北农业大学离散数学第十一章 例11.1 ： 在下图中分别找出一条基本路径、简单路径、基本回路和简单回路。 v1 解：路径： e1 e3 e2 v2 v3 基本路径： e4 简单路径： e5 e6 e7 基本回路： v4 e8 v5 简单回路： 东北农业大学离散数学第十一章 定理11.1 在一个具有n个结点的图中，如果从结点v 到结点v 存在一条路径，则从结点v 到 j k j 结点v 存在一条不多于n −1条边的