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

http://feedproxy.google.com/~r/bashorg_russian/~3/5V_9Urs0_Ds/445462