问题标签 [bipartite]

我给出了一个图，其中每个顶点正好有 3 条边。现在我必须找出该图是否可以分解为爪。我知道，如果图是二部图，那么它可以分解成爪，我不明白，爪与二部检查有什么关系？

有两组，一组包含班级列表，另一组包含教师列表。每个教师都有一组班级。我们必须为特定班级分配一名教师，这样教师参与的班级数量应该是最大的。这是问题与任何优化算法有关？我找不到任何类似的算法。请帮助我获取逻辑。

预先感谢

我有两种类型的数据，X 和 Y。X 中的每个 x 都与一定数量的 Y 相关联，并且 Y 中的每个 y 可能会或可能不会与一定数量的 X 相关联。

X 不与其他 X 关联，Y 也不与其他 Y 关联。所以情况是这样的：

左边是 Xs，右边是 Ys。

当我只有一种类型的数据时，我知道如何找到图形的连通分量：创建一个 N×N 矩阵并调用graphconncomp它。当我有两种类型的数据时，如何找到所有连接的组件？

在为不相关的事物绘制图表时，我遇到了以下算法问题：

我们有一个二分图的平面图，不相交的集合按列排列，如图所示。我们如何重新排列每列中的节点，以使边缘交叉的数量最小化？我知道这个问题对于一般图（链接）来说是 NP-hard，但是考虑到图是二分的，有什么技巧吗？

作为后续，如果有第三列w，它只有边缘到v怎么办？还是更进一步？

我有一个项目，它要求我将课程分发给学生。所有学生都要求一些课程，但他们只能获得一些课程（可能是他们要求的，少于或只有 0），所有的课程都有配额，我需要找到完美匹配（所有配额都已满，学生得到了他们被允许的）是否存在——如果存在匹配的输出。

到目前为止，我只是获取输入并将其存储在对象中。项目有时间限制，我不知道从哪里开始。对这个项目有什么建议或方法吗？

我想我应该实现二分匹配算法。我是 C++ 新手，所以我需要同时实现节点类和边缘类吗？或者我应该使用邻接列表？哪一个跑得更快？

例如，一个学生要求学习编号为 3,4 和 5 的课程，但他可以上 2 节课，因此如果存在完美匹配的可能性，算法应该给出其中 2 个选择。

我对二分问题的想象是这样的，但我认为这很难实现。 http://i.stack.imgur.com/wtJ6o.jpg

可能还有更多，我不知道。

（学生 -> 课程）

积分定理告诉我们，如果流网络中的所有容量都是整数，那么存在一个最大流，其中每个值都是整数

但最显着的部分是存在，不是每一个最​​大流量！这意味着该语句并未声称每个最大流量都是整数值

我无法弄清楚为什么如果所有容量都是整数，但存在最大流量不是整数值！

还是我只是对试图告诉我的这个定理有错误的想法？

我正在研究一个算法需要使用二分图的项目，我想知道在 javascript 中创建这种数据结构的最佳或更简单的方法是什么？

我无法在网上找到任何好的解释，所以如果有人可以自己帮助我或以正确的方式指出我，那就太好了。

在论文的最后 2 段中，关于 Hopcroft–Karp 算法在二分图中找到最大基数匹配：

https://dl.dropboxusercontent.com/u/64823035/04569670.pdf

一个阶段的执行时间为 O(m+n)，其中 m 是 G 中的边数，n 是顶点数。因此整个算法的执行时间为 O((m+n)s)，其中 s 是最大匹配的基数。

如果 G 有 n 个顶点，则 m <= n^2 / 4 和 s < n / 2，因此执行时间以 O(n^(5/2)) 为界。

我不明白给出：

为什么他们得出结论：

不应该是：

任何想法？

已编辑：链接已修复。我的错。

免责声明：这不是任何作业，当我浏览所有圣诞贺卡时，我才想到这个问题

问题如下：我们有 M 个信封和 N 个字母，每个字母被描述为一对正整数。信封和信件都是矩形的，显然可以旋转。如果两个尺寸都小于或等于信封的尺寸，则一封信可以装入信封。目标是找到最大的信封字母匹配。

该问题很容易转换为最大二分匹配问题，其中O(sqrt(M+N) * MN)存在运行算法（Hopcroft-Karp，转换运行微不足道O(MN)）。我试图提出一个贪心算法或动态方法，但我没有找到任何方法。

你知道任何更快的解决方案吗？

我有一个图，它可能（或可能不）包含一组使其成为二分的边。我怎样才能发现这样的集合是否存在？

在 BFS 遍历期间删除特定级别中的所有边会有所帮助吗？