Часть 5. Алгоритмы на графах. тием, поскольку оно подводит нас ближе к компактной и элегантной реализации, кото­рая достигает обеих целей.

тием, поскольку оно подводит нас ближе к компактной и элегантной реализации, кото­рая достигает обеих целей.

Мы полагаем существование двух конкретных задач в рамках модели потоков в се­тях, а именно, задачи о максимальном потоке (maxflow) и задачи о потоке минимальной сто­имости (mincost-flow). Несложно будет обнаружить их определенную связь с описанными выше моделями решения задач, с моделью кратчайшего пути из главы 21, с LP-моделью (linear-programming model — моделью линейного программирования) из части 8, а так­же со множеством специальных моделей задач, в том числе и только что обсужденных.

На первый взгляд может показаться, что многие из этих задач не имеют ничего общего с задачами о потоках в сетях. Выявление зависимости между заданной задачей и извест­ными задачами часто является важным шагом при разработке подхода к решению этой задачи. Более того, этот шаг часто важен еще и потому, что мы должны иметь представ­ление о той хрупкой границе, которая отделяет тривиальные задачи от труднорешаемых задач, прежде чем предпринимать попытки разработки реализаций. Внутренняя структу­ра задач и различного вида зависимости между задачами, которые мы рассматриваем в этой главе, создают благоприятный контекст для выбора подхода к решению подобного рода задач.

В рамках приближенной классификации алгоритмов по категориям, которую мы на­чали в главе 17, алгоритмы, которые будут изучаться в этой главе, попадают в категорию " легко решаемых", поскольку у нас имеется простые реализации, которые гарантирова­но выполняются за время, пропорциональное полиному от размера сети. Другие реали­зации хотя и не гарантируют полиномиального времени выполнения в худшем случае, тем не менее, они компактны и элегантны и, как показала практика, пригодны для решения широкого круга практических задач, аналогичных обсуждаемым здесь. Мы рассмотрим их подробно, поскольку в дальнейшем они принесут нам несомненную пользу. Исследо­ватели по-прежнему заняты поиском более быстродействующих алгоритмов с тем, чтобы стали возможными крупные приложения, а также чтобы снизить себестоимость критичес­ких приложений. Идеальные оптимальные алгоритмы решения задач о потоках в сети, обеспечивающие максимально возможное быстродействие, еще ждут своих первооткры­вателей.

С другой стороны, известно, что некоторые задачи, которые сводятся к задачам о по­токах в сетях, решаются эффективнее с помощью специальных алгоритмов. В принципе, мы можем заняться реализацией и совершенствованием таких специализированных алго­ритмов. Однако, несмотря на то, что этот поход продуктивен в отдельных случаях, алго­ритмы решения множества других задач (отличных от тех, что решаются методом сведе­ния к потокам в сети) не существуют. Но даже в тех случаях, когда специализированные алгоритмы существуют, разработка реализаций, способных превзойти удачные програм­мы, в основе которых лежит задача о потоках в сетях, связана с существенными слож­ностями. Более того, исследователи продолжают работы по совершенствованию алгорит­мов решения задач о потоках в сетях, так что удачные алгоритмы этого типа вполне могут превзойти известные методы решения данной практической задачи.

С другой стороны, задачи о потоках в сетях представляют собой специальные случаи еще более общей LP-задачи, которые нам предстоит рассмотреть в части 8. И хотя мы могли воспользоваться (а многие так и делают) алгоритмом решения LP-задач для реше-