- Объяснял на днях студентам, как задача о совершенном паросочетании в двудольном графе сводится к задаче о максимальном целочисленном потоке в некоторой сети (это теория графов -- область дискретной математики). Если коротко, то в задаче о совершенном паросочетании есть N мальчиков и N девочек, и указаны пары мальчик-девочка, которые типа нравятся друг другу. А задача в том, чтобы разбить их на непересекающиеся пары, чтобы создать N типа счастливых семей. Только сейчас понял, почему публика так радовалась, когда речь пошла о потоках в сетях: "пусть поток пойдёт из мальчика b(i) в девочку g(j)", повторял лектор.
Чтобы оставлять комментарии
войдите на сайт
(
)
Назад