二极图的优化

Question

有两个集合，一个包含班级列表，另一个包含教师列表。每个老师都有一组班级。我们必须为一个特定的班级指派一名教师，这样教师所从事的班级数量就应该是maximum.Is 这个问题与任何优化算法有关？我找不到任何类似的算法。请帮助我得到的逻辑。

感谢在advane

Answer 1

这是一个 最大匹配问题 这就是 在双极图中有效求解 使用 最大流量 算法。

最大流量的减少很简单:

• 让你的原始图是（V，U，E）[其中V，U是边-一个为 'classes'和一个用于'teachers'-方向是teacher->class]。
• 创建一个新的图G'，附加两个顶点: s,t.
• 连接 s 给所有教师，并将所有班级连接到 t.
• 为新图中的每条边赋予容量1。
• 运行最大流算法，返回整数结果（因为容量是整数，所以可以完成）。
• (利润)