问题标签 [bipartite]

我想使用 edmonds 算法在二分匹配中找到最大匹配。不幸的是，我无法获得伪代码。谁能帮我？

寻找朝着正确方向迈出的一步。我已经做了 4 节课。一个是超类，它是图和 3 个子类，称为 Edge、DirectedGraph 和 BipartiteGraph。

我在创建二分图时遇到了一些麻烦。具体来说，我得到了这些指示：

扩展 Graph 类以创建一个新的 BipartiteGraph 类。它应该继承超类的所有功能：

• 自动将所有偶数索引顶点 (0,2,4) 指定为类中“A 分区”的一部分，并将所有奇数索引顶点 (1,3,5) 指定为“B 分区”的一部分。这不需要新的代码，只是一个概念上的期望。

• 重写 Graph 的构造函数以具有相同的输入（顶点数），调用超级构造函数，然后验证图是二分的。也就是说，确保所有现有边都是从 A 中的顶点到 B 中的顶点。如果图不是二分图，则消除内部表示（例如，对于邻接矩阵，制作大小为 0x0 的数组），因此它不能使用！

• 添加一个方法 setPreferences() ，该方法将整数和整数数组或 ArrayList 作为参数。第一个整数是我们想要附加偏好的顶点，列表是偏好列表，从最喜欢到最不喜欢。验证 ints 数组是否以某种顺序包含另一个分区的所有成员，然后保存该信息（您将需要一个数组/ArrayLists 的一维数组来存储这些列表，每个顶点一个）。

• 添加没有参数并返回稳定匹配的方法 stableMatching（以整数对的 ArrayList 的形式）。查阅维基百科会有所帮助：http ://en.wikipedia.org/wiki/Stable_marriage_problem 。作为开始，我建议验证每个顶点是否都为其设置了首选项列表！

这是我在超类中的构造函数：

这是迄今为止我对 BipartiteGraph 类的内容：

我是不是把事情弄得太复杂了，代码比看起来简单吗？

我在 JUNG 中创建了一个二分图，我想对一组节点进行单模投影。在投影中，如果同一集合的两个节点共有一个属于另一个集合的节点，则它们将被链接。JUNG 中是否有已经完成的功能？到目前为止我的代码（对于 1600 个节点的二分网络来说非常慢，其中只有 400 个属于我想要投影的集合）是：

代码中的瓶颈是当我想更新链接权重时......没有它，代码真的很快......我不知道我错在哪里......任何帮助都比欢迎。

假设有N个这样的酒店想聘请一名厨师，N个这样的厨师正在寻找工作。所以，在进行了面试之后，每个酒店都根据自己的喜好准备了自己的厨师名单，同样，每个厨师也准备好了根据他/她的喜好排序的酒店列表。现在，我们得到了所有酒店和厨师的偏好列表，我们需要计算有多少酒店和厨师得到了他们的第一偏好。

示例：假设我们有 N=4 并且按降序排列的酒店偏好列表如下：

1 2 3 4

2 3 4 1

4 2 3 1

1 3 2 4

同样的首选厨师名单如下：

1 2 3 4

4 3 2 1

4 2 3 1

4 1 2 3

现在在这里 1 家酒店将获得他的第一个首选厨师，2 名厨师将获得他们首选的酒店。

我需要找到这些酒店和厨师的数量，他们都得到了他们的首选

我正在解决一个问题，它有一个加权完全二分图（X，Y，XxY），其中 X 有 n 个节点，Y 有 m 个节点，n 小于 m。我想要一个完美的无交叉匹配图，这样在匹配集合 X 到集合 Y 时没有两条边交叉，并且 X 中的所有节点都在最后取。结果图的权重总和应该是最小的，我需要设计一个动态规划算法。我是这样想的：

