耿素云等清华版离散数学ppt课件第八章特殊的图

第八章 一些特殊的图 定义2 给定简单无向图G=，若E*E，且E*中任意两条 边都是不相邻的，则E*称为G的一个匹配或边独立集，若在E*中再 加入任何一条边都不是匹配，称E*为极大匹配，边数最多的极大匹 配为最大匹配，最大匹配中边的个数称为G的匹配数，记为 令M是G的一个匹配，若结点v与M中的边关联，则称v是M饱和 点；否则，称v是M非饱和点；若G中的每个结点都是M饱和点，则 称M是完美匹配。显然，每个完美匹配是最大匹配，但反之不真。 定义3 设G=为一个二部图,M为G中一个最大匹配， 若|M|=min|V1|，|V2|，称M为G中的一个完备匹配，且 若|V1|V2|,称M为V1到V2的一个完备匹配； 若|V1|=|V2|，此时M为G的完美匹配； （完美匹配是完备匹配，反之不真） 定理2 （Hall 定理） 设二部图G=，|V1|V2|,G中存在从 V1到V2的完备匹配当且仅当V1中任意k个顶点至少 邻接V2中的k个顶点。（相异性条件） 定理3 设二部图G=，如果： （1）V1中每个顶点至少关联t（t0）条边； （2）V2中每个顶点至多关联t条边；（t条件） 则G中存在V1到V2的完备匹配。 满足t条件的二部图一定满足相异性条件；反之不真 第二节 欧拉图 PLAY 第三节 哈密顿图 第四节 平面图 第五节 图中顶点的着色（无环无向图） 第六节 地图的着色与平面图的点着色 第七节 边着色（无环无向图） 第三节 带权图与货郎担问题 第十七章 平面图及图的着色 第十七章 习题课 解 证 证 解 图20 图19 解 最短路径 (Shortest Path) v最短路径问题：如果从图中某一顶点(称为 源点)到达另一顶点(称为终点)的路径可能 不止一条，如何找到一条路径使得沿此路 径上各边上的权值总和达到最小。 v问题解法 边上权值非负情形的单源最短路径问题 Dijkstra算法 边上权值为任意值的单源最短路径问题 Bellman和Ford算法 所有顶点之间的最短路径 Floyd算法 边上权值非负情形的单源最短路径问题 v问题的提法： 给定一个带权有向图D与源 点v，求从v到D中其它顶点的最短路径。 限定各边上的权值大于或等于0。 v为求得这些最短路径，Dijkstra提出按路 径长度的递增次序，逐步产生最短路径的 算法。首先求出长度最短的一条最短路径 ，再参照它求出长度次短的一条最短路径 ，依次类推，直到从顶点v到其它各顶点的 最短路径全部求出为止。 v举例说明 DijkstraDijkstra逐步求解的过程逐步求解的过程 v引入一个辅助数组dist。它的每一个分量 disti表示当前找到的从源点v0到终点vi 的 最短路径的长度。初始状态： 若从源点v0到顶点vi有边，则disti为该边上 的权值； 若从源点v0到顶点vi 没有边，则disti为+ 。 v一般情况下，假设 S 是已求得的最短路径 的终点的集合，则可证明：下一条最短路 径必然是从v0 出发，中间只经过S中的顶点 便可到达的那些顶点vx (vx V-S )的路径中 的一条。 v每次求得一条最短路径之后，其终点vk 加 入集合S，然后对所有的vi V-S，修改其 disti值。 Dijkstra算法可描述如下： 初始化： S v0 ; distj Edge0j, j = 1, 2, , n-1; / n为图中顶点个 数 求出最短路径的长度： distk min disti , i V- S ; S S U k ; 修改： disti min disti, distk + Edgeki , 对于每一个 i V- S ; 判断： 若S = V, 则算法结束，否则转 。 DijkstraDijkstra算法中各辅助数组的变化算法中各辅助数组的变化 如何从表中读取源点0到终 点v的最短路径？举顶点4为例 path4 = 2 path2 = 3 path3 = 0，反过来排列， 得到路径0, 3, 2, 4，这就是源 点0到终点4的最短路径。 边上权值为任意值的单源最短路径问题 v带权有向图D的某几条边或所有边的长度 可能为负值。利用Dijkstra算法，不一定 能得到正确的结果。 v源点0到终点2的最短路径应是0, 1, 2，其 长度为2，它小于算法中计算出来的dist2 的值。 若设源点若设源点v v = 0 = 0，使用，使用 DijkstraDijkstra算法，所得到算法，所得到 的结果是不对的。的结果是不对的。 vBellman和Ford提出了从源点逐次绕过其 它顶点，以缩短到达终点的最短路径长度 的方法。该方法有一个限制条件，即要求 图中不能包含有由带负权值的边组成的回 路。 v当图中没有由带负权值的边组成的回路 时，有n个顶点的图中任意两个顶点之间 如果存在最短路径，此路径最多有n-1条 边。 v我们将以此为依据考虑计算从源点v到其 它顶点u的最短路径的长度distu。 vBellman-Ford方法构造一个最短路径长度 数组序列dist1 u，dist2 u，distn-1 u 。其中，dist1 u是从源点v到终点u的只经 过一条边的最短路径的长度，dist1 u = Edgevu；dist2 u是从源点v最多经过两 条边到达终点u的最短路径的长度，dist3 u是从源点v出发最多经过不构成带负长 度边回路的三条边到达终点u的最短路径 的长度，dist n-1u是从源点v出发最多 经过不构成带负长度边回路的n-1条边到达 终点u的最短路径的长度。 v算法的最终目的是计算出dist n-1u。 v可以用递推方式计算distk u。 dist1 u = Edgevu； distk u = min distk-1 u, min distk-1 j+ Edgeju 设已经求出 distk-1 j, j = 0, 1, , n-1, 此即从 源点 v 最多经过不构成带负长度边回路的 k- 1 条边到达终点 j 的最短路径的长度。 从图的邻接矩阵中可以找到各个顶点 j 到达 顶点 u 的距离 Edgeju，计算 min distk-1 j+ Edgeju ，可得从源点 v 绕过各个顶 点，最多经过不构成带负长度边回路的 k 条 边到达终点u的最短路径的长度。 用它与distk-1 u比较，取小者作为distk u的 值。 图的最短路径长度图的最短路径长度 计算最短路径的计算最短路径的BellmanBellman和和FordFord算法算法 void Graph:BellmanFord ( const int n, const int v ) / /在带权有向图中有的边具有负的权值。从顶点在带权有向图中有的边具有负的权值。从顶点 v v / /找到所有其它顶点的最短路径。找到所有其它顶点的最短路径。 for ( int i = 0; i 0 pathu = i; 所有顶点之间的最短路径 v问题的提法：已知一个各边权值均大于0 的带权有向图，对每一对顶点 vi vj，要 求求出vi 与vj之间的最短路径和最短路径 长度。 vFloyd算法的基本思想： 定义一个n阶方阵序列： A(-1), A(0), , A(n-1). 其中 A(-1) ij = Edgeij； A(k) ij = min A(k-1)ij， A(k-1)ik + A(k-1)kj , k = 0,1, n-1 A(0) ij是从顶点vi 到vj , 中间顶点是v0的 最短路径的长度, A(k) ij是从顶点vi 到vj , 中间顶点的序号不大于k的最短路径的 长度, A(n-1)ij是从顶点vi 到vj 的最短路径 长度。 所有各对顶点之间的最短路径所有各对顶点之间的最短路径 void Graph:AllLengths ( const int n ) / / EdgeEdge n n n n 是一个具有是一个具有n n个顶点的图的邻接矩阵。个顶点的图的邻接矩阵。 / / a a i i j j 是顶点是顶点 i i 和和 j j 之间的最短路径长度。之间的最短路径长度。pathpath i i j j / /是相应路径上顶点是相应路径上顶点 j j 的前一顶点的顶点号的前一顶点的顶点号, , 在求在求 / /最短路径时图的类定义中要修改最短路径时图的类定义中要修改pathpath为为 / /pathpath NumVerticesNumVertices NumVerticesNumVertices 。 for ( int i = 0; i j & aij ,。 FloydFloyd算法允许图中有带负权值的边，但不许有算法允许图中有带负权值的边，但不许有 包含带负权值的边组成的回路。包含带负权值的边组成的回路。 本章给出的求解最短路径的算法不仅适用于带本章给出的求解最短路径的算法不仅适用于带 权有向图，对带权无向图也可以适用。因为带权权有向图，对带权无向图也可以适用。因为带权 无向图可以看作是有往返二重边的有向图，只要无向图可以看作是有往返二重边的有向图，只要 在顶点在顶点v v i i 与与v v j j 之间存在无向边之间存在无向边( (v v i i , , v v j j ) )，就可以看成，就可以看成 是在这两个顶点之间存在权值相同的两条有向边是在这两个顶点之间存在权值相同的两条有向边 和和 。 用边表示活动的网络(AOE网络) v如果在无有向环的带权有向图中 用有向边表示一个工程中的各项活动 (Activity) 用边上的权值表示活动的持续时间 (Duration) 用顶点表示事件(Event) v则这样的有向图叫做用边表示活动的网络 ，简称AOE (Activity On Edges)网络。 vAOE网络在某些工程估算方面非常有用。 例如，可以使人们了解： (1) 完成整个工程至少需要多少时间(假设 网络中没有环)? (2) 为缩短完成工程所需的时间, 应当加快 哪些活动? v在AOE网络中, 有些活动顺序进行，有些 活动并行进行。 v从源点到各个顶点，以至从源点到汇点的 有向路径可能不止一条。这些路径的长度 也可能不同。完成不同路径的活动所需的 时间虽然不同，但只有各条路径上所有活 动都完成了，整个工程才算完成。 v因此，完成整个工程所需的时间取决于从 源点到汇点的最长路径长度，即在这条路 径上所有活动的持续时间之和。这条路径 长度最长的路径就叫做关键路径(Critical Path)。 v要找出关键路径，必须找出关键活动，即 不按期完成就会影响整个工程完成的活动 。 v关键路径上的所有活动都是关键活动。因 此，只要找到了关键活动，就可以找到 关键路径关键路径 定义几个与计算关键活动有关的量： 事件Vi 的最早可能开始时间Ve(i) 是从源点V0 到顶点Vi 的最长路径长度。 事件Vi 的最迟允许开始时间Vli 是在保证汇点Vn-1 在Ven-1 时刻完成的 前提下，事件Vi 的允许的最迟开始时间。 活动ak 的最早可能开始时间 ek 设活动ak 在边上，则ek是从源 点V0到顶点Vi 的最长路径长度。因此, ek = Vei。 活动ak 的最迟允许开始时间 lk lk是在不会引起时间延误的前提下，该 活动允许的最迟开始时间。 lk = Vlj - dur()。 其中，dur()是完成ak 所需的时间。 时间余量 lk - ek 表示活动ak 的最早可能开始时间和最迟允 许开始时间的时间余量。lk = ek表示 活动ak 是没有时间余量的关键活动。 v为找出关键活动, 需要求各个活动的 ek 与 lk，以判别是否 lk = ek. v为求得ek与 lk，需要先求得从源点V0 到各个顶点Vi 的 Vei 和 Vli。 v求Vei的递推公式 从Ve0 = 0开始，向前递推 S2, i = 1, 2, , n-1 其中, S2是所有指向顶点Vi 的有向边的集合。 从Vln-1 = Ven-1开始，反向递推 S1, i = n-2, n-3, , 0 其中, S1是所有从顶点Vi 发出的有向边的集合。 v这两个递推公式的计算必须分别在拓扑有 序及逆拓扑有序的前提下进行。 v设活动ak (k = 1, 2, , e)在带权有向边 上, 它的持续时间用dur () 表 示，则有 ek = Vei； lk = Vlj - dur()；k = 1, 2, , e。这样就得到计算关键路径的算法。 v计算关键路径时，可以一边进行拓扑排序 一边计算各顶点的Vei。为了简化算法， 假定在求关键路径之前已经对各顶点实现 了拓扑排序，并按拓扑有序的顺序对各顶 点重新进行了编号。算法在求Vei, i=0