Определение. Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.
Пусть G связный граф. Тогда остовное дерево графа G (если оно существует) должно содержать n(G) – 1 ребер. Таким образом, любое остовное дерево графа G есть результат удаления из G ровно m(G)-(n(G)-1)=m(G)-n(G)+1 ребер.
Определение. Число m(G)-n(G)+1 называется цикломатическим числом связного графа G и обозначается через v(G).
Замечание. Понятие остовного дерева и цикломатического числа аналогичным образом определяется и для произвольного связного псевдографа G.
Покажем существование остовного дерева для произвольного связного псевдографа G=(V,X), описав алгоритм его выделения.
Шаг 1. Выбираем в G произвольную вершину u1, которая образует подграф G1 псевдографа G, являющийся деревом. Полагаем i=1.
Шаг 2. Если i=n, где n=n(G), то задача решена, и Gi – искомое остовное дерево псевдографа G. В противном случае переходим к шагу 3.
Шаг 3. Пусть уже построено дерево Gi, являющееся подграфом псевдографа G и содержащий некоторые вершины u1, …, ui, где 1didn-1. Строим граф Gi+1, добавляя к графу Gi новую вершину ui+1О V, смежную в G с некоторой вершиной uj графа Gi, и новое ребро (ui+1, uj) (в силу связности G и того обстоятельства, что i < n, указанная вершина ui+1 обязательно найдется). Согласно утверждению граф Gi+1 также является деревом. Присваиваем i:=i+1 и переходим к шагу 2.
Пример 87.
Используя алгоритм, выделим остовное дерево графа G, изображенного на рисунке 39.
ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ - Задача о нахождении на ориентированном графе пути наименьшей длины между двумя заданными его вершинами. Длиной пути такого графа называется сумма длин дуг, составляющих этот путь. Задача о кратчайшем пути возникает чаще всего при решении транспортных задач, дискретных задач динамического программирования и др. В задачах сетевых методов планирования и управления алгоритмы решения задачи о кратчайшем пути используют для нахождения критического пути. Известно несколько эффективных методов ее решения.
Задача О Кратчайшем Пути - задача о нахождении методом пути наименьшей длины между двумя заданными вершинами. Длиной пути такого графа является сумма длин дуг, составляющих этот путь. Чаще всего используется при решении транспортных задач.
Остовное дерево связного неориентированного графа — ациклический связный подграф данного графа, в который входят все его вершины. Неформально говоря, остовное дерево состоит из некоторого подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрами, и в нём нет циклов, то есть из любой вершины нельзя попасть в саму себя, не пройдя какое-то ребро дважды.
Понятие остовный лес неоднозначно, под ним могут понимать один из следующих подграфов:
· любой ациклический подграф, в который входят все вершины графа, но не обязательно связный;
· в несвязном графе — подграф, состоящий из объединения остовных деревьев для каждой его компоненты связности.
Остовное дерево также иногда называют покрывающим деревом, остовом или скелетом графа. Ударение в слове «остовный» у разных авторов указывается на первый (от слова о́стов) или на второй слог.
Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном, взвешенном, неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
Пример минимального остовного дерева в графе. Числа на ребрах обозначают вес ребер.
Задача о нахождении минимального остовного дерева часто встречается в подобной постановке: допустим, есть n городов, которые необходимо соединить дорогами, так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Разрешается строить дороги между заданными парами городов и известна стоимость строительства каждой такой дороги. Требуется решить, какие именно дороги нужно строить, чтобы минимизировать общую стоимость строительства.
Эта задача может быть сформулирована в терминах теории графов как задача о нахождении минимального остовного дерева в графе, вершины которого представляют города, рёбра — это пары городов, между которыми можно проложить прямую дорогу, а вес ребра равен стоимости строительства соответствующей дороги.
Алгоритм Краскала
Описание
Алгоритм Краскала изначально помещает каждую вершину в своё дерево, а затем постепенно объединяет эти деревья, объединяя на каждой итерации два некоторых дерева некоторым ребром. Перед началом выполнения алгоритма, все рёбра сортируются по весу (в порядке неубывания). Затем начинается процесс объединения: перебираются все рёбра от первого до последнего (в порядке сортировки), и если у текущего ребра его концы принадлежат разным поддеревьям, то эти поддеревья объединяются, а ребро добавляется к ответу. По окончании перебора всех рёбер все вершины окажутся принадлежащими одному поддереву, и ответ найден.
Существует несколько алгоритмов для нахождения минимального остовного дерева. Некоторые наиболее известные из них: алгоритм Прима; алгоритм Краскала (или алгоритм Крускала); алгоритм Борувки.
Сетевое планирование – метод управления, основанный на использовании математического аппарата теории графов и системного подхода для отображения и алгоритмизации комплексов взаимосвязанных работ, действий или мероприятий для достижения четко поставленной цели.
Разработаны в начале 50-х г. ХХ в. Наиболее известны практически одновременно и независимо разработанные метод критического пути - МКП и метод оценки и пересмотра планов - PERT. Применяются для оптимизации планирования и управления сложными разветвленными комплексами работ, требующими участия большого числа исполнителей и затрат ограниченных ресурсов.
Основная цель сетевого планирования - сокращение до минимума продолжительности проекта. Задача сетевого планирования состоит в том, чтобы графически, наглядно и системно отобразить и оптимизировать последовательность и взаимозависимость работ, действий или мероприятий, обеспечивающих своевременное и планомерное достижение конечных целей. Для отображения и алгоритмизации тех или иных действий или ситуаций используются экономико-математические модели, которые принято называть сетевыми моделями, простейшие из них - сетевые графики. С помощью сетевой модели руководитель работ или операции имеет возможность системно и масштабно представлять весь ход работ или оперативных мероприятий, управлять процессом их осуществления, а также маневрировать ресурсами.
Наиболее распространенными направлениями применения сетевого планирования являются:
· целевые научно-исследовательские и проектно-конструкторские разработки сложных объектов, машин и установок, в создании которых принимают участие многие предприятия и организации;
· планирование и управление основной деятельностью разрабатывающих организаций;
· планирование комплекса работ по подготовке и освоению производства новых видов промышленной продукции;
· строительство и монтаж объектов промышленного, культурно-бытового и жилищного назначения;
· реконструкция и ремонт действующих промышленных и других объектов;
· планирование подготовки и переподготовки кадров, проверка исполнения принятых решений, организация комплексной проверки деятельности предприятий, объединений, строительно-монтажных организаций и учреждений.
Использование методов сетевого планирования способствует сокращению сроков создания новых объектов на 15-20%, обеспечению рационального использования трудовых ресурсов и техники.