问题标签 [bipartite]

我正在研究与图论相关的事情。实际上我有一些二分图的数据，我想通过以图形形式可视化来测试它的有效性。

我的数据形式如下（三角形）：

V 表示顶点，U 表示边（A、B、C 和 E 是标签）。任何人都可以建议最适合我的目的的任何工具/库（Java/C）。

我是图表新手。我在二部图中有两组。我需要找到所有可能组合的唯一匹配。所以我想我使用 Hopcroft-Karp 来找到最大匹配。作为一个新手，我以为我会得到结果匹配图，但它告诉我的只是 42。啊，这真的很有帮助。我不需要知道有多少匹配项我需要知道自己的唯一匹配项。

我错过了什么吗？如何获得结果匹配？

我正在实现一种算法来确定无向图是否是二分图。基于这个伪代码实现了我的实现，它适用于连接的图，但是当它断开连接时，程序只会指示错误的答案。我认为如果它没有连接，那么每个不相交的子图都需要一个循环。但我坚持这一点。如何解决我的代码以打印正确答案？

例如对于这个输入

输出应该是：

而是向我抛出输出：

发生这种情况是因为该图不是连通图，即具有两个连通分量。我希望您能帮助我，因为我已经被这个问题困扰了好几天了。

我阅读了《算法设计》一书，第 1 章，它对如何将二分匹配转换为独立集问题进行了非常简短的描述，但我不明白。

有人知道描述这个过程的任何详细资料吗？谢谢！

我正在使用元启发式方法编写一些代码，以找到解决固定电荷传输问题 (FCTP) 的良好解决方案。

我遇到的问题是基于为底层二分图找到生成树来生成一个起始解决方案。

我希望它是一棵随机生成树，这样我就可以多次针对同一个问题运行该过程，可能会得到不同的解决方案。

我在做这件事时遇到了一些困难。到目前为止，我采用的方法是对弧进行随机排列，然后遍历此列表，如果不会创建循环，则按顺序将它们放入基础。

我需要找到一种快速的方法来检查是否包含弧会创建一个循环。我不想“蛮力”它，因为考虑到大问题实例，这种方法可能需要大量时间。

鉴于这A是一个具有随机排列的弧的数组，您将如何进行选择过程？

我已经为此工作了几个小时，但我尝试过的任何方法都没有奏效，其中大部分在应用方面都是荒谬的......

我正在尝试从绘制点并且部分或全部具有标签的图形 xy 图中提取语义。标签被绘制在“点附近”，以便人们通常可以理解哪个标签与哪个点对应。例如，在此图中，可以清楚地看到哪个标签（数字）属于哪个点（*），并且基于欧几里得距离的算法将起作用。（标签和点没有语义排序 - 例如散点图）

在拥挤的图中，创作软件/人可以将标签放置在不同的方向以避免重叠。例如在

人类读者通常可以计算出哪个标签与哪个标签相关联。

我接受的一种解决方案是创建一个欧几里得距离矩阵并打乱行以获得函数的最小值（例如，对角线或其他启发式距离的平方和）。在第二个示例中（从 NW 角顺时针标记为 a、b、c、d 的点）我们有一个距离矩阵（到 1 dp）

我们需要给a1 b2 c4 d3. 交换第 3 行和第 4 行给出对角线的最小和。这是一个更复杂的示例，其中简单地选择最近的可能会失败

如果解决了这个问题，那么我将需要处理标签数量可能小于或大于点数的情况。

如果算法是标准的，我将不胜感激开源 Java 的指针（例如 JAMA 或 Apache 数学）

注意：这个 SO 答案将附近的点与路径关联起来并不能很好地作为答案，因为给出了通过这些点的路径。

情况：用户选择多个其他用户作为项目的可能合作伙伴。用户对他选择的一个用户没有偏好（即，他列表中的任何用户都足以成为合作伙伴）。例子：

真正的清单会大得多。

我的问题：给定一组用户及其首选合作伙伴（如上面的列表），我想生成一组最终合作对。最终合作对的数量必须最大化（我希望尽可能多的人成对）。

这是我认为我需要的算法：Edmonds's matching algorithm，但由于我不是数学背景，我在解释和实现它时遇到了麻烦。

任何帮助，将不胜感激。提前致谢。

也就是说，我怎样才能找到一些顶点可能不连接到任何其他顶点的图的二分匹配？

编辑：还有一个条件，假设边缘也被加权，我想要一个匹配，使得总边缘权重最小化（或最大化）。

我的一般问题是我在使用 iGraph 生成图形时丢失了顶点名称/标签（不确定这里的正确词）。

我有一个二分网络的边缘列表 IC_edge_sub，如下所示：

然后我创建一个图形元素：

然后将其折叠以仅识别 companyID 之间的连接

然后得到邻接矩阵：

在 iGraph 中，节点编号从零开始，因此矩阵命名也从零开始。但是，我现在需要最终 CC_matrix_IC_based 矩阵中边缘列表的第二列中指定的“new_companyID”。

你能帮我如何使用原始边缘列表中的信息将行名和列名放入最终的邻接矩阵中吗？

我用谷歌搜索并搜索了堆栈流，但无法真正找到有效的答案。非常感谢你的帮助

假设我们有两个集合：A=(a_1,a_2,...,a_m) 和 B=(b_1,b_2,...,a_n)（不一定大小相同）。函数 F 为从集合 A 到集合 B 的每个链接分配权重：F:A*B->R。因此，例如，F(a_1,b_1)=2 表示 a_1 和 b_1 之间链接的权重为 2。问题是将集合 A 的元素连接到集合 B 的元素，以最大化满足这些约束的链接权重：

• 集合 A 的元素必须与集合 B 的一个元素完全匹配。
• 集合 B 的元素允许有零个或多个匹配 (0,1,2...)，尽管 B 的元素存在对权重总和 C_i 的约束。也就是说，如果我们选择将 a_1 连接到 b_1，而a_2到b_1，权重之和F(a_1,b_1)+F(a_2,b_1)应该小于等于C_1。此约束适用于 B 的所有元素。

我已经搜索了一些想法，并研究了分配问题和匈牙利算法。另外一点是，这些都没有考虑到我的第二个约束。您对如何解决这个问题有任何想法吗？

谢谢