问题标签 [bipartite]

我有一个查询的二分图和相关的点击网址。基于这些查询，我想对查询进行聚类。我打算使用简单的基于集合的公式来确定两个查询是否相同。我的初始输入数据格式如下：

我很难确定合适的算法来解决这个问题。

将不胜感激任何帮助。

我目前正在通过进行深度优先搜索（最多 10 个级别）来计算二分图中长度为 $n$ 的路径数。但是，我的实现需要 5 分钟以上的时间才能从具有 3000 多个元素的二部图中计算出 700 万条长度为 5 的路径。我正在寻找一种更有效的方法来解决这个计数问题，我想知道文献中是否有这样的算法。

这些是无向二部图，因此路径中可能存在循环。

我的目标是计算在一分钟内包含 100 万个元素的二分图中长度为 $n$ 的路径的数量。

提前感谢您提供任何建议的答案。

我有一个断开的二部无向图。我想完全断开图表。我可以执行的唯一操作是删除节点。删除一个节点会自动删除它的边。任务是最小化要删除的节点数。图中的每个节点最多有 4 条边。

通过完全断开图表，我的意思是不应该通过链接连接两个节点。基本上是一个空边集。

我在课堂测试中遇到了一个问题。在图书馆里，每个成员要四本书，而每本书只有两个成员要。此信息以二分图 G = ( X + Y , E ) 的形式给出

X：所有成员的集合 Y：所有书籍的集合 Edge E = 边的集合 (x,y)，其中 x 是为书籍 y 请求的成员。我们必须找到图书馆员最多可以给每个成员两本书的方式，以使最多的成员满意。

我提出了两种方法：

1. 引入两个新顶点 s(source) 和 t(destination)。将边从 s 引入 X 中容量为 2 的所有成员。所有边 E 的容量为 1，新边 Y 到 t 的容量为 1。现在应用 Max flow 算法找到最大匹配。最大匹配是所需的解决方案。
2. 另一种方法是通过引入相同的边来遵循与上述相同的算法，但每条边的容量为1。现在找到最大匹配。此匹配将为最多成员提供一本书。删除匹配的书籍并再次应用上述算法。再次删除匹配的书籍和拥有两本书的成员，并再次应用算法，直到 X 和 Y 之间没有边缘。获得的解决方案是所需的解决方案。

虽然我得到了上面的算法，但我不确定哪个是正确的，或者没有一个是正确的。如果还有其他算法，请在此处提出建议。

我似乎找到了一种算法，但无法理解它，我想知道你们中是否有人知道该算法的通用大纲。

这是我在第 2 页找到的算法的链接

http://www.cse.iitb.ac.in/~sundar/cs435/lecture23.pdf

有谁知道用于在二分图中找到最大独立顶点集的蛮力算法的通用轮廓？

我知道还有其他算法，例如用于查找 MIS 的 König 定理，但我想知道蛮力方法的伪代码是什么？

此外，这种蛮力算法的运行时间复杂度是多少？

我正在用两个解决一个匹配vectors问题class

这是我试图实现的算法：

对于粗略匹配，如果left[i]与 匹配right[j]，则left[i].n = j、left[i].match ='M'、right[j].n = i和right[j].match = 'M'不匹配的有成员n = -1和match = 'U'

在找到增广路径时，如果一个存在另一个（i，j），那么我们将match不匹配的成员从'M'to更改为，'U' 并且n = -1 与增广路径匹配的两个match在我们更改时将其成员更改为“A”他们的成员n根据他们的指数。

我不知道这是否是解决这个问题的正确方法，这是我第一次尝试最大匹配，我已经阅读了很多文章并在线观看了教程，但我无法让我的“代码”正常运行。

我不需要代码，我可以编写我的代码。我只是想一步一步地理解这个算法。如果有人能给我一个像我上面尝试过的算法，我将不胜感激。另外，如果从那以后我一直走错方向，请纠正我。

我有以下数据框：

其中 X1 是人员编号，X2 是人员所属的组。一个人可以在不同的组中。现在我想从每个人到他所属的每个组划一条线。我用plot()这种方式解决了它：

结果如下所示：

现在我想知道如何用 ggplot2 做到这一点？

谢谢你的帮助！

给定一个二部图G = ( U , V , E )，我想找到V的所有（最大）子集，它们是G的连通分量的一个“边” 。

例如，对于关联矩阵

其中行索引表示U而列索引表示V，输出应该是集合 {0, 1, 5}, {2, 4} 和 {3}。

这是否等同于任何标准问题？更重要的是，有没有有效的解决方案？

我正在重新开发一个遗留系统，将一篮子用户选择的零售产品与一个或多个有效促销相匹配。这些促销是行业标准的BOGOF（买一送一），买二送三，购买产品X和Y并获得10％的折扣，等等......但都要求您可以将潜在项目列表过滤到那些满足这些促销活动。

我希望解决方案能够在一次操作中获取一整篮零售商品并对其进行分析，而不是在订购时匹配单个产品的现有方法。（当前的解决方案导致了不良的限制）

每个促销活动都有一系列符合条件的产品，必须存在这些产品才能触发促销活动。它们排列在 n 组（或位置）中，例如：

除非该商品多次出现在同一组中，否则每次促销活动必须包含每个组中的一种产品。促销可以有无限（但通常<10）“套”产品。

举个简单的例子，一个购物篮Item 1, Item 4 and Item 6会触发促销，同样的购物篮Item 1, Item 1 and Item 2也会触发它。然而，篮子Item 1, Item 2 and Item 3不会像每套都不满意。

除了检测何时触发促销的最佳方法这一显而易见的问题之外，我还需要恢复该项目已匹配到的集合（位置）以处理定价等细节。这也是可取的如果将更昂贵（以货币计）的商品分配给促销活动时，它们比更便宜（同等匹配）的商品更受青睐。

希望下一部分能帮助解决问题，不要听起来那么不清楚以至于会产生不必要的噪音，请随意忽略！

到目前为止，我最好的解决方案是为“购物篮”中的每个零售项目创建一个新的集合，其中包含该项目将满足的促销集（位置）。IE。

然后我的理论是你“检查”这个集合列表在每个位置都包含一个独特的项目，并且每个提升位置都被填充。到目前为止，我的工作示例都使用蛮力、循环或递归来生成集合的所有组合（上图），以尝试检查是否存在唯一组合。这非常糟糕，除了一个非常微不足道的例子之外的任何东西在现实世界中根本不起作用。（此函数将在商品添加到购物篮时实时调用，因此需要快速）

许多研究表明，二分匹配会产生一些预期的结果，但我只能找到关于该主题的研究文章和相当复杂的数学文本。一些伪代码或基本逻辑会很棒。

我的两个问题基本上是：

1) 有没有人看到一种更好/更快/更简单的方法来分析客户篮子以产生匹配的促销活动。
2) 假设我已经确定了将商品匹配到相关位置的最有效方式，那么确定要针对促销记录的零售商品清单的最便宜方式是什么。

任何帮助将不胜感激，因为我再也看不到隧道尽头的光了！（最终的解决方案将在 .NET 中，我们使用 SQL server 2008 R2。）