Дана сеть

Нужно найти максимальный поток.

задан 1 Авг '13 22:01

изменен 3 Авг '13 23:23

Есть очень много алгоритмов для решения этой задачи. Посмотрите в Сети или в литературе по словам "теорема Форда' - Фалкерсона".

(2 Авг '13 5:56) falcao
10|600 символов нужно символов осталось
0

Дана сесть.

Сесть - это значит взять стул и сесть на него.

А если дана сеть.

То мало данных задачи, а точнее их совсем нет.

ссылка

отвечен 3 Авг '13 13:53

Сесть - это опечатка. Сама сеть с пропускными способностями ребер есть на рисунке по ссылке.

(3 Авг '13 14:00) falcao

А что такое поток сети?

Я если в микроэлектронике не разбираюсь, то и этот термин тоже не знаю.

(3 Авг '13 14:13) artem00

Если из второй вершины будет идти в пятую и всё, то будет
максимальный поток 9 единиц чего-то пропускать.

(3 Авг '13 14:18) artem00

С алгоритмом кое как разобрался. Максимальный поток через сеть равен 11. Получилось весьма странное распределение потока (4 дуги с нулевыми мощностями). Типа "ты туда не езжай, ты сюда езжай". Хотя провел 8 итераций используя все дуги, дабы приблизить к реальности и избежать пустых дуг. Вот что получилось http://savepic.org/4319017.jpg

(3 Авг '13 23:32) IviBring

Ничего приближать к реалности тут не надо. Число 11 - это максимальное значение, так как в последнюю вершину нельзя перекачать больше. То, что есть ребра с нулевым потоком - это нормально.

(4 Авг '13 7:34) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×338

задан
1 Авг '13 22:01

показан
926 раз

обновлен
4 Авг '13 7:34

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru