45. Изложите алгоритм Форда- Фалкерсона для нахождения максимального потока.

Теорема Форда-Фалкерсона

В любой сети максимальная виличина потока из источника Ео(Еn)равна минимальной пропускной способностью разреза, отделяющего Ео от Еn.

Алгоритм Форда-Факерсона нахождения максимального потока.

Предварительный шаг:

Записываем пропускные способности дуг сети в таблицу размерности (n+1)x(n+1), где n+1 – коллічество вершін сеті G(E,e). Если пропускная способность дуг (Ei,Ej) больше нуля, а семметричной ей дуги (Ej,Ei) равна нулю, то в клетку (i,j) заносится элемент bij , а в клетке (j,i) ноль, если же bij=bji=0 , то клетки (i,j) и (j,i) не заполняются.

Общий шаг:

Заключительный шаг должен быть таким образом, что не будет возможно найти следующий путь. Для проверки правильности необходимо будет сложить значения Ео столбца и Е4 строки как проиллюстрировано на рисунке, после чего сравнить с первой таблице если числа будут одинаковы (знаки не сморим) то мы всё сделали правильно.

46. Изложите принципы решения задачи с несколькими источниками и несколькими стоками.

В задаче о максимальном потоке может быть несколько источников и стоков. Для преобразования задачи о максимальном потоке с несколькими источниками и несколькими стоками к задаче с одним источником и одним стоком добавляется фиктивный источник и ориентированные ребра с пропускной способностью 0 для каждого Точно так же создается новый фиктивный сток и добавляются ориентированные ребра 0 для каждого. Единственный источник просто обеспечивает поток любого требуемого объема к другим источникам, а единственный сток аналогичным образом потребляет поток любого желаемого объема от множественных первоначальных стоков.

47. Дайте определения основных понятий сетевого графика комплекса операций.

Сетевой график представляет собой ориентированный граф без контуров дугам или вершинам которого, которого приписаны некоторые числовые значения.

Виды работ

Действительная работа в прямом смысле слова (например — подготовка трассы соревнований), требующая затрат труда, материальных ресурсов и времени;

Ожидание — работа не требующая затрат труда и материальных ресурсов, но занимающая некоторое время;

Фиктивная работа (Зависимость) — связь между двумя или более событиями, не требующая затрат труда, материальных ресурсов и времени, но указывающая, что возможность начала одной операции непосредственно зависит от выполнения другой. Продолжительность такой работы = 0.

Всякая работа в сети соединяет два события: предшествующее (являющееся для нее начальным) и следующее за ней (конечное).

Виды событий

Исходное событие — начало выполнения комплекса работ;

Завершающее событие — конечное событие, означающее достижение конечной цели комплекса работ;

Промежуточное событие, как результат одной или нескольких работ, представляющих возможность начать одну или несколько непосредственно следующих работ. Продолжительность промежуточного события во времени всегда = 0.

Событие определяет состояние, а не процесс.

Пути

Любая последовательность работ в сетевом графике, в котором конечное событие каждой работы этой последовательности совпадает с начальным событием следующей за ней работой, называется путем. Пути в сетевом графике могут быть трех видов:

Полный путь — начало которого совпадает с исходным событием сети, а конец — с завершающим, называется полным путем;

Путь, предшествующий событию — путь от исходного события сети до данного события;

Путь, следующий за событием — путь, соединяющий событие с завершающим событием;

Путь между событиями i и j — путь, соединяющий какие-либо два события i и j, из которых ни одно не является исходным или завершающим событием сетевого графика;

Критический путь — путь, имеющий наибольшую продолжительность от исходного события до завершающего. (см. Метод критического пути)