网站建设yingkagou,app001推广平台官网,google永久免费服务器,wordpress瀑布流图片主题目录 一、介绍 二、染色算法的实现
三、无权二部图中的最大匹配
四、有权二部图中的最大匹配
五、稳定婚配问题 一、介绍
二部图是一种特殊的图#xff0c;其中所有的节点可以被分成两个不相交的集合#xff0c;使得图中的每条边连接的两个节点分属于不同的集合。换句话…目录 一、介绍 二、染色算法的实现
三、无权二部图中的最大匹配
四、有权二部图中的最大匹配
五、稳定婚配问题 一、介绍
二部图是一种特殊的图其中所有的节点可以被分成两个不相交的集合使得图中的每条边连接的两个节点分属于不同的集合。换句话说二部图可以被划分为两个独立的顶点集合且所有边的两个节点分别属于这两个集合。
二部图可以用来描述许多现实世界中的问题例如婚姻稳定性问题、任务分配等。因此判定一个图是否是二部图的问题具有重要的意义。
常用的判定二部图的算法之一是基于深度优先搜索DFS的染色算法 从任意一个节点开始将该节点染成一个颜色例如红色。遍历该节点的所有邻居节点如果某个邻居节点未被染色则将其染成与当前节点不同的颜色例如蓝色。对每个邻居节点再递归地执行步骤2。如果在遍历的过程中遇到某个邻居节点已经被染成与当前节点相同的颜色则说明该图不是二部图。如果成功对图中的所有节点都进行了染色并没有出现步骤4的情况则说明该图是二部图。 如果使用染色算法判定二部图则时间复杂度为 O(VE)其中 V 是节点的数量E 是边的数量。这是因为每个点和每条边仅会进出一次。
另外二部图可以用邻接矩阵或邻接表的形式表示并且可以使用其他算法和技术来解决和优化相关问题例如匹配问题和最大权匹配问题等。
总结来说二部图是一种特殊的图可以被划分为两个独立的节点集合且图中的每条边都连接两个不同的节点集合。判定一个图是否是二部图的染色算法是常用的方法时间复杂度为 O(VE)。 二、染色算法的实现 以下是使用 MATLAB 实现二部图判定算法的例子代码 function isBipartite checkBipartite(graph)numNodes size(graph, 1);colors zeros(numNodes, 1); % 用于存储节点的颜色0表示未染色1和-1表示染成的两种颜色% 从节点1开始进行深度优先搜索if dfs(1, graph, 1, colors)isBipartite true;elseisBipartite false;end
endfunction isBipartite dfs(node, graph, color, colors)% 染色colors(node) color;% 遍历当前节点的邻居节点neighbors find(graph(node, :));for i 1:length(neighbors)neighbor neighbors(i);% 如果邻居节点未染色就染成与当前节点不同的颜色并递归地对邻居节点进行DFSif colors(neighbor) 0if ~dfs(neighbor, graph, -color, colors)isBipartite false;return;end% 如果邻居节点已经染色并且颜色相同于当前节点说明该图不是二部图elseif colors(neighbor) colorisBipartite false;return;endendisBipartite true;
end
使用该代码你需要构建一个邻接矩阵表示的图其中矩阵的每个元素 graph(i, j) 表示节点 i 和节点 j 之间是否有边。如果图是二部图函数 checkBipartite 返回值为 true否则返回值为 false。 例如下面是一个简单的例子 % 构建邻接矩阵表示的图
graph zeros(4); % 创建一个4个节点的图
graph(1, 2) 1; % 添加边
graph(2, 1) 1;
graph(2, 3) 1;
graph(3, 2) 1;
graph(3, 4) 1;
graph(4, 3) 1;% 判定该图是否为二部图
isBipartite checkBipartite(graph);if isBipartitedisp(该图是二部图);
elsedisp(该图不是二部图);
end
在这个例子中构建了一个包括4个节点和3条边的图。经过二部图判定算法的判断输出结果为 “该图是二部图”。你可以根据需要修改邻接矩阵来进行测试。
三、无权二部图中的最大匹配
这个问题其实也可以转化为最大流问题。我们这用贪心的思想步骤如下 初始化一个空的匹配集合对于每一个未匹配的左边节点遍历它的所有可连边右边节点并将其中一个作为该左边节点的匹配如果右边节点已经被匹配则进行以下比较: 如果右边节点已经被匹配但是已匹配节点的度数大于当前节点则更改匹配反之保留原有结果不进行匹配匹配过程结束后返回当前匹配集合。 这个策略的基本思路是从左到右地扫描无权二部图对于每个左端节点选择和它直接相连的一个右端节点进行匹配操作直到无法找到增广路径为止。
此算法的时间复杂度为 O(V^2)其中 V 是二部图的顶点数。缺点也十分明显即可能无法找到最优解
以下是使用 MATLAB 实现贪心算法求解无权二部图最大匹配的例子代码
function maxMatching greedyMatching(graph)numNodes size(graph, 1);maxMatching 0;matching zeros(numNodes, 1); % 存储节点的匹配情况0 表示未匹配非零表示匹配的节点编号for u 1:numNodesif matching(u) 0 % 当前节点未匹配neighbors find(graph(u, :)); % 找到与当前节点相连的节点% 遍历所有可匹配的右边节点for i 1:length(neighbors)v neighbors(i);% 如果节点 v 未匹配直接进行匹配if matching(v) 0matching(v) u;maxMatching maxMatching 1;break;% 如果节点 v 已匹配比较度数后决定是否更新匹配elseif sum(graph(:, v)) sum(graph(:, matching(v)))matching(v) u;break;endendendend
end
四、有权二部图中的最大匹配
其实有权二部图的最大匹配和最小匹配是可以相互转化的下面介绍的算法是来寻找最小匹配的在权值前面加一个负号就可以转换为最大匹配。
对于有权二部图的最大匹配问题我们一般采用匈牙利算法 Hungarian Algorithm先来介绍匈牙利算法。
匈牙利算法Hungarian Algorithm是一种经典的用于解决最大权值二分图最大匹配问题的算法。它由匈牙利数学家Dénes Kőnig于1931年提出后来由Eugene L. Lawler在1961年重新发现并进行了改进。
匈牙利算法的基本思想是通过寻找增广路径来逐步构建最大匹配。增广路径是从一个未匹配的左顶点开始通过交替考察边的方式找到一个未匹配的右顶点再找一个已匹配的左顶点然后继续找未匹配的右顶点如此往复直到找不到延伸路径为止。
算法的具体步骤如下 初始化一个空匹配对每个未匹配的左顶点u使用DFS深度优先搜索或BFS广度优先搜索找到一条增广路径如果找到增广路径则根据增广路径的方向修改匹配即反转路径中已匹配的边和未匹配的边如果找不到增广路径则算法结束当前匹配就是最大匹配。 匈牙利算法的时间复杂度为O(V^3)其中V是二分图中的顶点数。虽然算法在理论上的复杂性较高但实际上被证明是非常有效的特别是在小规模和中等规模的问题上。
下面上代码
function [max_matching, matching] hungarian_algorithm(graph)num_nodes size(graph, 1);matching -1 * ones(1, num_nodes); % 存储节点的匹配情况-1表示未匹配非负整数表示匹配的节点编号function result dfs(node)for neighbor 1:num_nodesif graph(node, neighbor) ~visited(neighbor)visited(neighbor) true;if matching(neighbor) -1 || dfs(matching(neighbor))matching(neighbor) node;result true;return;endendendresult false;endmax_matching 0;for node 1:num_nodesvisited false(1, num_nodes);if dfs(node)max_matching max_matching 1;endendend
你可以通过调用 hungarian_algorithm 函数传入一个邻接矩阵 graph来求解二分图的最大匹配。函数将返回最大匹配的数量 max_matching 和匹配结果 matching其中 matching 是一个向量表示每个左顶点匹配的右顶点编号值为 -1 表示未匹配。
以下是一个使用示例
% 构建二分图邻接矩阵
graph [0 1 0 0 1;1 0 1 1 0;0 1 0 1 0;0 1 1 0 0;1 0 0 0 1];% 使用匈牙利算法求解二分图最大匹配
[max_matching, matching] hungarian_algorithm(graph);% 输出最大匹配结果
fprintf(最大匹配数: %d\n, max_matching);
for i 1:length(matching)if matching(i) ~ -1fprintf(左顶点 %d 与右顶点 %d 匹配\n, i, matching(i));end
end
在上面的例子中我们首先定义了一个二分图的邻接矩阵 graph然后调用 hungarian_algorithm 函数来求解最大匹配。最后我们输出最大匹配的数量和具体的匹配结果。
五、稳定婚配问题
稳定婚配问题Stable Marriage Problem是一种经典的组合优化问题它源自于数学家David Gale和Lloyd Shapley在1962年的研究。该问题描述了如何稳定地匹配两组个体通常是男性和女性之间的偏好。
假设有n个男性和n个女性每个男性可以按照对女性的偏好顺序对女性进行排名同样每个女性也可以对男性进行排名。稳定婚配问题的目标是找到一个婚配情况使得没有两个人可以离开他们当前的配偶并配对在一起形成一对不稳定的夫妻。
稳定婚配问题的一个经典解决方案是Gale-Shapley算法也称为Deferred Acceptance Algorithm。该算法如下 1. 初始化所有人都未婚并且没有被拒绝的配偶。将所有男性列入“自由男性”列表。 2. 选择一个自由男性让他向他在女性排名上最高的未婚女性求婚。 3. 如果该女性是未婚的则接受求婚并将她与该男性匹配。如果该女性已经与另一男性匹配比较该女性对当前男性和已匹配男性的偏好并做出决定如果她更喜欢当前男性则与当前男性解除婚约与新男性匹配如果她更喜欢已匹配男性则拒绝当前男性的求婚。 4. 将未婚的男性从自由男性列表中移除并将被拒绝的求婚男性加入列表中。 5. 重复步骤2-4直到所有男性都完成求婚过程。 6. 返回最终匹配结果。 Gale-Shapley算法保证了找到一个稳定的配对即不存在两人可以配对在一起并不再与原先的配偶在一起的情况。而且根据问题的设定男性会更倾向于提出求婚而女性则会根据自己的喜好作出决定。
稳定婚配问题不仅仅局限于男性和女性之间的匹配它也可以应用于其他场景比如求职者和职位的匹配学生和学校的匹配等。
下面是一个用 MATLAB 实现稳定婚配问题Gale-Shapley算法的简单示例代码
function [matches] stableMatching(menPrefs, womenPrefs)n size(menPrefs, 1);men 1:n;women (n1):(2*n);matches zeros(1, 2*n);proposals zeros(1, 2*n);while any(matches(men) 0)freeMan men(matches(men) 0, 1); % 找到没有匹配的男性for i 1:length(freeMan)man freeMan(i);woman menPrefs(man, proposals(man) 1); % 找到男性当前喜欢的女性proposals(man) proposals(man) 1;if matches(woman) 0 % 女性还没有匹配matches(man) woman;matches(woman) man;elsecurrentMan matches(woman);if find(womenPrefs(woman, :) man) find(womenPrefs(woman, :) currentMan) % 比较女性的偏好matches(man) woman;matches(woman) man;matches(currentMan) 0;endendendend
end
使用示例:
menPrefs [3 1 2; 1 3 2; 2 3 1]; % 男性对女性的偏好每行代表一个男性的偏好顺序
womenPrefs [2 1 3; 2 3 1; 3 1 2]; % 女性对男性的偏好每行代表一个女性的偏好顺序matches stableMatching(menPrefs, womenPrefs);在这个例子中有3个男性和3个女性。 menPrefs 矩阵表示了男性对女性的偏好每行代表一个男性的偏好顺序数字越小表示越喜欢womenPrefs 矩阵表示了女性对男性的偏好每行代表一个女性的偏好顺序。运行代码后将得到匹配结果 matches它是一个包含每个男性和女性配对的向量索引1-3表示男性索引4-6表示女性。
