Форум программистов, компьютерный форум, киберфорум
Наши страницы
Мат. логика и множества
Войти
Регистрация
Восстановить пароль
 
Pupsometr
1 / 1 / 0
Регистрация: 12.08.2011
Сообщений: 40
1

Алгоритм Форда Фалкерсона

29.12.2012, 18:42. Просмотров 1001. Ответов 0
Метки нет (Все метки)

Помогите, пожалуйста!
Алгоритм Форда Фалкерсона


Вот мое решение:

Расставим пометки во втором графе (там, где дан поток).
1-я вершина (источник) всегда имеет пометку бесконечность - это означает, что второе число как угодно большое. Пометка вершины с номером 4 будет (+1,7). Это означает, что дуга (1,4) прямая, ненасыщенная и по ней можно “перевезти” дополнительно 7 единиц “груза”.
Далее пометим вершину 3, ее пометка будет (–4,3).
Это означает, что дуга (4,3) обратная, и, учитывая “разворот”, по ней можно дополнительно “перевезти” 3 единицы “груза”. Пометим вершину 5 (+3, 5). Таким образом, наш поток можно увеличить на 3 единицы, прибавляя эти 3 единицы к прямым дугам и вычитая из обратных с учетом возможного “разворота” обратных дуг.
Для нового потока, снова расставляем пометки. Мы видим, что для этого потока (кроме источника) можно пометить только 1 вершину: вершину 4 (ее пометка будет (+1,4)). Больше ничего пометить нельзя, так как из множества помеченных вершин (Y) в множество непомеченных вершин (Z) идет только одна прямая дуга (4;5). Эта дуга образует минимальное сечение, величина которого равна 11 условных единиц, и эта же величина равна величине потока.
Преподаватель не зачел
1) написал что пометка вершины 3 на первом этапе неверная, дополнил: можно перевезти больше единиц груза.
2) на втором этапе написал, что можно пометить и вершину 3 и вершину 5.

Если честно не совсем понимаю его ход мыслей, вроде делала все по алгоритму. Правильно ли я понимаю, если дана обратная дуга, то величина ее потока может быть только 0? Или же она может дойти до -8? ( и вообще корректен ли здесь будет -) Если несложно укажите как все-таки должно быть
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.12.2012, 18:42
Ответы с готовыми решениями:

алгоритм форда-фалкерсона
Доброго времени суток, как можно реализовать алгоритм Форда-Фалкерсона в...

Алгоритм Форда-Фалкерсона
Здравствуйте дорогие друзья, не завалялась ли у вас где-нибудь реализация...

Алгоритм Форда-Фалкерсона
Нужно за алгоритмом Форда-Фалкерсона рассщитать максимальный поток транспортной...

алгоритм Форда-Фалкерсона максимальный поток
какой компилятор лучше испольковать что бы запустить эту программу >...

Алгоритм Форда-Фалкерсона максимальный поток
Для определения потока в сети используют алгоритм Форда-Фалкерсона: а) ищем...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.12.2012, 18:42

Алгоритм Форда-Фалкерсона, максимальный поток в сети
Первое красное значение на пути это вес а второе поток. Проблема заключается в...

Алгоритм Форда-Фалкерсона, программа выводит ноль
в чем проблема?вроде матрица инициализируется раз выводит первоначальную...

Входные данные. Метод Форда-Фалкерсона
Доброго времени суток! Есть код, который работает и справляется с основной...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru