《二分图匹配及其应用讲解》由会员分享，可在线阅读，更多相关《二分图匹配及其应用讲解（40页珍藏版）》请在金锄头文库上搜索。
1、二分图匹配及其应用 例题1 棋盘的覆盖 n一张普通的国际象棋棋盘 n8*8 = 64 格中被删除了一些格子 n使用1*2 的多米诺骨牌进行覆盖 n求最大覆盖的格数和方案 例题1 思路 n染色 n建图 n性质 n最大匹配和完美匹配 基本概念 n点集分为互补的两个集合 基本定理 n判定定理： n一个图为二分图的充要条件是其所有回路均 为偶数长。 q如何判断一张图是否为二分图，并对节点进 行正确的划分呢？ 二分图的判断问题 n染色法 n将节点用黑白两种颜色染 n实现：深度优先搜索 二分图判断问题解答1 nvar n visited: array1.100 of integer; n data: ar
2、ray1.1001.100 of integer; n n: integer; n success: boolean; 二分图判断问题解答2 procedure 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
3、 dfs(i, 3-color); end; 二分图判断问题解答3 function 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每 个数字出现一
4、次且仅一次，每列都有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如何找？算法选择？ 增广路和
5、匈牙利算法 实例1 增广路和匈牙利算法 实例2 找增广路的两种办法 n广度优先搜索 n深度优先搜索 广度优先算法程序 nvar ndata: array1.100,1.100 of integer; nmatch1,match2: array1.100 of integer; nn：integer; 广度优先算法程序 nfunction bmatch:integer; nvar n i,r:integer; nbegin n for i:=1 to n do n r := r + find(i); n bmatch := r; nend; 广度优先算法程序 nfunction find(s:i
6、nteger):integer; nvar n i,j, d,t, qh,ql:integer; n father2,queue1:array1.100 of integer; nbegin n 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:=queue1
7、qh; 广度优先算法程序 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; 深度优先算法程序 var data: array1.100,1.100 of integer; match1,match2: array1.100 of integer; int n; use
8、d2: 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 begi
9、n 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已知导弹依次飞来的高度，计算 这套
10、系统最多能拦截 多少导弹，和如果要拦截所有导弹最少要配备多少套 这种导弹拦截 系统。 例题4 拦截导弹 标准解法 n动态规划 n贪心法 例题4 拦截导弹 匹配解法 n将特殊情况一般化 n建图 n化为最小路径覆盖 最小路径覆盖 n转换 n拆分顶点 n化为二分图匹配 例题5 伞兵降落 n某个城市的街道图是一个有向无环图， 现在伞兵可在图中任意一个节点降落， 并负责清扫后面他走过的街道。 n任意一条街道必须有一个伞兵清扫，并 不允许其他伞兵经过 n求最少需要的伞兵数 例题6 旅馆预订 n一个旅馆接到n张定单，表示要从第s天 开始入住，从第e天结束并离开， n求最少需要的房间数目，以满足所有定 单的要
11、求。 例题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二分图的最大匹配 最小边覆盖=最大匹配
