КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Решение. 2 страницаЧетвертый шаг: проделываем все операции для вершины 3: . ; . Метки для остальных вершин оставляем прежними. Метка для вершины 6 уменьшилась. Записываем меньшую. Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 4. .
Пятый шаг: проделываем все операции для вершины 4: . ; . Для вершины 2 расстояние не рассчитываем, т.к. она уже получила постоянную метку. Метки для остальных вершин оставляем прежними. Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 5. .
Шестой шаг: проделываем все операции для вершины 5: . ; ; ; ; Для вершины 4 расстояние не рассчитываем, т.к. она уже получила постоянную метку. Метки для остальных вершин оставляем прежними. Метки для вершин 6, 7, 8 уменьшились. Записываем меньшие. Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 6. .
Седьмой шаг: проделываем все операции для вершины 6: . ; Метки для остальных вершин оставляем прежними. Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 7. .
Восьмой шаг: проделываем все операции для вершины 7: . ; Метки для остальных вершин оставляем прежними. Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 8. . Для вершины 9 метка на девятом шаге не меняется, поэтому все результаты записываем в таблицу.
Таким образом, минимальные расстояния от вершины 1 ко всем вершинам графа равны: Задание 14. Найти максимальный поток в транспортной сети, изображенной на рисунке _____.
Рисунок ____. Решение. Длянахождения максимального потока воспользуемся алгоритмом Форда-Фалкерсона. Найдем суммарную пропускную способность дуг, выходящих из истока (вершина 1) и суммарную пропускную способность дуг, входящих в сток (вершина 14). ; . Значит, максимальный поток в этой сети не может превосходить 31. Далее разбиваем сеть на простые непересекающиеся цепи (произвольным образом). В данном случае удобно сделать это следующим образом: 1 – (1, 2, 6, 10, 14); 2 – (1, 3, 7, 11, 14); 3 – (1, 4, 8, 12, 14); 4 – (1, 5, 9, 13, 14). Для каждой из цепей находим максимальный поток, исходя из пропускных способностей дуг: например, в первой цепи – (1, 2, 6, 10, 14) – минимальная пропускная способность у дуги (2,6) – 6, поэтому поток по этой дуге не может превышать 6-ти. На рис. _____ показана сеть, в которой синим цветом обозначены простые цепи, а рядом с пропускными способностями дуг обозначено значение потока. Дуги, у которых пропускная способность равна потоку, называются насыщенными. На первой итерации получаем суммарный поток: 6+5+6+4=21. На следующих итерациях будем пытаться увеличить величину потока.
Рисунок ____ – первая итерация.
Для этого выбираем другие цепи, в которых нет насыщенных дуг. На рисунках _______ изображены последующие итерации. (Над дугой рядом с пропускными способностями дуг через «;» обозначаем новое значение потока). Вторая итерация: выбираем цепь, по которой можно увеличить поток: (1, 2, 3, 6, 10, 14). Поток можно увеличить на 1 (т.к. пропускная способность дуги (6, 10) равна 7).
Рисунок ____ – вторая итерация.
На второй итерации поток увеличился на 1, и стал равен 22. Третья итерация: выбираем цепь (1, 3, 8, 7, 10, 14). По этой дуге мы можем пропустить поток величиной 2 (т.к. пропускная способность дуги (3,8) равна 2). Получаем суммарный поток, равный 22+2=24. На рис. ____ изображена сеть с потоком, равным 24.
Рисунок ____ – третья итерация.
Четвертая итерация: выбираем цепь (1, 4, 9, 13, 14). По этой дуге мы можем пропустить поток величиной 1 (т.к. пропускная способность дуги (9, 13) равна 5). Получаем суммарный поток, равный 24+1=25. На рис. ____ изображена сеть с потоком, равным 25.
Рисунок ____ – четвертая итерация.
Задание 9. Доказать справедливость соотношения .
Дата добавления: 2014-11-20; Просмотров: 420; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |