Максимальный поток двухсторонний с промежуточными узлами

Question

Я работаю над проблемой, когда нужно создать расписание экзаменов на основе некоторых ограничений, создав сеть потоков.

• Набор количество курсов C
• Набор количество дней D
• Набор количество комнат R
• Отображение студентов S на их курсы

Если студент проходит курс c1 и c2, два экзамена не могут проводиться одновременно.

У меня возникли проблемы с созданием сети потоков из этих ограничений. Это одна из сетей, которые я пытался сделать до сих пор.

Черные узлы являются источником и раковиной. Красный студентов. Зеленые курсы. Оранжевые - это дни. Синие номера.

Цифры представляют пропускную способность.

После создания соответствующего графика потока я знаю, что я бы использовал алгоритм Форда-Фулкерсона, чтобы найти максимальный поток.

Answer 1

Это не проблема потока. Это на самом деле NP-полный; вы можете уменьшить проблему окраски графа к ней следующим образом:

Возьмите в качестве набора курсов набор вершин графа в вашем экземпляре раскраски графа. Для каждого ребра в этом графе, скажем, между u и v, создайте ученика, который принимает только курсы u и v. У вас ровно столько временных интервалов, сколько доступных цветов.

Тогда допустимое расписание (когда ни один студент не имеет обоих экзаменов одновременно) будет окрашивать ваш график.

Возможно, вам удастся построить целую модель программирования вашей проблемы.