Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по дискретной математике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 106 RSS
←   Июль 2009   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/525
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

106 подписчиков
0 за неделю
←   Все выпуски   →

RusFAQ.ru: Дискретная математика


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный платный хостинг на базе Windows 2008

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Чемпионы рейтинга экспертов в этой рассылке

Гордиенко Андрей Владимирович
Статус: Специалист
Рейтинг: 677
∙ повысить рейтинг >> 		_Ayl_
Статус: 8-й класс
Рейтинг: 601
∙ повысить рейтинг >> 		Galinab222
Статус: 5-й класс
Рейтинг: 263
∙ повысить рейтинг >>

∙ / НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Дискретная математика

Выпуск № 125 от 03.07.2009, 14:35
Администратор рассылки: Alexey G. Gladenyuk, Управляющий
В рассылке: подписчиков - 104, экспертов - 39
В номере: вопросов - 1, ответов - 1

Нам очень важно Ваше мнение об этом выпуске рассылки. Вы можете оценить этот выпуск по пятибалльной шкале, пройдя по ссылке:
оценить выпуск >>

Вопрос № 169969: Ув. эксперты помогите с решением задачи. http://pic.rapidshare.ru/1083225 Найти (хотя бы один) максимальный поток. Пожалуйста с разъяснением....

Вопрос № 169969:

Ув. эксперты помогите с решением задачи.
http://pic.rapidshare.ru/1083225
Найти (хотя бы один) максимальный поток. Пожалуйста с разъяснением.

Отправлен: 28.06.2009, 14:32
Вопрос задал: Roland Deschain, Посетитель
Всего ответов: 1
Страница вопроса >>

Отвечает Гордиенко Андрей Владимирович, Специалист :
Здравствуйте, Roland Deschain.

Анализируя рисунок, устанавливаем, что крайняя левая вершина сети является ее истоком s, крайняя правая – стоком t. Промежуточные вершины сети обозначаем буквами a, b, d, следуя снизу вверх. В соответствии с рисунком пропускные способности дуг следующие:
c(s, d) = 2, c(s, b) = 4, c(s, a) = 5, c(d, b) = c(b, d) = 1, c(b, a) = 3, c(d, a) = 1, c(a, d) = 2,
c(d, t) = 3, c(a, t) = 6,

Для решения задачи используем алгоритм Форда-Фалкерсона, который заключается в выполнении следующей последовательности действий:
1) ищется любая цепь из истока в сток;
2) каждой дуге приписывается возможный больший поток из истока в сток, который записывается в виде дроби с числителем, равным пропускной способности, и знаменателем, равным потоку дуги;
3) если поток равен весу дуги, то эта дуга является насыщенной, и через нее нельзя пройти при рассмотрении цепей в графе;
4) перебираются все возможные цепи, позволяющие попасть из истока в сток.

Поток в сети равен сумме потоков всех дуг, инцидентных стоку графа.

По указанному алгоритму рассмотрим следующие цепи:
s – a – t,
s – b – d – t.

Расставим потоки у дуг.



Далее выбираем цепи так, чтобы насыщались дуги, инцидентные истоку
s – b – a – d – t (здесь поток каждой дуги увеличивается на 2),
s – d – a – t (здесь поток каждой дуги увеличивается на 1).

Расставим потоки у дуг.



В итоге обе дуги, инцидентные стоку, оказались насыщенными. Резервов для увеличения потока в сети нет.

Максимальный поток равен сумме потоков через дуги (a, t) и (d, t): П = 6 + 3 = 9.

С уважением.
-----
Пусть говорят дела

Ответ отправил: Гордиенко Андрей Владимирович, Специалист
Ответ отправлен: 29.06.2009, 19:03

Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 251636 на номер 1151 (Россия) | Еще номера >>
  • Отправить WebMoney:
    • Вам помогли? Пожалуйста, поблагодарите эксперта за это!

    Нам очень важно Ваше мнение об этом выпуске рассылки. Вы можете оценить этот выпуск по пятибалльной шкале, пройдя по ссылке:
    оценить выпуск >>

    подать вопрос экспертам этой рассылки >>

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)
    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров >>

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

    © 2001-2009, Портал RFpro.ru, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Автор: Калашников О.А. | Программирование: Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2009.6.3 от 20.06.2009
    В избранное