二分图匹配问题（二分图匹配问题）_匹配_节点_增广

本文目录

• 二分图匹配问题
• 二分图匹配，匈牙利算法原理与实现
• 二分图最大匹配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=false(1,s(2));%每次初始化径访问过的节点为空
    incpath(i);%从Ai开始寻找增广路径
end
h=G_h;num=sum(h(:));%输出最大匹配数，和匹配矩阵h
clear global ’G_h’;clear global ’G_g’;
end
function OK = incpath(i)%从Ai开始
global G_h;global G_g;global G_v;OK=false;
j=find(~G_h(i,:)&G_g(i,:)&~G_v,1);%寻找合条件的Bj
if isempty(j),return;end%找不到返回false
G_v(j)=true;%找到了，标记Bj为以访问节点
ii=find(G_h(:,j));%寻找Bj在原来匹配中
if isempty(ii)%如果不在原匹配中
G_h(i,j)=true;OK=true;return;end%找到增广路径末端，返回true
ok=incpath(ii);%如果在原来的匹配中，根据匹配对应的Aii递归调用incpath寻找
if ok %如果递归寻找返回成功
G_h(i,j)=~G_h(i,j);G_h(ii,j)=~G_h(ii,j);OK=true;return;end%路径反色返回true
end

离散数学中二分图和匹配问题

以V1＝｛L1,L2,L3,L4,L5,L6｝和V2＝｛G1,G2,G3,G4,G5,G6｝为顶点组，若Li和Gj互为结婚对象，则在两个顶点之间添加一条边，如此构造出一个二分图（图一）.V1中任意k个点（k＝1,2,...,6）至少与V2中k个点相邻，V1和V2中顶点个数相同，所以存在从V1到V2的完美匹配.图一改画为图二，图二中两部分皆有2个完美匹配，由此得图一的完美匹配：（1）L1－G1，L2－G3，L3－G4，L4－G2，L5－G6，L6－G5（2）L1－G4，L2－G3，L3－G1，L4－G2，L5－G6，L6－G5（3）L1－G1，L2－G5，L3－G4，L4－G6，L5－G3，L6－G2（4）L1－G4，L2－G5，L3－G1，L4－G6，L5－G3，L6－G2

二分图匹配的匹配

设M是图G=(V,E)的一个匹配，vi∈V。若vi与M中的边相关联，则称vi是M饱和点，否则称vi为M非饱和点。　如果G中每个顶点都是M饱和点，则称M为G的完美匹配。　设M是G的一个匹配，P是G的一条链。如果P的边交替地一条是M中的边，一条不是M中的边，则称P为M交错链。类似地，我们可以定义G的交错圈。易知，G的交错圈一定是偶圈。　一条连接两个不同的M非饱和点的M交错链称为M增广链。　两个集合S1与S2的“异或”操作S1⊕S2是指集合S1⊕S2=（S1∩S2）\（S1∪S2）　容易看出，设M是G的匹配，P是G中的M增广链、则M⊕P也是G的匹配，而且　可以证明，G中匹配M是最大匹配当且仅当G中没有M增广链。

谁能仔细讲解一下二分图匹配(pascal)

假设几个位置让几人坐（一些人只能做固定的位置），就是一次又一次的尝试，如果位置上没人，就让他做那个位置，如果匹配过就尝试让原来的座位上的起来去坐其他的位置看能不能坐（这里的问题就和刚才的问题一样了，所以用递归实现），这样一层一层的递归下去，直到所有的尝试完，如果可以匹配就会把原来的位置空出来，第一次的就有位置了，如果不行，那就不行，你先找记到裸的匹配题做做吧！（自从我拿一等候就基本上没碰过了，我没去NOI,凭记忆，不怎么专业，不求给分，希望对你有些帮助）。

二分图多重最大匹配

( 一 ) 如果x部节点只对应一个y部节点,而y部节点可以对应多个x部节点,那么这种匹配可以用 匈牙利算法 来解决。
如何解决?
方法一:
我们知道,传统的二分匹配是一对一匹配的,那么我们把y节点拆点,然后再按照正常的二分匹配就可以了。
这样做的问题是:当y节点很大时,那么拆点耗费的时间会很多!
方法二:
把y部节点的match数组改为二维的,第一维度表示第i个y节点,第二个维度表示这个y节点剩余的容量

G - Escape
题意:
有N(N《100,000)个人要去M(M《10)个星球，每个人只可以去一个星球，一个星球最多容纳Ki个人。请问是否所有人都可以选择自己的星球
题解:

( 二 )如果x部节点可以匹配多个y部节点,y部节点可以同时匹配多个x部节点,那么应该用 网络流 来解决。(因为匈牙利算法无法应对两边都可以选多个这种情况)
怎么建图?
很简单,假设x部节点的容量为capx。然后连接每个x与y直接相连的边,边权为1。
hidoCoder 1393