本文目录
- 二分图匹配问题
- 二分图匹配，匈牙利算法原理与实现
- 二分图最大匹配Matlab程序（在线等，感激不尽！）
- 离散数学中二分图和匹配问题
- 二分图匹配的匹配
- 谁能仔细讲解一下二分图匹配(pascal)
- 二分图多重最大匹配
二分图匹配问题
g:arrayof boolean;
y:arrayof boolean;
link:arrayof longint;
function find(v:longint):boolean;
var i:longint;
begin
for i:=1 to m do
if g) then
begin
y:=true;
if (link) then
begin
link:=v;
find:=true;
exit;
end;
end;
find:=false;
end;
begin
//read the graph into array g
for i:=1 to n do
begin
fillchar(y,sizeof(y),0);
if find(i) then inc(ans);
end;
我用C++的,这个PASCAL程序是别处的
其中n,m分别为2部图两边节点的个数,两边的节点分别用1..n,1..m编号
g=true表示x,y两个点之间有边相连
link记录的是当前与y节点相连的x节点
y记录的是y中的i节点是否被访问过.
算法的思路是不停的找增广轨,并增加匹配的个数,增广轨顾名思义是指一条可以使匹配数变多的路径,在匹配问题中,增广轨的表现形式是一条“交错轨“,也就是说这条由图的边组成的路径,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被选择过.这样交错进行,显然他有奇数条边.那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推.也就是将所有的边进行“反色“,容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对.另外,单独的一条连接两个未匹配点的边显然也是交错轨.可以证明,当不能再找到增广轨时,就得到了一个最大匹配.这也就是匈牙利算法的思路.
代码中find(i)就是寻找有没有从x点i开始的增广轨,如果有就进行上述操作,代码是递归的,所以看起来不是很显然,画个图试试就很清楚了.
P.S. 我比较笨,以前学习匈牙利算法时花了不少时间来理解这段代码的意思,希望楼主能很快理解,所以用很贫乏和不规范的语言描述了一下算法.希望能满意
二分图匹配，匈牙利算法原理与实现
中国如今男女比例严重失衡，2021年预计将有9200万单身贵族。为了帮助解决这个社会性问题，提升整体人民的幸福感，小K打算投身到这份伟大的事业中。
“ 几何思维 ”婚恋所，用最科学的方法，帮你脱单。通过概率论寻找最佳匹配对象，再通过微积分精确计算好感上升曲线，最后用数值分析无限逼近对方的理想型。最可怕的是，还包邮呢亲，关注一波了解一下？
上班第一天，老板给了小K一份单身男女好感的数据资料。如下图，连线表示双方互有好感，可以尝试处对象。
突然遇到了一个问题，那怎么才能进行最大的匹配，创造整体人民最大的幸福感呢，当然也可以顺便拿最多的中介费啦。
很多时候不是你比别人差，而是你执行力不够，在犹豫中丧失机会。
大家就先行动起来吧。
快看，男1号选手在小K的鼓励(怂恿)下，率先对女1号发起了进攻。在离失败只有0.01公分的时候，他竟然奇迹般的完成反杀，没错，他成功啦，这种高超的技巧，娴熟的手法简直如同教科书一般，值得在座的每个同学深入研究反复琢磨啊。
男2号选手也不甘落后，也对女2号选手发起了进攻，没错，又一次成功啦。
男3号选手：我勒个去，我上我也行啊。于是也对自己心动的女1号发起了进攻，毫无意外，他阵亡了。。。
中间彩蛋。
男3号不甘心，原地复活，想再战一回。在一个地方跌倒，咱们就换一个地方再跌。。。
于是对女2号发起了进攻。
几经波折。
男3号终于也成为了有牵绊的男人，不论未来有多久，只在乎曾经拥有过。
男4一看：这也没我啥事儿了啊。
以上的过程其实就是经典的 匈牙利算法 ，求解二分图的最大匹配问题。
二分图
定义：设G=(V,E)是一个无向图，顶点集V可分割为两个互不相交的子集X，Y，并且图中每条边关联的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。
判断是否为二分图的充要条件：G至少有两个顶点,且其所有回路的长度均为偶数。
判断方法：染色法
可用bfs或者dfs。
匹配
在二分图G的子图M中，M的边集E中的任意两条边都不依附于同一个顶点，则称M是一个 匹配 。
饱和点
匹配M的边集所关联的点为 饱和点 ，否则为 非饱和点 。如上图：
交错路
定义：图G的一条路径，且路径中的边在属于M和不属于M中交替出现。
增广路(非网络流中的定义)
定义：一条交错路，且该交错路的起点和终点都为匹配M的非饱和点。
如上图，交错路1是增广路；交错路2不是增广路，因为终点 X1 不是非饱和点。
由增广路推出以下结论：
匈牙利算法核心思想：
变量定义及初始化
初始化
递归寻找增广路
遍历所有点
测试数据
二分图最大匹配Matlab程序（在线等，感激不尽！）
第一个问题比较简单，这里懒得对着你的图片敲数据，用随机数代替
long=100;
A=0.1*rand(long,1);
B=0.15*rand(long,1);
=meshgrid(A,B);
gg=0.5017*AA-0.65*BB;
g=gg》=-0.03&gg《=0.03; %这就是gij矩阵，相当于二分图的连接矩阵
= maxnum(g);%第二个问题就是求二分图的最大匹配问题，这里
%调用了一个自己写maxnum函数，返回num就是最大值，h是hij(不唯一）
以下是maxnum.m的内容，用的是匈牙利算法
其中还用了一个递归的incpath函数，寻找增广路径
function = maxnum(g)
s=size(g);
global G_h;%矩阵hij记录选中
global G_g;%矩阵gij记录匹配
global G_v;%记录当前一次路径访问过的节点
G_h=false(s);%矩阵hij初始为空
G_g=g;%矩阵gij就是传递进来的参数g
for i=1:s(1)
G_v=fa
