我有一个在二分图中找到有效匹配的问题。
设一个二部图，每组有 N 个顶点，我有一组未加权的边，将一组中的顶点连接到另一组中的顶点，并且 not 第 1 组中的每个顶点都连接到每个顶点在第 2 组中。
我的问题是在图中找到所有有效匹配（或者至少一些匹配，如果不是全部），其中“valid matching”匹配第 1 组中的所有顶点与第 2 组中与现有连接的任何顶点边和第 2 组中的任何顶点都与第 1 组中的任何顶点匹配。
当然天真的解决方案是遍历所有N个阶乘匹配并找到与当前边真正存在的匹配，但是当N大于10甚至50时，阶乘发散，我需要找到一些具有多项式时间的算法复杂性。
我尝试了一些复杂性不够好的启发式方法，我尝试按顺序对每个顶点进行随机匹配采样，即遍历第 1 组中的所有顶点，对第 2 组中的每个连接顶点进行采样并将其从图中删除，以便没有顶点会匹配两次。这种方式非常糟糕，因为当 N 大到 50 时，大多数寻找匹配的尝试都无法匹配所有顶点。
我在考虑一些使用递归的直观方法，但这个想法并不完整，我很乐意得到另一个想法。