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

     Между вершинами, располагающимися в два столбца, дуги имеют очень
большую пропускную способность, а оставшиеся дуги имеют пропускную спо-
собность равную единице. После решения задачи граф имеет следующий вид
(рисунок 27).




                                 Рисунок 27
     Если представить, что один столбец это служащие, другой столбец вакан-
сии, а дуги между ними это всевозможные назначения на должности, то дуги
выделенные толстыми линиями представляют те назначения, которые нужно
сделать, что бы всех распределить.
    2.7 Результаты решения некоторых задач
     В качестве демонстрации возможностей работы программы, приведем
примеры решения некоторых задач. Далее рассмотрим три типа решаемых за-
дач, причем для каждого из типов укажем задачи различной сложности.
  2.7.1 Задачи на нахождение максимальной пропускной способности сети
     Задача №1. Эта задача демонстрирует решение достаточно простого
графа, для которого можно найти максимальную пропускную способность ана-
литически, используя алгоритм Форда-Фалкерсона. Она равна для данного гра-

                                       27