Дискретная математика, Потоки в сетях Опции

[Малышка]

Помогите пожалуйста решить задачки...

1. Для заданной сети найти максимальный поток и минимальный разрез, отделя.щий исток от стока. Истоком является вершина1, стоком-вершина2. В качестве начального потока взять поток по одному из путей из истока в сток.

2. Задана матрица (aij) эффективности выполнения i-ым рабочим j-ой работы. Расставить рабочих по работам так, чтобы min(aij)--max(задача о назначении рабочих на конвейер). первоночальную расстановку рабочих по работам выполнить так: i рабочий назначается на i работу.

3. Задана матрица (aij)-стоимости доставки единицы груза от производителя i к потребителю j. Предложение a(i) производителя и спрос b(j)-потребителя единицы груза задаются в виде таблицы:
Найти план перевозок fij


333.doc - удален! См. правила!

Сообщение отредактировано: APAL - 18.02.2006 22:27

[Малышка]

Atos, прости, но мне кажется что в первой задачки.... твоё решение.. в третьей итерации ошибка...

3 итерация. Вершину 1 помечаем [+s, бесконечность]. Вершину 2 помечаем [+1, 5-3=2]. Вершину 4 помечаем [+1, 5] Вершину 3 помечаем [+2, 3-2=1] Вершину 4 помечаем [+1, 5] Вершину 5 помечаем [+4, 6-2=4].

Кажется, что 5 вершина получает пометку [+4, 4-2=2]... может я ошиблась? Посмотри, пожалуйста...
И еще... ты написал про вершину 4 два раза... это опечатка твоя, или так и надо?

Сообщение отредактировано: Малышка - 23.02.2006 15:19