二分图匹配及其应用概要.ppt

二分图匹配及其应用例题1 棋盘的覆盖n一张普通的国际象棋棋盘n8*8=64 格中被删除了一些格子n使用1*2 的多米诺骨牌进行覆盖n求最大覆盖的格数和方案例题1 思路n染色n建图n性质n最大匹配和完美匹配基本概念n点集分为互补的两个集合基本定理n判定定理：判定定理：n一个图为二分图的充要条件是其所有回路均一个图为二分图的充要条件是其所有回路均为偶数长。为偶数长。q如何判断一张图是否为二分图，并对节点进如何判断一张图是否为二分图，并对节点进行正确的划分呢？行正确的划分呢？二分图的判断问题n染色法n将节点用黑白两种颜色染n实现：深度优先搜索二分图判断问题解答1nvarn visited:array1.100 of integer;n data:array1.1001.100 of integer;n n:integer;n success:boolean;二分图判断问题解答2procedure dfs(which,color:integer);var i:integer;begin if not success then exit;if visitedwhich 0 then begin if visitedwhich color then success=false;exit;end;visitedwhich:=color;for i:=1 to n do if datawhichi 0 then dfs(i,3-color);end;二分图判断问题解答3function judge:boolean;var i:integer;begin success:=true;for i:=1 to n do if visitedi=0 then dfs(i,1);judge:=success;end.HALL 定理n二分图，存在完美匹配的充分必要条件是，对于任意一个顶点集合的子集A，它的相邻点构成的邻集X(A)，都满足以下条件：HALL 定理 证明n必要性n充分性例题2 HALL定理的应用n构造N*N的矩阵，使得每行都有1到n每个数字出现一次且仅一次，每列都有1到n每个数字出现一次且仅一次例题2 思路n每次构造一行n循环n次构造n行n建图n如何证明？例题3 思考题nN为奇数，M=(N-1)/2，由组合数学知:n因为M+M+1=N例题3 思考题现将所有的从n个数里取m个数的组合构成一个集合A将所有的从n个数里取m+1个数的组合构成另一个集合B这两个集合是否存在着一一映射的关系？使得A中的每个元素a都对应到B中的元素b，且a为b的一个子集？例题3 思考题解答n建图n找完美匹配n如何证明？增广路和匈牙利算法n增广路（交错轨）的概念n匈牙利算法：找增广路n如何找？算法选择？增广路和匈牙利算法 实例1增广路和匈牙利算法 实例2找增广路的两种办法n广度优先搜索n深度优先搜索广度优先算法程序nvarndata:array1.100,1.100 of integer;nmatch1,match2:array1.100 of integer;nn：integer;广度优先算法程序nfunction bmatch:integer;nvarn i,r:integer;nbeginn for i:=1 to n don r:=r+find(i);n bmatch:=r;nend;广度优先算法程序nfunction find(s:integer):integer;nvarn i,j,d,t,qh,ql:integer;n father2,queue1:array1.100 of integer;nbeginn fillchar(father2,sizeof(father2),0);n queue11:=s;n qh:=1;n ql:=1;广度优先算法程序while(qh 0)or(dataqueue1qhi=0)then continue;if(match2i0)then begin inc(ql);queue1ql:=match2i;father2i:=queue1qh;广度优先算法程序 end else begin j:=queueqh;while(true)do begin t:=match1j;match1j:=i;match2i:=j;if(t=0)then break;i:=t;j:=father2t;广度优先算法程序 end;find:=1;Exit;end;end;end;find:=0;end;深度优先算法程序vardata:array1.100,1.100 of integer;match1,match2:array1.100 of integer;int n;used2:array1.100 of integer;深度优先算法程序function bmatch:integer;var i,r:integer;begin for i:=1 to n do begin fillchar(used2,sizeof(used2),0);r:=r+find(i);end;bmatch:=r;end;深度优先算法程序function find(s:integer):integer;var i:integer;begin for i:=1 to n do if(datasi 0)and(used2i=0)then begin used2i:=1;if(match2i=0)or find(match2i)then begin match2i:=s;match1s:=i;find:=1;exit;end;end;find:=0;end;二分图与网络流的关系 例题4 拦截导弹n某国为了防御敌国的导弹袭击，发展出一种导弹拦截某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统系统。但是这种导弹拦截系统 有一个缺陷：虽然它的有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高弹都不能高 于前一发的高度。某天，雷达捕捉到敌国于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于只有一套系统，因此有可能不能拦的导弹来袭。由于只有一套系统，因此有可能不能拦截所有的导弹。截所有的导弹。n已知导弹依次飞来的高度，计算已知导弹依次飞来的高度，计算 这套系统最多能拦截这套系统最多能拦截多少导弹，和如果要拦截所有导弹最少要配备多少套多少导弹，和如果要拦截所有导弹最少要配备多少套这种导弹拦截这种导弹拦截 系统。系统。例题4 拦截导弹 标准解法n动态规划n贪心法例题4 拦截导弹 匹配解法n将特殊情况一般化n建图n化为最小路径覆盖最小路径覆盖n转换转换n拆分顶点拆分顶点n化为二分图匹配化为二分图匹配例题5 伞兵降落n某个城市的街道图是一个有向无环图，某个城市的街道图是一个有向无环图，现在伞兵可在图中任意一个节点降落，现在伞兵可在图中任意一个节点降落，并负责清扫后面他走过的街道。并负责清扫后面他走过的街道。n任意一条街道必须有一个伞兵清扫，并任意一条街道必须有一个伞兵清扫，并不允许其他伞兵经过不允许其他伞兵经过n求最少需要的伞兵数求最少需要的伞兵数例题6 旅馆预订n一个旅馆接到一个旅馆接到n张定单，表示要从第张定单，表示要从第s天天开始入住，从第开始入住，从第e天结束并离开，天结束并离开，n求最少需要的房间数目，以满足所有定求最少需要的房间数目，以满足所有定单的要求。单的要求。例题7 火星探测器n火星探测器要在一个火星探测器要在一个n*n的网格内采集的网格内采集岩石标本，它从岩石标本，它从(1,1)出发，到达出发，到达(n,n)n有些网格内是标本，探测器第一次经过有些网格内是标本，探测器第一次经过时将得到此标本时将得到此标本n有些网格内是障碍物，不能通过有些网格内是障碍物，不能通过n探测器只能走最短路线探测器只能走最短路线例题7 火星探测器 问题n问题问题1.只有一个探测器，如何走采集到只有一个探测器，如何走采集到最多的标本？最多的标本？n问题问题2.至少要几个探测器才能收集完这至少要几个探测器才能收集完这里所有的标本？里所有的标本？n问题问题3.若只有若只有k个探测器，最多能收集到个探测器，最多能收集到几个标本？几个标本？例题8 打猎n猎人要在猎人要在n*n的格子里打鸟，他可以在的格子里打鸟，他可以在某一行中打一枪，这样此行中的所有鸟某一行中打一枪，这样此行中的所有鸟都被打掉，也可以在某一列中打，这样都被打掉，也可以在某一列中打，这样此列中的所有鸟都打掉此列中的所有鸟都打掉n至少打几枪，才能打光所有的鸟？至少打几枪，才能打光所有的鸟？例题8 打猎 解答n建图建图n二分图的最小边覆盖二分图的最小边覆盖n转化转化n二分图的最大匹配二分图的最大匹配最小边覆盖最小边覆盖=最大匹配最大匹配