问题标签 [bipartite]

我遇到了以下问题：

• 有两个不相交的集合，A并且B
• 对于每对元素 ( a, b)（a属于 set A，其中b属于 set B），预先知道一个概率pij。它表示匹配 的概率（确定性级别）a，b或者换句话说，a匹配b的紧密程度（反之亦然，因为pij== pji）。
• 我必须找到具有最高概率/确定性的匹配并找出描述匹配的对 ( a, )b
• 每个元素必须与另一个集合中的另一个元素匹配/配对一次（就像在标准的二分匹配问题中一样）
• 如果可能的话，我想计算一个数字，该数字近似表示所获得匹配的不确定性级别（假设 0 代表随机猜测，1 代表确定性）

下面描述了一个需要这种算法的简单实际示例（这实际上不是我要解决的问题！）：

• 要求两个人在一张纸上写字母 a - z
• 对于每对字母 ( a, )，我们运行一个模式匹配器来确定person写的字母代表person写的b字母的概率。这给了我们一个概率矩阵，它表示每对字母 ( , )的某种相似性相关性aAbBab
• 对于那个人写的每封信A，我们需要找到这个人写的对应的信B

当前方法： 我想知道我是否可以只分配与确定性水平的对数/集合中的元素与集合中的元素匹配的概率成比例的权重，然后a运行A最大加权二分匹配以找到最大总和。对数是因为我想最大化多个匹配的总概率，并且由于单个匹配（表示为匹配元素对-bBab) 形成一个事件链，它是概率的乘积，通过取对数，我们将其转换为概率之和，然后使用加权二分匹配算法（例如匈牙利算法）轻松最大化概率之和。但我不知何故怀疑这种方法能否确保在统计预期最大值方面的最佳匹配。

经过一番搜索，我发现最接近的问题是两阶段随机最大加权匹配问题，这是 NP-hard，但我实际上需要某种“单阶段”随机最大加权匹配问题。

我正在寻找一种方法，该方法采用任意数量的 NSArray 对象，并返回该数组成员的所有可能完整组合的嵌套数组。

正如我在回答这个问题时被告知的那样，我正在寻找创建一个二分图，或者更准确地说，一个完整的二分图。

因此，例如，如果我有两个数组：

我想要一个采用这些数组的数组的方法：

并返回所有可能组合的数组，长度相同。所以，在这个例子中，我想要一个大致如下所示的数组：

随着这些数组中对象数量的增加，我相信结果的数量也会呈指数增长。然后我可能会将此方法作为 NSArray 上的一个类别。另外，我希望结果的长度都相同。也就是说，如果有三个源数组，则该方法返回的每个嵌套数组的长度都应为 3。

关于最优雅的方法的任何想法？

我需要一种算法来（有效地）解决我正在编写的一些图表软件中出现的问题。

我有两组节点，N 和 M。N 中的每个节点 n0 与 M 中的唯一（对于 n0）节点有 0 到 M 个连接。这些节点集将排列在两条平行的水平线上，N 个节点在 M 个节点上方的行中。连接将绘制为从 N 到 M 的直线。

我需要做的是在它们的水平线上重新排列 N 和 M 节点，以尽量减少交叉。他们有什么方法比简单地列举所有可能的安排更有效，即 O(N!*M!)？（实际上，它比这差得多，因为还必须检查每个连接是否交叉）。

也欢迎参考相关文献，尽管解释为什么需要它的相关性。

正如已经指出的，在一般情况下，这可以被认为是二分图（集合 N 和 M）平面化算法。然而，这个特定的问题比那个（我希望可以让它更快）受到更多的限制，并且需要产生额外的信息（这可能会使它变慢），如下所示：

1. 该图的限制是连接必须绘制为从 N 到 M 的直线。在图论中，这实际上意味着连接不能在 N 或 M 中的节点后面，只能在它们之间。因此，具有四个连接器的 2x2 案例可以在一般的二分图案例中进行平面化，但在我的图表中不能。

