程序员经验分享-hwhale

最大二部图 (1,n)“匹配”

2023-12-19

我有一个二分图。我正在寻找最大 (1,n) “匹配”，这意味着分区 A 中的每个顶点都有分区 B 中的 n 个关联顶点。

下图显示了图中的最大 (1,3) 匹配。为匹配选择的边缘为红色，未选择的边缘为黑色。

见图http://www.freeimagehosting.net/uploads/9a8df2d97c.gif http://www.freeimagehosting.net/uploads/9a8df2d97c.gif

这与标准的二分匹配问题不同，在标准的二分匹配问题中，每个顶点仅与一个其他顶点相关联，用这种表示法可以将其称为 (1,1) 匹配。

如果匹配基数 (n) 不是强制的，而是一个上限（来自 A 的顶点可以有 0


这是 NP 难问题，是最大独立集问题的简化。对于任何图G您可以（在多项式时间内）构建问题的实例，以便：

  • A 中的顶点代表G
  • A 的每个顶点恰好连接到 B 的 n 个顶点
  • A 的任意两个顶点在 B 中都有公共邻居当且仅当它们在G。为了始终实现这一点，请选择 n=Δ(G)。

现在实例中的最大“匹配”映射回最大独立集G.

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

Graph

matching

最大二部图 (1,n)“匹配” 的相关文章

  • 如何求小于给定数的最大2次方

    我需要找到小于给定数字的最大 2 次幂 我陷入困境 找不到任何解决方案 Code public class MathPow public int largestPowerOf2 int n int res 2 while res lt n

  • 寻找将集合映射到整数的双射函数

    对于任意两个序列 a b 其中 a a1 a2 an 且 b b1 b2 bn 0a b具有相同的元素 而不关心它们的顺序 例如 如果 a 1 1 2 3 b 2 1 3 1 c 3 2 1 3 则 f a f b f a f b 我知道有

  • 在 C++ 中通过引用传递 std 算法谓词

    我正在尝试从 a 中删除元素std list并保留已删除元素的一些统计信息 为此 我使用列表中的remove if 函数 并且我有一个谓词 我想使用这个谓词来收集统计数据 这是谓词的代码 class TestPredicate privat

  • 将字符串中的“奇怪”字符转换为罗马字符

    我需要能够将用户输入仅转换为 a z 罗马字符 不区分大小写 所以 我感兴趣的角色只有26个 然而 用户可以输入他们想要的任何 形式 的字符 西班牙语 n 法语 e 和德语 u 都可以包含用户输入中的重音符号 这些重音符号会被程序删除 我已

  • 0-1背包算法

    以下 0 1 背包问题是否可解 浮动 正值和 浮动 权重 可以是正数或负数 背包的 浮动 容量 gt 0 我平均有 这是一个相对简单的二进制程序 我建议用蛮力进行修剪 如果任何时候你超过了允许的重量 你不需要尝试其他物品的组合 你可以丢弃整

  • 如何仅使用单个数组在 JavaScript 中模拟调用堆栈

    我正在看维基百科页面 https en wikipedia org wiki Call stack在调用堆栈上 并尝试理解这个图像 据我所知 哈哈 const memory memory 0 3 top of stack pointer m

  • 分而治之策略来确定列表中是否有超过 1/3 的相同元素

    我正在使用分治算法来确定列表中是否有超过 1 3 的元素相同 例如 1 2 3 4 不 所有元素都是唯一的 1 1 2 4 5 是的 其中 2 个是相同的 没有排序 是否有分而治之的策略 我陷入了如何划分的困境 def is valid i

  • 生成所有多集大小为 n 的分区的算法

    我一直在试图找出一种方法来生成多重集的所有不同的大小为 n 的分区 但到目前为止却空手而归 首先让我展示一下我想要实现的目标 假设我们有一个输入向量uint32 t std vector

  • 如何有效地找到距给定点最远的点（从一组点中）？

    我正在寻找一种算法或数据结构来解决以下问题 给你一组点 S 然后你会得到另一个点形式的 Q 查询 对于每个查询 找到集合中距离给定点最远的点 集合中最多有 10 5 个点和 10 5 个查询 所有点的坐标都在 0 到 10 5 范围内 我想

  • d3力定向布局-链接距离优先

    在 d3 中使用力导向布局 如何使链接距离成为优先事项 同时仍然保持良好的图形布局 如果我指定动态链接距离 但保留默认费用 则我的图形距离会因费用函数而发生一些变形 并且不再是准确的距离 但是 如果我删除电荷 图表将如下所示 任何建议表示赞

  • 直接选择排序与交换选择排序

    有什么区别直接选择排序 vs 交换选择排序 今天我陷入了一场争论 我的教授在他的讲义中使用了这两个术语 维基百科和任何教科书或网站都会为您提供的选择排序就是他所说的 交换选择排序 我以前从未听说过 交换选择排序 这个术语 仅 选择排序 并且

  • 如何检查是否存在可能的路径？

    我正在开发一个基于 javascript 的实验性游戏 玩家必须在二维平铺地图上移动才能退出 请随意检查这个小提琴并演奏 http jsfiddle net moonlife 74vLd 我只是随机放置障碍物 但有时障碍物会挡住玩家和出口之

  • 迭代任意大小的子集

    我可以迭代大小为 1 的子集 for int a 0 a lt size a 或大小为 2 的子集 for int a1 0 a1 lt size a1 for int a2 a1 1 a2 lt size a2 or 3 for int

  • 如何从迭代器推导连续内存

    不知何故 本土stl copy VC Dinkumware 上的算法表明它可以使用memcpy 可以轻松复制的数据 一个凡人能做到这一点吗 假设每个元素都是普通可复制的 random access iterator 是否意味着连续内存 标准

  • 在鼠标光标位置添加 cytoscape 节点

    我想在画布上的单击事件上的鼠标箭头位置添加一个 cytoscape 节点 我怎样才能做到这一点 我的方法 效果不太好 我可以通过单击创建一个节点 但无法确保创建的节点的位置位于我单击的位置 使用这样的东西 cy click function

  • Florian 的 Grisu2 算法如何工作？

    我遇到了一个关于将 double 转换为 ascii 的问题 经过搜索 我得到了 Florian 的论文 使用整数快速准确地打印浮点数 http www cs tufts edu nr cs257 archive florian loits

  • Java递归方法求阶乘返回负输出[重复]

    这个问题在这里已经有答案了 我知道这是溢出 但问题是 20 是相对较小的数字 这不应该发生 对吧 有没有更好的方法来查找大数 例如 1000 的阶乘 而不会得到这种奇怪的结果 public class RecursiveFunctionsE

  • 在java中使用BUBBLE SORT对二维字符串数组进行排序

    类似的问题已经被问过 但从来没有关于二维字符串数组 因此在尝试了很长时间之后我找不到我想要的 我正在尝试使用 BubbleSort 对 java 中的 2D 字符串数组进行排序 作为输入 我收到一个二维字符串数组 一个表 以及您应该排序的

  • 需要解释搜索最小大和的算法

    我正在解决 Codility 问题作为练习 但无法回答其中一个问题 我在互联网上找到了答案 但我不明白这个算法是如何工作的 有人可以引导我逐步完成它吗 这是问题 You are given integers K M and a non em

  • Prim 的迷宫生成算法：获取相邻单元格

    我基于 Prim 算法编写了一个迷宫生成器程序 该算法是 Prim 算法的随机版本 从充满墙壁的网格开始 选择一个单元格 将其标记为迷宫的一部分 将单元格的墙壁添加到墙壁列表中 While there are walls in the li

随机推荐

热门标签