bipartite

3热度

3回答

我正在实现一个算法来确定一个无向图是否是二分的。基于this pseudo-code使我的实现，它适用于图形连接，但是当它断开时，只是程序指出了一个错误的答案。我认为如果它没有连接，那么每个不相交的子图就需要一个循环。但我坚持这一点。我怎样才能解决我的代码，让我打印出正确的答案？ #include <cstdio> #include <vector> #include <queue> #in

3热度

1回答

如何将二部匹配转换为独立集

我读过“算法设计”一章，它给出了如何将二部匹配转换为独立集问题的简短描述，我不明白。有没有人知道任何详细的matriel来描述这个过程？谢谢！

2热度

2回答

二分图的随机生成树

我正在努力使用metaheuristics为寻找固定电荷运输问题（FCTP）的良好解决方案做一些代码。我遇到的问题是生成一个起始解决方案，基于找到基础二分图的生成树。我希望它是一个随机生成树，以便我可以多次运行同一个问题的过程，可能会得到不同的解决方案。我在做这个时遇到了一些困难。到目前为止我所采用的方法是对弧进行随机置换，然后遍历这个列表，如果它不会创建一个循环，则将它们依次放入基础中。

0热度

1回答

将图书馆书籍分配给成员以使最大成员满意的算法

我在班级测试中遇到了问题。在一个图书馆里，每个成员要求四本书和每本书只有两个成员要求。此信息在二分图G =（X + Y，E）的形式给出 X：设置所有成员的Y：设置的所有书籍边缘E =边集（X，Y），其中x是书y所要求的成员。我们必须找到图书管理员可以给每个成员最多两本书的方式，以使最大成员满意。我想出了两种方法：引入了两个新的顶点S（源）和T（目标）。将边从s引入到X中容量为2的所有成员

0热度

2回答

绘制二分图的工具或库？

我正在从事与图论相关的工作。其实我有一些关于二分图的数据，我想通过以图形形式显示来测试它的有效性。我的数据是在等（三角形）形式： V 0 A V 1 B V 2 C U 0 1 E V表示顶点和U表示的边缘（A，B，C和E是标签）。任何人都可以推荐任何最适合我的目的的工具/库（Java/C）。

15热度

2回答

iGraph图中的顶点名称在哪里

我的一般问题是，当使用iGraph生成图时，我丢失了顶点名称/标签（不确定这里是否有正确的单词）。我有二分网络的边缘列表IC_edge_sub，看起来像以下： new_individualID new_companyID 1 <NA> 10024354c 3 10069415i 2020225c 4 10069415i 16020347c 5 10069272i 20

1热度

2回答

查找最小顶点给定匹配最大值的二分图覆盖

我似乎找到了算法，但无法理解它，我想知道是否有人知道该算法的通用轮廓。这里是链接到算法I 2页 http://www.cse.iitb.ac.in/~sundar/cs435/lecture23.pdf

3热度

1回答

Brute Force在二分图中寻找最大独立顶点集的算法？

有没有人知道蛮力算法的通用轮廓在二分图中找到最大独立顶点集？我知道还有其他算法，例如König定理，用于查找MIS，但是我想知道蛮力方法的伪代码是什么？另外，这种蛮力算法的运行时间复杂度是多少？

1热度

2回答

用户之间非二部非加权最大匹配

情况：用户选择多个其他用户作为项目的可能合作伙伴。用户没有偏好他选择的另一个用户（即，他的列表中的任何用户对于伙伴而言足够好）。例如： | user_id | preferred_partners | | 1 | 2 4 | | 2 | 3 1 | | 3 | 4 2 1 | | 4 | 1 | 真实名单会大得多。我的问题：给定一组用户及其首选合作伙

3热度

2回答

我怎样才能找到一个图的非完美双向匹配？

也就是说，我怎样才能找到一个图的二部分匹配，其中一些顶点可能没有连接到任何其他顶点？编辑：一个更多的条件，假设边缘也加权，我想匹配，使总边权重最小化（或最大化）。