第10章 网络流与二分图.ppt

2020 2 26 第10章网络流与二分图 第12 13讲 黄丽韶ly sa 2020 2 26 目录 10 1网络与流10 1 1网络流基本概念10 1 2增广路算法10 1 3求最大流的标号法 Ford Fulkerson方法10 2二分图匹配10 2 1二分图与匹配10 2 2二分图最大匹配问题网络流算法10 2 3二分图最大匹配问题的匈牙利算法10 2 4最小点覆盖与最小路径覆盖10 2 5二分图最优匹配 2020 2 26 问题引入 如下图 经济区域中城市s和城市t间的物流运输网络 记v1为s v9为t 每一条有向边 vi vj 表示从vi到vj的运输线 货物经这条运输线由vi运送到vj 线旁的数字表示线的最大运输能力 货物经过网络从城市s运送到城市t 现要求制定一个运输方案 使从s运送到t的货物最多 物流运输网络图 2020 2 26 一种运输方案 2020 2 26 运输网络的特点 1 实际运输量不能为负 2 每条有向边上的实际运输量不能大于该边上的容量 3 除了起点s和终点t外 对于其他顶点来说 所有指向vi的线上的运输量的和 应该等于所有从vi出发的有向边上的运输量的和 2020 2 26 10 1网络与流 2020 2 26 10 1 1网络流基本概念 1 网络设G是一个简单有向图 G V E V v1 v2 v3 vn 在V中指定一个顶点s 称为源 或称源点或发点 取另一个顶点t 称为汇 或称汇点或收点 对于有向图G的每一条有向边 vi vj E 对应的有一个值cij 0 称为该有向边上的容量 通常把这样的有向图G叫做一个网络 记为G V E C 其中C是网络的容量函数 2 网络流网络上的流 是指定义在有向边集合E上的一个函数F fij vi vj E 并称fij为边 vi vj 上的流量 2020 2 26 10 1 1网络流基本概念 3 可行流容量限制条件 对于每一条边 vi vj E 0 fij cij 平衡条件 对于每个中间点vi vi的流出量 vi的流入量 V F 可行流的流量 2020 2 26 10 1 1网络流基本概念 4 最大流一个可行流F fij 使其流量V F 达到最大 并且满足 vi vj E 0 fij cij 2020 2 26 10 1 1网络流基本概念 5 残流网络边 vi vj E的残流容量为cij fij 表示通过该边能调整的最大流容量 给定网络G V E C 及G的一个可行流F fij G的残流网络G 是通过下列方法得到的网络G V E C 设 vi vj E 当cij fij时 G 中有对应的边 vi vj E 边上的流量是c ij cij fij 当fij 0时 G 中还有一条边 vj vi E 边 vj vi 上的流量是c ij fij 2020 2 26 10 1 2增广路算法 1 向前边与后向边对于网络G V E C 若给一个可行流F fij 则把网络中使fij cij的有向边称为饱和边 使fij 的边称为非零流边 若P是网络中联结源点s和汇点t的一条路 定义路的方向是从s到t 则路上的边被分成两类 一类是边的方向与路的方向一致 叫做向前边 向前边的全体记为P 另一类边与路的方向相反 叫做向后边 向后边的全体记为P 2020 2 26 原问题的算法设计 2 增广路定义 设F是一个可行流 P是从s到t的一条路 若P满足下列条件 1 在P的所有向前边 vi vj 上 0 fij cij 即P 中的每一条边是非饱和边 2 在P的所有向后边 vi vj 上 0 fij cij 即P 中的每一条边是非零流边 2020 2 26 3 增广路算法思想与增广路定理 对一条增广路P 将可行流F改进成一个值更大的流F 基本思想 1 不属于增广路P的边 vi vj 上的流量一概不变 即f ij fij 2 增广路P上的所有边 vi vj 上的流量按下述规则调整 在P 中的向前边 vi vj 上 f ij fij 在P 中的向后边 vi vj 上 f ij fij 2020 2 26 实例 调整后的运送方案 2020 2 26 增广路定理 设F是网络G的一个流 如果不存在从s到t关于F的增广路P 那么F一定是最大流 2020 2 26 增广路方法求最大流的基本流程 2020 2 26 残流网络 如果残流网络G 中没有从s到t的增广路 那么当前流为最大流 反之 如果当前流G不为最大流 则G 一定有增广路 2020 2 26 10 1 3求最大流的标号法 Ford Fulkerson方法 从一个可行流出发 若网络中没有给定可行流F 则可以设F为平凡的零流 经过标号过程和调整过程 可以求出网络中的最大流 标号过程 网络中的顶点逐渐进行标号 顶点分为两类 标号顶点 已检查和未检查两种 未标号顶点 每个标号顶点v的标号由两个部分 u d 组成 标号的第一部分u指明它的标号是从哪一个顶点得到的 以便找出增广路 标号的第二部分d是为确定增广路的调整量 用的 2020 2 26 标号步骤 先将s标上 0 标号 或称标记 取一个已标号而未检查的顶点vi 对一切与vi相连而未标号顶点vj 1 若在边 vi vj 上 fij 则给vj标号为 vi d vj 这里d vj Min d vi fji 这时顶点vj成为标号而未检查的顶点 2020 2 26 标号步骤 在vi的全部相邻顶点都已标号后 vi成为已检查过的顶点 于是 重复上述步骤 一旦t被标上号 表明得到一条从s到t的增广路P 转入调整过程 若所有标号都是已检查过的 而标号过程无法进行时 则算法结束 这时的可行流即为最大流 2020 2 26 调整过程 采用 逆向追踪 的方法 从t开始 利用标号点的第一个分量得到前趋顶点 逐条边地寻找 得到一条增广路P 并以t标号的第二个分量d t 作为改进量 改进路径P上的流量 2020 2 26 10 2二分图匹配 11 2 1问题一个公司有n个工作空缺 每项工作需要具有一定资格的人承担 今有m个人申请这n项工作 如果一个工作空缺只能由一名满足该工作资格的人承担 那么在这m个申请人中能够承担工作的最大个数是多少 2020 2 26 求职者关系图 申请者的集合为X x1 x2 xm 工作的集合为Y y1 y2 yn X与Y关系图 2020 2 26 10 2 2二分图与匹配 二分图G 所有的顶点分成两个集合X和Y 其中X或Y在各自集合中的任意两个点都不相连 而在X和Y中的顶点可以构成边 2020 2 26 匹配概念 二分图G的匹配M 边集E的子集M 具有性质 M中没有两条边有公共顶点 最大匹配 就是在G的所有匹配中具有最多边数的匹配 完美匹配 如果所有点都在匹配边上 称这个最大匹配是完美匹配 2020 2 26 10 2 3二分图最大匹配问题网络流算法 给定二分图G X E Y 构造与G对应的网络G 构造方法如下 1 增加一个源点s 一个汇点t 2 从s向X的每个顶点引一条有向边 从Y的每个顶点向t引一条有向边 3 将原图G的每条边改为从X指向Y的有向边 4 置所有边的容量为1 求网络F的最大流 最大流值是对应于二分图G的最大匹配边数 2020 2 26 10 2 4二分图最大匹配问题的匈牙利算法 令G X E Y 是一个二分图 其中x x1 x2 xm Y y1 y2 yn 令M为G的任意匹配 S1 将X的所有不与M的边关联的顶点标上 并称所有的顶点为未扫描的 转到S2 S2 如果在上一步没有新的标记加到X的顶点上 那么停止 否则 转S3 S3 当X中存在被标记但未被扫描的顶点时 选择一个被标记但未被扫描的X的顶点 比如xi 用 xi 标记Y的所有顶点 这些顶点被不属于M且尚未标记的边连到xi 现在顶点xi是被扫描的 如果不存在被标记但未被扫描的顶点 那么转S4 2020 2 26 匈牙利算法 续 S4 如果在步骤S3没有新的标记被标记到Y的顶点上 那么停止 否则 转S5 S5 当存在y被标记但未被扫描的顶点时 选择Y的一个被标记但未被扫描的顶点 比如yj 用 yj 标记X的顶点 这些顶点被属于M且尚未标记的边连到yj 现在 顶点yj是被扫描的 如果不存在被标记但未被扫描的顶点 那么转S2 然后进行匹配关系扩展 如果无法进行扩展 那么M就是最大匹配 结束 否则转S1 2020 2 26 匹配关系扩展过程 如果Y中所有被标记的顶点都是M的某条边的端点 那么M已是一个最大匹配 结束查找 如果Y的顶点yj被标记 且没有一条以yj为端点的边是M的匹配边 那么需要进行增广路径的扩展 即通过取反操作实现扩展 2020 2 26 最大匹配与增广路调整举例 2020 2 26 第一轮操作 图10 10第一轮操作 2020 2 26 第二轮操作 图10 11第二轮操作 2020 2 26 第三轮操作 图10 12第三轮操作 2020 2 26 关于增广路的三个结论 1 P的路径长度必定为奇数 第一条边和最后一条边都不属于M 2 P经过取反操作可以得到一个更大的匹配M 3 M为G的最大匹配当且仅当不存在相对于M的增广路径 2020 2 26 匈牙利算法算法框架 voidhungary 匈牙利算法过程for i 1 i n i if DFS i 如果从i的对应项出发有可增广路匹配数 那么匹配数加1 输出匹配数 2020 2 26 搜索过程 boolDFS intk 寻找从k出发的增广路while j与k邻接 if j不在增广路上 把j加入增广路 if j没有被标记的边连到k或者与j相连的顶点x出发有可增广路 则修改j的对应项为k 返回true 如果从k的对应项出发没有可增广路 那么返回false 2020 2 26 10 2 4最小点覆盖与最小路径覆盖 几个概念点覆盖定义1 给定图G V E V 是V的一个子集 若对于G的任何边e 有顶点v V 使得v与e相关联 则称v覆盖e 并称V 为G的点覆盖集或简称点覆盖 设V 是G的点覆盖 若V 的任何真子集都不是G的点覆盖 则称V 是极小点覆盖 G中顶点个数最少的点覆盖称为G的最小点覆盖 其顶点个数称为点覆盖数 2020 2 26 几个概念 边覆盖定义2 给定图G V E E 是E的一个非空子集 若对于G的任何顶点v 都有边e E 使得e与v相关联 则称e覆盖v 并称E 为G的边覆盖集或简称边覆盖 设E 是G的边覆盖 若E 的任何真子集都不是G的边覆盖 则称E 是极小边覆盖 G中边数最少的边覆盖称为G的最小边覆盖 其顶点个数称为边覆盖数 2020 2 26 几个概念 独立集定义3给定图G V E V 是V的一个非空子集 若V 的任何两个顶点u v都不是同一条边的两个端点 则称V 是G的一个空子图 设V 是G的空子图 若V 任意增加一个G中不在V 中的点后都不是空子图 则称V 是G的独立集 G中所含顶点数最多的独立集V 称为G的最大独立集 2020 2 26 几个概念 支配集定义4设G V E 是无向简单图 S是V的一个非空子集 若对于不在S中的G的点u u与S里至少一个顶点v相关联 则称S是图G的支配集 设S是图G的支配集 若S的任何真子集都不是G的支配集 则称S为图G的极小支配集 G中含顶点数最少的支配集S 称为G的最小支配集 其顶点个数 S 称为图G的支配数 2020 2 26 举例 无向简单图最小支配集 图11 13无向简单图最小支配集 2020 2 26 几个概念 最大团定义5给定图G V E V 是V的一个子集 若V 的任意两个顶点都相邻 则称V 是G的一个完全子图 若V 不包含在G的更大的完全子图中 则称V 是G的一个团 G中所含顶点数最多的团称为G的最大团 补图定义6对于任一无向图G V E 其补图G V E 定义为 u v E 当且仅当 u v E 2020 2 26 几个概念 路径覆盖定义7在一个有向图G中 如果在图G中有一些路经 使之覆盖了图G中的所有顶点 且任何一个顶点有且只有一条路径与之关联 那么这些路径称为G的一个路径覆盖 最小路径覆盖就是找出最小条数的路径 使之成为G的一个路径覆盖 2020 2 26 有用的结论 1 团与独立集的关系 设G 为无向图G的补图 U是G的完全子图 当且仅当 U是G 的空子图 U是G的团 当且仅当 U是G 的独立集 U是G的最大团 当且仅当 U是G 的最大独立集 2 独立集与点覆盖的关系 设无向图G V E 中无孤立点 U是G的独立集 当且仅当 V U是G的极小点覆盖 U是G的最大独立集 当且仅当 V U是G的最小点覆盖 2020 2 26 有用的结论 3 独立集合和支配集的关系 设G是无孤立顶点的图 则G的极大独立集必为极小支配集 其逆不真 4 二分图的最大独立集与最小边覆盖的关系 如果G V E 是连通的二分图 那么G的最大独立集点数D等于G的最小边覆盖EC数 即D EC 5 二分图的最大独立集与最大匹配的关系 二分图G的最大独立集点数D等于G的顶点数 V 减去G的最大匹配数m 即D m V 2020 2 26 有用的结论 6 二分图的最大匹配数与最小边覆盖的关系 如果G V E 是连通的二分图 那么G的最大匹配数m与G的最小边覆盖数EC之和等于G的顶点集 m EC V 7 二分图的最大匹配与最小点覆盖的关系K nig定理 一个二分图G中的最大匹配数m等于G的最小点覆盖数C 即m C 8 无圈有向图的路径覆盖与二分图匹配的关系 构建与G对应的一个二分图G G的最小路径覆盖数 V G的最大匹配数m 2020 2 26 举例 无圈有向图与对应的二分图 2020 2 26 10 2 5二分图最优匹配 给定一个二分图G 其中边 x y 有权w x y 现在要找一个从X到Y具有最大权和的匹配M 这就是二分图最优匹配问题 2020 2 26 二分图最优匹配问题的数学描述 记X x1 x2 xn Y y1