道路与回路课件

1 第二章 道路与回路 2 路与回路 3 有向道路 有向图 G=(V, A) 中，一条 有向道路 指的是一个首尾相接的弧的有限非空序列 P = (k1) 其中 ( i =0. k ), ( j =1. 且 ( j=1. k ) 的 起点 和 终点 ， 的 长度 。在简单图中，也可记作 P = ( ， 或 路与回路 4 简单道路 若对任意的 ij有 称之为 简单有向道路 (没有重复边的路径 ) 回路 若 称之为 封闭的 。 简单封闭有向道路（闭迹）称为 有向简单回路 。 初级道路 若对任意的 i 称之为 初级道路 /基本道路 /路径 (or 圈 若对任意的 ij有 例外地 之为 初级回路 /圈 ( 无向图具有完全类似的定义。 单道路与圈 5 路与回路 练习：找出上图结点 1至结点 9的简单道路和初级道路， 1到 1的有向回路和圈。 6 容易证明： 定理 2（ 1）基本道路是简单道路； （ 2）如果存在 u到 存在 u到 v 的基本道路； (3) (4) n. 本道路 7 定理 2无向图 G=(V, E)， u, v V 且 uv。若 u,v 之间存在两条不同的路，则 G 中存在一条回路。 证明 （构造法） 定理 2无向图 G=(V, E) 中每个顶点的度均为偶数，且至少有一个顶点不是孤立点，则 G 中存在一条回路。 证明 （反证法）设 v)必存在 0 其他 可求得 P。 算法复杂度 O(路矩阵 14 道路矩阵可以通过二值矩阵的逻辑运算求得。 定义 二值元素的逻辑运算： 0 0=0， 0 1=1 0=1， 1 1=1 0 0=0， 0 1=1 0=0， 1 1=1 定义 二值矩阵的逻辑运算。 设有矩阵 A = ( B = (矩阵元素值域为 0,1，定义运算： i j i ji k k ( A B ) =( A B ) = ( )路矩阵的计算 15 定义 A(k) = A(k1) A ( k2 )， A(1) = A 注意 A(k) 与 区别 定理 2设 Ann 是图 从 l 的路，则 A(l) 1，否则 A(l) 0。 证明 对 l 作归纳；或直接引用 定理 2 路矩阵的计算 16 设 A n的邻接矩阵，求 。 1. P A 2. i=1 to n . j=1 to n . k=1 to n . ( 计算复杂度 O(路矩阵及 初始： 的直达路径 第 v1,v i的路径 。 17 例 图 如右，使用 的道路矩阵 P。 0 1 0 00 0 1 1A = 1 1 0 11 0 0 0解 P A 0 1 0 00 0 1 1P = 1 1 0 11 0 0 路矩阵及 18 (1) i =1 0 1 0 00 0 1 1P = 1 1 0 11 0 0 0 j =1,2,3,4 增量方向 i =1 矩阵元素处理次序： ， 路矩阵及 19 如： ( = ( = 0 ( = ( = 1 ( = ( = 0 0 1 0 00 0 1 1P = 1 1 0 11 1 0 0结果为 路矩阵及 20 上的搜索 可以使用搜索的方法判断从一个顶点 深度优先 顶点 果不是，则从 果没有后继 ,则回溯，直至找到或者没有可搜索的顶点。 21 上的搜索 广度优先 先检查其所有的直接后继是否等于；然后依次检查这些后继的直接后继，直到找到或者没有可遍历顶点。 练习：编写一个使用深度优先或者广度优先搜索判定两个点之间是否有道路的程序。 22 若连通图 G=(V, E) 中存在一条简单回路（无重复边）经过 称该回路为 在 定理 2设有连通图 G=(V, E)，则下述命题等价： (1) (2) 证明 （略） 路 23 注意定理中对图的连通性的假定； 定理对非简单图也成立； 定理的证明过程给出了为一个 定理 2设连通图 G=(V, E)中恰有 2个顶点度为奇数，则 证明 连接两个奇度数结点形成 删除该边即可。 路 24 有向图的 若有向连通图 G=(V, A) 中存在一条简单有向回路经过 称该回路为该图为 定理 2设连通有向图 G=(V, A)，则下述命题等价： (1) (2) 证明 （略） 路 25 若连通图 G=(V, E) 中存在一条初级道路（无重复顶点）经过 称该道路为 在 ）的图称 为 引入记号： G =(V, E)， SV。从 中的顶点及其关联边得到的 S。 路 26 构造 他边可以删除； 左图如有 则必包含三个二度结点的邻接边，从而中心结点至少有三个邻接边包含在其中，故不可能有圈。 27 定理 2若 G=(V, E)是一个 S，则 W(GS) |S| 证明 记 ， 中所有顶点。 考察 CS：每从 的一个顶点，连通分支数至多增加 1（第一次以及当该顶点处于边缘时操作不会增加连通分支数），故 W(CS) |S| 而 中添加边构成，故 W(GS) W(CS) 所以 W(GS) |S| 28 例 图 G 1 2 3 4 5 7 8 6 令 S=2,6，则 W(GS)=3。而 |S|=2，即 W(GS)|S| 故图 1 3 4 5 7 8 图 29 例 |V|=10， 对任何 SV， 都有 W(GS)S ， 但 是 作习题）。存在 删除一个或者两个顶点仍然连通，删除三个顶点最多得到两个连通分支， 30 例 下图不存在 给图的相邻顶点标以 A， B，则 ,B. 31 定理 2简单图 G=(V, E)， n=|V|，若对任一对不相邻顶点 u, vV, uv，有 u) + v) n1，则 证明 (梗概 ) (1) (2) 如果 v1,v p 赋予一个非负实数权 得到一个有向网络。 距离矩阵 对上述网络，定义 D=(nn， n=|V| 当 A 其它 带权路径长度 对上述网络，路径 , 带权路径长度定义为 短路径 1,11 39 两点间的最短距离 对上述网络，结点 带权路径长度称为 引理 在有向网络中，若路径 , 路径 , 短路径 证明 如果路径 , 是 , 40 法 本思想 : 如果 么 按路径长度的递增次序，逐步产生最短路径 . 设源点为 即具有最小权的边 ; 其终点是 u，则或者由一条已求得的最短路径（ v)和边 构成； 直到从顶点 41 法 例：求 用 S=v5 v4 v3 v2 v1 00 60 30 10 10 20 5 50 第一条最短路径： ( S = v0,求下一条最短路径： 先求 结点的路径： (v0,v2, 60 (v0, 30 (v0, 100 第二条最短路径： (v0,， S = v0,42 法 v5 v4 v3 v2 v1 00 60 30 10 10 20 5 50 第一条最短路径： ( S = v0,求下一条最短路径： 先求 结点的路径： (v0,v2, 60, (v0,v4,50 (v0, 100, (v0,v4, 90 第二条最短路径： (v0,， S = v0,第三条最短路径： (v0,v4,， S = v0,第四条最短路径： (v0,v4,v3,， S = v0,43 法 用 引入一个辅助数组 D, Dj表示 当前找到的从源点 途径 初始状态： S= 若从源点 Di为该边上的权值； 若从源点 有边，则 Di为 + 一般情况下， ),(),(; 3. 在 k, 并将 ； 4. 修改数组 D: Dj=j, Dk + W; 5. 重复 3， 4 直至求得 此外 , 增设一个数组 若 ,wk,v是 则 Pv=Pw( , P45 法 则结果不正确； 时一个无向边次相当于两个有向边。 习题 证明 46 例 单源点最短距离的 123455 5 4 0 2 55 2 04 0 2 0 1 0 2 02 5 2 01 0 2 5 5 5 结果： U = (0, 50 , 55 , 40 , 25) 计算复杂度： O(47 对于任意结点 v, 假如在将加入之前另外有一条更短的路径，首先经过，然后到达，那么在之前加入，矛盾。 48 键路径 作业网络 一项工程通常包括多个工序，这些工序间存在次序的约束：一个工序的开始的前提是某些工序已经结束。每个工序有预计的完成时间。 1 2 3 4 5 6 编号 课程号 先修课 时间 49 1 2 3 4 5 6 1 4 2 3 6 5 3 1 1 2 1 1 顶点表示活动的图 (：工序用顶点表示，工序 示，其权表示工序 50 1 4 2 3 6 5 3 1 1 2 1 1 一个工程的两个问题： 工程能否顺利进行，即可否找到工序的一个线性排列： v1,v2,v3,v4,v5,得如果 是一条有向边，那么 iA, 则 边 所带的非负实数权为完成作业 作业开始条件：该作业的所有前驱作业全部完成； 无回路假设 (向无环图 )； 网络中有且只有一点入度为 0，称为源点，表示工程开始；有且只有一点出度为 0，称为汇点，表示工程结束。 键路径 54 键路径 关键路径 =(V,A)中从源点 关键路径不一定是唯一的。 关键路径的长度为完成任务所需的必要时间 T。 关键作业 处于关键路径上的作业。 记 ( 特别地， (=( 则有 ),()(m a x)(, 55 根据以上关系，可以按照拓扑排序顺序求 (。 定理 4将 =(V,A)的结点按照拓扑序列排序为 , 则 (0, (= (1 i 定 。 则 最长路径长度。 键路径 56 例 键路径 v2 v5 v3 v4 v7 1 1 2 1 1 v1 0 0 0 (0, (0, (0, (3, (1, (5, (2, (5 关键路径 v1,v2,v4,v6,(5。 57 键路径 作业最早开始时间 从源点到该作业 ( 作业最晚开始时间 设作业 ( 时刻而不会影响任务完成的预期时间 T= (,则有 缓冲时间 不影响