X 和 Y 中的节点排列为 x0，xi 可以与 Y0、Yi 等具有水平边缘，但 Y 的节点比 X 多。对于 X (i) 中的每个节点，我考虑两个选项，即水平邻居，即 j in设置 Y 或对角线邻居 (i, j-1), (i,j+1) 并选择最小化成本的边。我跟踪 X 和 Y 中已经采用的节点。时间复杂度 O(纳米）

有没有更好的方法可以实现这一点。任何帮助表示赞赏。这是我在期中考试时遇到的一个问题，但我把它留给了选择。

我一直在为一个编程竞赛（Andrew Stankevich Contest 21）中的一个问题苦苦挣扎，这个游戏如下所示：

尼克和彼得喜欢玩以下游戏 [...]。他们在一张纸上绘制一个无向二分图 G，并在其中一个顶点上放置一个标记。之后，他们轮流行动。尼克先行动。

移动包括沿图边缘移动标记。在它之后，标记在移动之前所在的顶点以及与其相关的所有边都从图中删除。没有有效动作的玩家输掉游戏。

给出了图表，现在的任务是寻找给定的起始节点，如果两个玩家都发挥最佳，起始玩家是赢还是输。总结

• 二分图
• 我们得到了起始节点（比如在左侧）
• 我们轮流移动，移动包括跟随一条边，但我们不能访问已经访问过的节点
• 不能移动的玩家输了

由于该图是二分图，Nick（第一个玩家）总是会从左侧删除一个节点，而 Peter 总是会从右侧删除一个节点。

该图最多可以有1000个节点（每边最多500个）和50000条边，所以需要一个好的多项式时间算法（这里的时间限制是2秒来解决所有起始位置，但我认为我们可以分享很多不同起始位置之间的信息）。

我很确定这可以简化为某种顶点覆盖或打包问题，因为该图是二分图，但我找不到与其中任何一个相关的策略。

我知道一个特殊情况的解决方案：假设边分别有n ₁和n ₂个顶点。如果存在大小为min(n ₁ , n ₂ )的匹配并且如果较小一方的玩家开始，则存在获胜策略：他只需遵循匹配的边缘并自动获胜。

有任何想法吗？

我看到了 jgraph 和 jgrapht 的示例，并且很容易理解，但现在确定我将如何使用 CompleteBipartiteGraph？用于实例化图形的语法如何？

http://jgrapht.org/javadoc/

http://jgrapht.org/javadoc/org/jgrapht/generate/CompleteBipartiteGraphGenerator.html

I having problem getting jgrapht or jgraph or applet to visualize this graph correctly? Can I use this graph library to visualize similarly to the picture beneath? U would be x and V would be Y in the code for example. I'm using the demo versions that used directed graphs to do same in this example. Not sure if I should use a jgAdapter or jgxAdapter? Currently getting blank applet for either.

我正在研究算法分析。我目前正在阅读Network Flow算法。我正在考虑应用Network Flow有关寻找bipartite matchings最低成本的算法。

• 让G对应的网络流G'
• 让M我们perfect matching进入G
• 让G<sub>M</sub>与residual graph此匹配相关联

来自 Jon Kleinberg 和 Eva Tardos 的算法设计7.13 第 406 页，

Theorem 7.62状态：

(7.62) 令 M 为完美匹配。_{如果 G M}中存在负成本有向循环 C ，则 M 不是最小成本

这个定理是有道理的，但是，我对 abipartite flow network's residual graph的 aperfect matching如何实际上包含一个循环感到困惑。我可以看到一个循环的唯一方法是是否涉及sink或source。

然而，在 aperfect matching中将source不包含离开它的边缘，并且在sink将不包含进入它的边缘。此外，内部节点中发生的循环似乎与 a 的定义相矛盾Bipartite graph。

有人可以在残差图中提供这样一个循环的例子吗？

我有一个矩阵，我在 MATLAB 中绘制了一个二分图，如下所示。

在这种情况下，所有线都分别连接（0 和 1）第 2 列。但我只想在第 2 列的元素等于1时连接。 不需要 0。如何绘制或如何在 MATLAB 中编写代码？