По данной матрице пропускных способностей дуг Ω графа G найти максимальный поток от вершины s=x1 до вершины t=x7 и указать минимальный разрез, отделяющий s от t.

       x1 x2 x3 x4 x5 x6 x7
     x1 - 9  -  11 -  17 -
     x2 - -  6  -  8  -  12
  Ω= x3 - -  -  -  -  -  7
     x4 - 5  -  -  -  5  4
     x5 - -  -  -  -  7  -
     x6 - -  -  -  -  -  9
     x7 - -  -  -  -  -  -

задан 14 Июн '15 9:17

10|600 символов нужно символов осталось
1

Рассмотрим разбиение вершин на два подмножества: $%\{1;4;6\}$% и $%\{2;3;5;7\}$%. Из вершин первого множества в вершины второго суммарный поток не превосходит $%9+(5+4)+9=27$%. Такой поток можно построить при помощи алгоритма Форда - Фалкерсона.

Поток у меня получился такой (надо иметь в виду, что сам вид потока не обязательно однозначен -- важно, чтобы он был максимальным): $%1\to2(9)$%, $%1\to4(9)$%, $%1\to6(9)$%, $%2\to3(5)$%, $%2\to7(9)$%, $%3\to7(5)$%, $%4\to2(5)$%, $%4\to7(4)$%, $%6\to7(9)$%.

Таким образом, построен максимальный поток и минимальный разрез.

ссылка

отвечен 14 Июн '15 15:01

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,037

задан
14 Июн '15 9:17

показан
808 раз

обновлен
14 Июн '15 19:52

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

по почте:

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

по RSS:

Ответы

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

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