algorithm - 二部图的优化

Question

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

提前致谢

Answer 1

这是一个 maximal matching problem那是solveable efficiently in bipartite graphs使用 maximal flow算法。

减少到最大流量很简单:

• 让您的原始图形为 (V,U,E) [其中 V,U 是边 - 一个用于'classes' 和一个给 'teachers' - 方向是 teacher->class]。
• 创建一个新图 G'，带有两个额外的顶点:s,t。
• 将s连接到所有教师，将所有类(class)连接到t。
• 为新图中的每条边指定容量 1。
• 运行最大流算法，返回整数结果(因为容量是整数，所以可以这样做)。
• (利润)