2. 额外的信息是，如果它不能被平面化，我仍然需要一个最小交叉的解决方案（或接近它）。通常，最小交叉算法与仅平面化的算法有很大不同。

当你的图有多个组件时，你如何找到最大的二分匹配？每个组件可以用两种方式着色。您如何确定两组 X 和 Y 以运行最大匹配例程？

我得到了一个包含许多单独组件的图表。每个组件都是二分的。如何将顶点分配到两组A中B，使两组之间的差异最小？

例子：

1：1 -> 2 ->3 -> 4 -> 5

2：6 -> 7 -> 8

最好的解决方案是

A = {1, 3, 5, 7}

B = {2, 4 ,6, 8}

另一个（非最佳）解决方案是

A = {1, 3, 5, 6, 8}

B = {2, 4, 7}

当图有许多单独的二分组件时，您如何解决这个问题？

在二分图中有一个表示连接的二元方阵。问题是：是否存在所有行到列的一对一映射？（需要明确的是，如果我使用的语言错误，完全连接的图可以满足这个要求，因为我们不仅限于一对一的映射）。

我写了以下内容。有没有更快的方法来实现这一点？

一位朋友向我提出了一个看似正确的猜想，但我们俩都无法提出证明。这是问题所在：

给定一个具有不相交的非空顶点集 U 和 V 的连通二部图，使得 |U|<|V|，所有顶点都在 U 或 V 中，并且没有连接同一集合中的两个顶点的边，则至少存在一条连接顶点 a∈U 和 b∈V 的边使得 degree(a)>degree(b)

证明 U 中至少有一个顶点的度数高于 V 中的 1 是微不足道的，但要证明存在一对存在连接它们的边却难倒我们。

考虑以下与图论相关的问题：

让 G 成为二分图。为了使问题更具体，假设 G 是两个集合的不相交并集，例如 I 和 S。假设

• I 代表姓​​名为 1、2、3、4、5、6、7、8、9、10 的个人
• S 代表技能，名称为 a、b、c、d、e、f、g、h。

所以，每个人都有一些技能，例如，

• 个人 1 具有技能 b、d、g 和 h，
• 个人 2 具有技能 a、f 和 h，
• 等等

[在示例中，数据是随机给出的]。

我们的目标是建立一个由来自I的最少数量的个人组成的团队，这样S中的每个技能都将在团队中得到体现，也就是说，对于 S 中的每个技能s ，都有一个具有该技能的团队成员小号_

这个问题有名字吗？解决它的有效算法是否已知？

我在二分图问题中遇到了最大匹配问题。问题是这样的：

给定一个有 m 个圆孔的板和一组 n 个圆盘。孔编号为 h ₁ , ..., h _m，圆盘编号为 d ₁ , ..., d _n。

我们有一个 m 行 n 列的矩阵 A。_{如果 h i}可以拟合 d _j（即 h _i的直径≥ d _j的直径），则 A[i][j] = 1 ，否则为 0。

鉴于任何孔最多只能包含一个圆盘的条件，我需要找到最大的孔盘拟合配置。

我读过这个问题可以建模为网络流量问题，但不能完全遵循。有人可以解释如何做到这一点吗？另外，是否有任何我可以查看的 C 代码？

我有以下代码，它是 BPM 的实现（来自图论的二分匹配）

该代码的定义cnt和目的如下。

给定一个表示为 m×n 矩阵的二分图，其中当当且graph[i][j]仅当从鸽子到洞true存在一条边时，计算可以找到洞的最大鸽子数量（每只鸽子一个）和最佳分配。ij

• graph[m][n], matchL[n],matchR[m]和seen[m]是全局数组。
• main()初始化matchL[]并matchR[]在-1所有组件中。

• main()对所有鸽子进行循环，i并在每次迭代中

  • 清除seen[]所有0组件
  • calls bpm(i) and increments the maxflow counter
  • bpm(i) returns true iff pigeon i can be assigned a hole

• cnt contains the number of happy pigeons.

In my case, cnt's value is output as 0. Does this graph algorithm work correctly or have I made some error?