КАТЕГОРИИ: Архитектура-(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) |
Пример задачи о многополюсном максимальном потоке
Рассмотрим сеть изображенную на рисунке п1.4. Числа, приписанные дугам, соответствуют их пропускным способностям. Требуется для каждой пары узлов сети определить величину максимального потока между ними. Рис.п1.4. Сеть в задаче о многополюсном максимальном потоке. Данная задача решается за интеграций алгоритма Гомори – Ху. Если процедура расстановки пометок поменялась бы к каждой паре узлов, то потребовалось бы решить 21 задачу о максимальном потоке. Разрезы, построенные на каждой итерации, состоят из дуг, остаточная пропускная способность которых равна нулю. Для простоты изложения мы опустили результаты, полученные при выполнении процедур расстановки пометок. Итерация 1. Рассмотрим узлы s=2 и t=5. Величина максимального потока равна 13. Поэтому . По разрезу с минимальной пропускной способностью мы определяем, что построение дерева разрезов можно начать с ветви, соединяющей узел 5 и конденсированные узел, состоящий из узлов 1, 2, 3, 4, 6, 7 (рис п1.4а). Вес данной ветви равен 13. Рис.п1.4а. Задача о максимальном потоке: первая итерация. Итерация 2. Рассмотрим узлы s=1 и t=2. Величина максимального потока равна 19. Поэтому . По минимальному разрезу мы определяем, что узлы 2 и 5 лежат по одну его сторону, а все остальные узлы сети – по другую сторону этого разреза (рис.п1.4б). Вес ветви, соединяющий узел 2 и конденсированный узел, состоящий из узлов 1, 3, 4, 6 и 7, равен 19.
Рис.п1.4б. Вторая итерация.
Итерация 3. Рассмотрим узлы 6 и 7. Величина максимального потока Равна 21. Поэтому . По минимальному разрезу мы определяем, что узел 7 в дереве разрезов соединяется с конденсированным узлом, состоящим из узлов 1, 3, 4, 6, дугой, вес которой равен 21. Кроме того, узлы 2 и 5 и конденсированный узел(1, 3, 4, 6) расположены по одну сторону минимального разреза, а узел 7 – по другую сторону этого разреза (рис.п1.4в).
Рис.п1.4в. Третья итерация. Итерация 4. Рассмотрим узлы s=4 и t=6. Величина максимального потока равна 25. Поэтому . По минимальному разрезу видно, что узлы 6 и 7 расположены в той же части дерева разрезов, что и узел (1, 3, 4) (рис.п1.4г). Рис.п1.4г.Четвертая итерация. Итерация 5. Рассмотрим узлы s=1 и t=4. Величина максимального потока равна 24. Поэтому . Определяя минимальный разрез, удаляем узел 1 из узла (1, 3, 4) и располагаем его по ту сторону узла (3, 4), где не находится ни один из оставшихся узлов (рис.п1.4д). Вес соответствующей дуги в дереве разрезов равен 24. Рис.п1.4д. Пятая итерация. Итерация 6. Рассмотрим узлы s=3 и t=4. Величина максимального потока равна 22. Поэтому . Найдя минимальный разрез, удаляем узел 3 из узла (3, 4) и соединяем его с узлом 4 дугой дерева разрезов, вес которой равен 22. Теперь дерево разрезов стало полным, т.е. состоит из шести дуг. Поэтому процедура заканчивается (рис.3.4е). Рис.п1.4е. Шестая итерация. Величины максимальных потоков можно записать в виде следующей матрицы:
Приложение 2 Задача об остовном дереве Перед тем как перейти к изучению этой новой потоковой задачи, остановимся на определениях, которые имеют непосредственное отношение к нахождению доминирующего остовного дерева. Назовем деревом связное множество неориентированных ребер (дуг), не содержащее циклов. Таким образом, если задано множество т узлов, соединенных неориентированными ребрами, то для построения дерева необходимо выделить подмножество, состоящее из т—1 дуги. Иными словами, каждый узел соединен с другим узлом одним-единственным путем. Рассмотрим сеть, содержащую п узлов, совокупность которых образует множество S.Остовным деревом называется связное множество, состоящее из (п—1) дуг (ребер) и п узлов. Из любого собственного подмножества множества S может быть образовано дерево. Будем предполагать, что каждой дуге, соединяющей узлы i и j из множества S, приписано число сij, называемое расстоянием, или весом, дуги. Теперь мы можем ввести понятие максимального доминирующего остова. Доминирующим остовом называется такой остов сети, у которого сумма весов сij всех его дуг максимальна.
Построение доминирующего остова встречается в задачах синтеза структуры сети по методу Гомори-Ху. Алгоритм построения доминирующего остова Шаг 1. Используя узлы исходной сети, определить следующие два множества: S — множество соединенных узлов; — множество несоединенных узлов. Вначале все узлы будут принадлежать множеству . Шаг 2. Выбрать произвольный узел из и соединить его с ближайшим соседним узлом дугой максимального веса. (После выполнения данного шага множество S будет содержать два узла.) Шаг 3. Среди всех дуг, соединяющих узлы из множества S с узлами из множества , выбрать дугу максимального веса. Концевой узел этой дуги, лежащий в S, обозначить через б. Удалить узел б из множества и поместить его в множество S. Шаг 4. Выполнять шаг 3 до тех пор, пока все узлы не будут принадлежать множеству S. Пример решения задачи из главы 9 Построить остовное дерево доминирующих потоков для ниже приведенной сети (рис.11.3) Рис.П.2.1. Пример сети в задаче о кратчайшем остове Шаг 1. = (1, 2, 3, 4, 5, 6, 7), S = 0. Шаг 2. Выбрать узел 6. Соединим дугой максимального веса с узлом 7 S = (6, 7) Стоимость = 7 ед. = (1,2,3,4,5). Шаг 3. а) Выбрать узел 5. S= (6, 7, 5), = (I, 2, 3, 4). б) Выбрать узел 2. S= (6, 7, 5,2), = (I, 3, 4) в) выбрать узел 3. S= (6, 7, 5, 2, 3), = (I, 4). г) выбрать узел 1. S= (6, 7, 5, 2, 3, 1), = (4).
д) Выбрать узел 4. S= (6, 7, 5, 2, 3, 1, 4), = 0.
ПРИМЕНЕНИЯ ЗАДАЧИ О КРАТЧАЙШЕМ ОСТОВЕ Задача о кратчайшем остове (ЗКО) находит широкое практическое применение. Многие задачи, на первый взгляд не похожие на ЗКО, после некоторых преобразований сводятся к ней. С помощью построения кратчайшего остова, например, Д. Росси, Хейзер и Кинг, предложили схему прокладки телевизионных кабелей, соединяющих все станции в единую сеть. Но наиболее интересное и важное применение ЗКО, по-видимому, находит в кластерном анализе, где ряд задач, решающихся другими методами этого анализа, наиболее эффективно решаются с помощью построения КО. Другое применение ЗКО находит при оценке надежности сетей: вес КО соответствует минимальной вероятности того, что дерево будет повреждено в одной или нескольких дугах. Гомори и Ху, использовали алгоритм построения КО при решении задач о многополюсных потоках. Хелд и Карп, нашли аналогичное применение ЗКО для решения задачи коммивояжера.
Приложение 3.
Дата добавления: 2014-01-07; Просмотров: 2942; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |