二分图匹配及其应用概要.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《二分图匹配及其应用概要.ppt》由会员分享,可在线阅读,更多相关《二分图匹配及其应用概要.ppt(40页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、二分图匹配及其应用例题1 棋盘的覆盖n一张普通的国际象棋棋盘n8*8=64 格中被删除了一些格子n使用1*2 的多米诺骨牌进行覆盖n求最大覆盖的格数和方案例题1 思路n染色n建图n性质n最大匹配和完美匹配基本概念n点集分为互补的两个集合基本定理n判定定理:判定定理:n一个图为二分图的充要条件是其所有回路均一个图为二分图的充要条件是其所有回路均为偶数长。为偶数长。q如何判断一张图是否为二分图,并对节点进如何判断一张图是否为二分图,并对节点进行正确的划分呢?行正确的划分呢?二分图的判断问题n染色法n将节点用黑白两种颜色染n实现:深度优先搜索二分图判断问题解答1nvarn visited:array
2、1.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
3、 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每个数字出现一
4、次且仅一次例题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深度优先搜索广度优
5、先算法程序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 i
6、nteger;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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二分 匹配 及其 应用 概要
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内