问题标签 [bipartite]

我正在寻找一种简单的算法来获得二分图的边中的最小加权边。我搜索了一下，我都知道这意味着二分图的覆盖边，换句话说，如果我们有二分图并且每条边都有一个数字权重，如何获得其中最小的数字

我在graphviz中绘制了一个二分图，我希望它有两列由直线连接的节点（以匹配其他地方使用的样式）。我基本上可以得到我想要的东西（见图），但是列太靠近了，这使得边缘不必要地难以遵循。

我试图在前两个节点之间添加一个非常低权重的连接，希望它将两个子图分开，但这不起作用（并且经常会弄乱布局的其余部分）。有没有办法将右侧的节点列进一步向右移动。

这是一个显示我看到的问题的示例

这是我用来生成此图的代码

如何使用广度优先搜索在简单（非有向）二部图中找到最短循环？

我需要测试我编写的一些代码来解决最大二分匹配问题。有谁知道我可以用来测试的大型数据集的任何示例？理想情况下，这些将包括二分图的数字表示，最好是大尺寸的，甚至更理想的是，提前包含解决方案，以便我可以检查我的结果。

有人可以推荐一个库或代码来可视化 C# 中的二分图吗？

Graph# 似乎不直接支持这种图（但对解开顶点有一些支持）。

我想创建一些像这个二分图这样的图形，在节点中有一些文本。具有相同宽度和高度的节点将是理想的。

WPF 控件将是完美的，因为它存在于 graph#。甚至可能存在 XAML 定义？作为替代方案：报告窗口也可以非常好。

可能在 Graph# 方面有更多经验的人可以提供有关如何使用 Graph# 执行此操作的提示。

使用 NodeXL 进行了一些尝试，但这似乎不是完美的解决方案，因为节点似乎不可修改。也许有人可以提供更好的解决方案。玩过 Soroush 提供的 NetworkView。目前这最接近我想要的。

-update- 试用了 Soroush Falahati 共享的 NetworkView。这似乎是一个很好的基础，但还没有我需要的那么灵活。我很难相信没有图书馆可以开箱即用地做这些事情。（NetworkView 具有在控件中设置连接/边缘的出色功能，这使其在 NodeXL 上得到了额外的提升）。也许 Graph# 可以做得更多，但目前我只是尝试了这两个。

有这个库实现了许多算法，其中之一是最大二分匹配。

这是源代码的链接： http: //shygypsy.com/tools/bpm.cpp

我也会把它包括在这里（没有评论）

我们有一个运行m时间的 for 循环。这个数字m是指工人的数量。然后我们进入bpm有另一个for循环的函数。这个循环运行的n时间n是任务的数量。

到目前为止，我们有m*n时间复杂度。

然而，bpm在第三个 if 语句中有一个递归函数调用。此函数的目标是运行 adfs以找到增强的路径。

我知道这dfs有时间复杂度O(n+m)。所以我会假设该函数bpm的复杂性为O(n+m)

因此总时间复杂度为O(m*(n+m))

但是作者说它是O(m*n^2). 有人可以解释一下为什么会这样吗？先感谢您！

给定一个二部图，我们要列出所有最大完全二部子图。

例如，

顶点集 L = {A, B, C, D}

顶点集 R = {a, b, c, d, e}

边缘：Aa、Ab、Ba、Bb、Cc、Cd、Dc、Dd、De

最大完全二分是：

{A,B}-{a,b}

{C,D}-{c,d}

{D} - {c, d, e}

我找到了一个蛮力算法，O(2^n)。我不知道是一些近似算法还是随机算法。

我只是在创建一个算法来检测二分图，但我想到了一些我不确定是否算作二分图的图，尽管我的算法说它是。

图表就像

所以这有 3 个节点，但只有A和之间有 1 条边B。这真的是双向的吗？

我想我正在寻找一种可以在二分图中找到“最小”“选择”的算法。每个顶点都有一个相关的（整数）成本来选择它。我只能找到最小化所选集中顶点数量的算法，而不是成本。我以前认为我需要一个“匹配”，但实际上我只需要覆盖每条边的顶点子集......

我认为贪婪的解决方案行不通。假设我们的集合是 A，B：

顶点 1,2,3 在 A 中，成本为 1。顶点 4 在 B 中，成本为 2。

解决方案是删除最昂贵的顶点，4。基于成本选择的贪婪解决方案将失败。类似地，如果 B 的成本为 10，我们无法贪婪地选择连接最多的顶点。

我想到了一个不同的措辞：“给定一个二分图，其中每个顶点都有一个相关的成本，找到一个成本最低的顶点子集，使得每条边都发生在所选子集中的至少一个顶点上”。

在The Algorithm Design Manual中，作者提供了一种对图进行两种着色的算法。它类似于计算组件数量的算法，因为它迭代所有可用顶点，然后仅在未发现该顶点时对该顶点着色并执行 BFS：

BFS在边缘没有被处理或者图是有向的process_edge时候调用一个函数。BFS 看起来像这样：yx -> y

该process_edge函数如下所示：

现在假设我们有一个这样的图表：

我们可以像这样对它进行两种着色：

但是，如果我们按顶点顺序遍历它，那么我们最初将从 node 开始1，并将其着色为WHITE。然后我们将找到节点13并将其着色为BLACK. 在循环的下一次迭代中，我们正在查看5未发现的节点，因此我们将对其着色WHITE并在其上启动 BFS。在执行此操作时，我们会发现节点之间存在冲突5，1因为1应该是BLACK，但之前设置为WHITE。1然后我们会发现and之间的另一个冲突13，因为13应该是WHITE，但它被设置为BLACK。

当通过所有组件（连接或未连接）执行图的正常遍历时，顺序无关紧要，因为无论如何我们最终都会访问所有节点，但是在为图着色的情况下顺序似乎很重要。我没有在书中看到提到这一点，只是在我尝试对上面的随机生成的图形进行双色着色时才遇到这个问题。我能够对现有算法进行一些小改动，从而消除了这个问题：

这种变化是否有意义，还是因为我不理解一些基本概念而造成的？

更新

根据 G. Bach 的回答，假设我们有以下图表：

我仍然对这将如何正确地变成双色感到困惑。使用原始算法，第一次迭代将启动一个带节点的 BFS，1为我们提供一个颜色如下的图：

在下一次迭代中，我们将启动一个带节点的 BFS，5为我们提供一个颜色如下的图：

下一次迭代将启动一个带节点的 BFS，6为我们提供一个像这样着色的图：

但是现在我们不会重新着色5，因为我们已经访问过它，所以这给我们留下了一个没有正确着色的图表。