среда, 28 марта 2012
00:57

помогите найти максимальный поток

все записи пользователя в сообществе fenix0093
с подробным решением

читать дальше

@темы: Теория графов, Дискретная математика

URL
Комментарии
28.03.2012 в 01:04

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
fenix0093, Вы ведь "не первый раз замужем"...
Спрячьте картинку под More...

И хотелось бы увидеть Ваши попытки...
URL
28.03.2012 в 01:09

fenix0093
в результате получается, что при построении полного потока не существует пути из истока в сток
URL
28.03.2012 в 01:15

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Путей много и все они несут часть потока... Ведь максимальный поток не означает, что всё должно течь через одну трубу...

Кстати, каким методом решаете?...
URL
28.03.2012 в 01:18

fenix0093
нужно применить алгоритм Форда - Фалкерсона
полный поток нашел:
v1, v2 = 4
v1, v3 = 1
v1, v5 = 5
v2, v4 = 1
v3, v6 = 2
v5, v7 = 10

что дальше делать - непонятно
URL
28.03.2012 в 02:04

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Как я понимаю алгоритм Форда - Фалкерсона является итерационным... а Вы сразу оптимум нашли?...

Если это полный поток осталось проверить оптимальность и найти величину потока... то есть оформить ответ...
URL
28.03.2012 в 02:09

fenix0093
нужно еще индексы какие-то расставлять
URL
28.03.2012 в 02:19

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Какие индексы?... их может быть много: насыщаемость дуги... или индексы, которые указывают на оптимальность...
URL
28.03.2012 в 02:30

fenix0093
насыщаемые дуги, потом еще минимальный разрез определить надо
URL
28.03.2012 в 02:37

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Ну, если Вы этого не сделали, то откуда уверенность, что записанный вами поток - полный?...

Возьмите с полок сообщества eek.diary.ru/p70169845.htm книгу Кузнецов, Саакович, Холод "Математическое программирование" там есть пример задачи с этим алгоритмом...
URL