Алгоритмы на графах и их приложения. Дорофеева В.И. - 8 стр.

телям, минимизирующими суммарные расходы по перевозке. Однако скоро вы-
яснилось, что методы, развитые при анализе такого рода задач, приложимы и к
другим сетевым проблемам, например к задачам об информационных потоках в
сетях связи или к задачам о дорожных транспортных потоках. Более того, обна-
ружилось, что целый ряд прикладных комбинаторных задач, не связанных с ре-
ально существующими сетями, допускает, тем не менее, изящное математиче-
ское решение на языке сетевых моделей.
       На практике часто возникает задача максимизации потока некоего про-
дукта между двумя заданными узлами сети при условии, что поток вдоль каж-
дой дуги ограничен. Очевидный пример – поток городского транспорта.
       Приведем основные определения из теории потоков в сетях.
       Транспортной сетью называется ориентированный граф G=(E,U) с
множеством вершин E и множеством дуг U, для которого выполняются усло-
вия:
       1) существует одна и только одна вершина X0, в которую не заходит ни
         одна дуга из множества U;
       2) существует одна и только одна вершина XN, из которой не исходит ни
         одной дуги;
       3) каждой дуге u∈U поставлено в соответствие целое число c(u)≥0, на-
         зываемое пропускной способностью дуги.
       Х0 называют входом (источником) сети, ХN – выходом (стоком), а c(u) –
пропускной способностью дуги u. На рисунке 3 изображен граф, являющийся
транспортной сетью
       Поток в транспортной сети. Функцию ϕ(u), определенную на множест-
ве U, называют потоком в транспортной сети, если:
       1. (∀u∈U)ϕ(u)≥0,
       2. (∀Xi≠0 и ≠XN)    ∑ ϕ (u) = ∑ ϕ (u)
                          u∈U -    u∈U +
                              xi       xi




                                            8