Примечаниe: если граф - неориентированный, то все матрицы Dm являются симметричными, поэтому достаточно вычислять элементы, находящиеся только выше (либо только ниже) главной диагонали.
Алгоритм построения деревьев
Пусть имеется некоторый граф G и каждому его ребру (х, у) поставлено в соответствие число m(x, y), которое называется его весом.
Вес дерева определяется как сумма весов составляющих его ребер. Для графа G необходимо построить покрывающее дерево минимального веса.
Алгоритм построения минимального покрывающего дерева
Просматривают ребра графа G в порядке возрастания их весов. Если ребро включается в покрывающее дерево, то его окрашивают в голубой цвет, в противном случае – в оранжевый цвет. Ребра, включенные в дерево, образуют граф, состоящий из нескольких компонент. Если концевые вершины просматриваемого ребра принадлежат одной и той же компоненте, то ребро образует цикл с ребрами, ранее включенными в дерево. Такое ребро не включают в дерево. В противном случае ребро включают в дерево. Вершины одной связной компоненты составляют букет.
1. Берут любое ребро, не являющееся петлей. Окрашивают его в голубой цвет, а его концевые вершины включают в первый букет.
2. Выбирают неокрашенное ребро.
Если его концевые вершины принадлежат одному и тому же букету, то окрашивают ребро в оранжевый цвет. Если ни одна из его концевых вершин не принадлежит ни одному из букетов, то включают их в новый букет и окрашивают ребро в голубой цвет. Если концевые вершины принадлежат разным букетам, то объединяют эти букеты в один и окрашивают ребро в голубой цвет. Если один конец ребра принадлежит некоторому букету, а второй не входит ни в один букет, то нужно включить второй конец в тот же букет и окрасить ребро в голубой цвет.
3. Заканчивают процедуру, если все вершины графа вошли в один букет. В противном случае переходят к шагу 2.
Число шагов при выполнении алгоритма конечно, так как оно не превышает числа ребер графа. Если голубые ребра не образуют покрывающего дерева, то у исходного графа его нет.
Пример. В новом районе имеется шесть жилых массивов. Нужно соединить их между собой дорогами, стоимость прокладки которых была бы минимальна. В следующей таблице приведены стоимости постройки дорог между каждой парой жилых массивов:
|
Решение задачи запишем в виде следующей таблицы:
Построено покрывающее дерево, вес которого равен 25 (рис, 1.22). |
Задачи сетевого планирования
Сетевое планирование применяют для организации и составления календарных планов реализации больших комплексов работ. Это, например, научно-исследовательские работы с участием нескольких институтов, разработка автоматизированной системы бухгалтерского учета, строительство большого объекта и т. д. Управление всеми этими работами можно осуществлять с помощью метода критического пути. Использование этого метода позволяет сравнительно просто выяснить, когда необходимо начинать и заканчивать выполнение отдельных операций, как задержка хода выполнения некоторой операции влияет на время завершения всего проекта.
Для использования метода критического пути нужно прежде всего разбить крупный проект на отдельные операции и составить перечень операции. Некоторые из них могут выполняться одновременно, другие – только в определенном порядке. Например, при строительстве дома нельзя возводить стены раньше, чем сделан фундамент. Необходимо выяснить очередность выполнения всех операций списка. Для этого составляют список операций, непосредственно предшествующих каждой операции. После этого нужно запланировать время, необходимое для выполнения каждой операции. Полученные данные обычно помещаются в таблицу. В табл. 11.1 приведены данные для проекта, состоящего из шести работ. Для каждой из них задана продолжительность и указаны непосредственно предшествующие ей операции.
При построении графа каждую операцию изображают в виде ориентированной дуги. Связи между операциями также представляются в виде дуги. Дугу-связь проводят из конца дуги, соответствующей предшествующей операции, в начало следующей операции. Чтобы отличить операции от связей, операции изображают сплошными линиями, а связи – пунктирами. Вершины графа называют событиями. Временем наступления события считают время, когда завершено выполнение всех операций, входящих в соответствующую вершину.
|
|
Граф, представляющий взаимосвязь отдельных работ проекта, называется сетевым графиком. На рис. 1.23. построен сетевой график для комплекса операций, задаваемых таблицей.
Большое количество дуг в сети усложняет решение задачи. Поэтому прежде всего нужно упростить полученную сеть. Для этого можно выбросить некоторые дуги-связи. Начало и конец выбрасываемой дуги объединяют в одну вершину. При этом нужно проверять, не нарушится ли порядок выполнения операций после выбрасывания дуги. Проверку проводят по таблице, задающей проект.
Задание на лабораторную работу
1. Ознакомиться с методами решения задач с сетевым представлением.
2. В соответствии с вариантом задания, определенным преподавателем, составить программы, реализующие метод решения.
3. Оформить отчет о выполнении задания с приведением условия задачи, алгоритмов и программ указанных методов, результаты решения.
Варианты заданий
1. В модульных перевозках груженые трейлерные платформы перевозятся по железной дороге между специальными перевалочными железнодорожными терминалами, где платформы снова присоединяются к трейлерам и далее следуют к потребителям автомобильным ходом. На рис. 1 показаны основные железнодорожные терминалы Соединенных Штатов и существующие железнодорожные пути между ними. Выделите сегменты железных дорог так, чтобы были связаны все железнодорожные терминалы и была минимизирована суммарная стоимость перевозок трейлерных платформ (стоимость перевозок пропорциональна длине железнодорожных путей).
Рис. 1
2. Ha рис. 2 показаны расстояния между платформами, добывающими газ в открытом море, и приемным пунктом, расположенным на берегу. Поскольку платформа 1 ближе остальных к берегу, она оснащена необходимым оборудованием для перекачки газа от остальных платформ к приемному пункту. Спроектируйте сеть трубопроводов минимальной длины, соединяющую приемный пункт со всеми добывающими платформами.
Рис. 2
3. Предположим, что в предыдущей задаче (рис. 2) все добывающие платформы разбиты на две группы в зависимости от давления газа в скважинах: к группе с высоким давлением газа относятся платформы 2, 3, 4 и 6, с низким давлением —5, 7, 8 и 9. Из–за разницы в давлении газопроводы от платформ разных групп нельзя соединять между собой. В то же время газопроводы от этих групп могут подсоединяться к приемному пункту через платформу 1. Определите минимальную сеть трубопроводов для данной ситуации.
4. Компания производит 15 типов изделий на 10 станках. Компания планирует сгруппировать станки так, чтобы минимизировать "несходство" операций, выполняемых на каждой группе станков. Мерой "несходства" между станками i и у служит величина dy, вычисляемая по формуле
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
