问题标签 [bipartite]

我必须找到一种算法来解决教职员工的问题。我不是要求解决方案（请不要发布任何解决方案），请进一步阅读。

问题的句子：

在过去的两天里，我一直在尝试找到一种算法来解决这个问题，我认为我走对了。对于之前偶然发现它的任何人：你知道这个问题是否已经在多项式时间内解决了吗？（如果不是，它是 NP-complete/NP-hard/NP 吗？）

在此先感谢，约翰

我有一个data.frame描述具有非常大（数百万）和相当小（数百）独立集的二部图。

我想在较小的独立集上获得图的二分投影，但无需先创建大二分图，尤其是对较大独立集的巨大二分投影。此限制的原因是igraph段错误和 RAM 限制（我只有 8GB RAM）。

例如，给定

我想要数据框

边的权重加起来。

（在本例中，abc是“较小”的集合，12是“较大”的集合）。

我有一个两种模式的网络边缘列表数据，如下tmp所示：

我这样做是为了添加“类型”属性以在 igraph 中创建二分图

但结果是类型全是“假”，名字不匹配。有谁知道这里出了什么问题？

我正在使用二分图分析我在给定主题和地理位置上下载的推文的网络和语义值。

使用 Python，我创建了一个 .net 文件，其中包含 2 组节点和边。该文件是我单独创建的文件的合并：2 组顶点和边。问题是创建 .net 文件的 Edges 组件。

我有 3 个文件：

• 带有发件人/高音扬声器（“号码/ID”和“姓名”）的tweeterers.csv
• words.csv，带有我从推文中提取的语义标签/单词。格式为“编号/ID”和“名称”，“编号”从上述文件的最后一个“编号”开始。每行有 0 到 6 个单词
• Names_Text_full_clean.csv，带有高音扬声器和单词。每行包含 1 个高音扬声器的名称和 0 到 6 个单词 该文件将为我提供高音扬声器和单词之间的关联，用于图表。

我基本上阅读每个高音喇叭，阅读一个单词，阅读是否有关联。如果是，我写关联（这是一个优势）。是三环。这对于中等规模的网络来说非常缓慢：一个拥有约 650 个节点和约 18000 个边缘的网络在 Mac Mini 2.7GHz 四核上花了我将近 2 天的时间。

任何加速它的帮助将不胜感激！

以下是代码：

我想知道是否存在一种有效的算法来计算有向无环图中的最小路径覆盖。请不要将最小“路径覆盖”与“顶点不相交路径覆盖”混淆。对于后者，我知道一种使用相应二分图的最大匹配的有效算法。但这仅适用于顶点不相交的情况。当每个顶点可以被多次访问时，是否可以放宽相同的算法以获得路径覆盖的答案？

二分图是一个图，其顶点可以分为两个不相交的集合 U 和 V，使得每条边都将 U 中的一个顶点连接到 V 中的一个顶点；也就是说，U 和 V 都是独立的集合。等效地，二分图是不包含任何奇数长度循环的图。

我还可以说，如果在图 G 中所有循环的长度都是偶数，那么它是二分的吗？

我想到了一个偶数周期图，结果证明它是非二分的。

我知道有很多类似的话题。但他们中的大多数给我留下了一些疑问。我想要做的是找到完美匹配（或者在没有完美匹配的情况下尽可能接近完美），然后从所有可以匹配 n 个顶点中的 k 个的匹配中（其中 k 可能是最高的） )，我想选择尽可能高的总重量。所以简单地说我要说的是以下优先级：

1. 匹配尽可能多的顶点
2. 因为在大多数情况下（非加权）最大匹配是明确的，所以我想选择边缘权重总和最大的匹配。如果其中有几个重量相同，那么选择哪个并不重要。

我听说过 Ford-Fulkerson 算法。它是按照我描述的方式工作还是我需要其他算法？

我在 SPOJ SPOJ:BUGLIFE上做了一个问题 它要求我检查图表是否是二分的。我知道单个连通图的方法，但是对于断开图的组合，我的方法给出了超出时间限制的错误。这是我的方法 - 广度优先搜索，使用循环队列和由邻接列表实现的图形。方法 -> 选择一个源，如果该源顶点=未访问，则假设它是源，则开始广度优先搜索。如果我在 BFS 中发现冲突，那么我会中止整个事情。否则，我会转到另一个未访问的来源。我怎样才能让它更快？或更好？

PS我是图论的新手，所以请详细解释一下。

我在 Skiena 的算法设计中遇到了一个问题。我不知道我的解决方案是否正确。

5-18。考虑一组电影 M_1、M_2、.. M_k。有一组客户，每个客户都表示他们想在这个周末看的两部电影。电影在周六晚上和周日晚上放映。可以同时放映多部电影。您必须决定哪些电影应该在周六播出，哪些电影在周日播出，这样每个客户都可以看到他们想要的两部电影。是否有每部电影最多放映一次的时间表？设计一种有效的算法来找到这样的时间表（如果存在）。

解决方案：我们有一组电影{M1,M2..Mk}和一组{C1,C2,..Cp}给客户。我们连接C1想要观看的边缘2电影，连接边缘2电影C2 想看的电影等等。这组电影变成了一个连通图。我想验证它是否是一个二分图，比如不能在同一晚放映 2 部喜欢的电影（将 2 部喜欢的电影用不同的颜色着色） .如果是，我们会在星期六显示所有以第一种颜色着色的电影，在星期日显示第二种颜色的所有电影。问题解决了。但如果不是我该怎么办？

以下是Maximum Bipartite匹配问题：http ://www.spoj.com/problems/QUEST4/ 通过论坛我知道这个问题可以转换为Minimum Vertex Cover问题，然后可以通过Maximum解决双向匹配。但是，我不明白问题是如何转换为最小顶点覆盖的。请帮助我理解这一点。