оптимизация двудольного графа

Question

Существует два набора, один из которых содержит список классов, а другой - список учителей.У каждого учителя есть набор классов.Мы должны назначить преподавателя для определенного класса таким образом, чтобы количество занятий, проводимых преподавателями, было максимальным.Связана ли эта проблема с каким-либо алгоритмом оптимизации?Я не смог найти ни одного подобного алгоритма.Пожалуйста, помогите мне разобраться в логике.

Заранее спасибо

Answer 1

Это настоящий задача о максимальном совпадении это эффективно разрешимый в двудольных графах используя максимальный расход алгоритмы.

Приведение к максимальному расходу простое:

• Пусть ваш исходный график равен (V, U, E) [где V, U - ребра - одно для "классы" и одно для "учителей" - направление учитель-> класс].
• Создайте новый граф G' с дополнительными двумя вершинами: s,t.
• Контакты s ко всем учителям и подключите все классы к t.
• Укажите емкость, равную 1 для каждого ребра в новом графике.
• Запустите алгоритм максимального потока, который возвращает целочисленный результат (поскольку емкости являются целыми числами, это можно сделать).
• (прибыль)