10

Во многих задачах, решаемых с использованием графов, требуется проложить маршрут от одной вершины графа к другой или обойти все его вершины, учитывая те или иные ограничения.

Прежде всего, надо уточнить термины "маршрут", "цепь", "цикл" и "путь". Эти четыре понятия находятся в следующем соотношении: пути и циклы – это особые виды цепей, цепь – особый вид маршрута.

Еще раз повторим эти понятия, перефразировав их.

Маршрут – это последовательность вершин и ребер графа, следуя по которым, можно попасть из одной его вершины в другую.

Маршрут в графе — это чередующаяся последовательность вершин и рёбер v₀,e₁,v₁,e₂,v₂,...,e_k,v_k, в которой любые два соседних элемента инцидентны. Если v₀ = v_k, то маршрут замкнут, иначе открыт.

Цепь – это маршрут без повторяющихся ребер.

Цепь в графе — маршрут, все рёбра которого различны. Если все вершины (а тем самым и рёбра) различны, то такая цепь называется простой (элементарной). В цепи v₀,e₁,...,e_k,v_k вершины v₀ и v_k называются концами цепи.

Цикл – это цепь, у которой совпадают начальная и конечная вершины, а все остальные различны.

Цикл — замкнутая цепь. Для орграфов цикл называется контуром.

Цикл (простой цикл) в орграфе — это простой путь, который начинается и заканчивается в одной и той же вершине.

Путь – это цепь, все вершины которой (за исключением, быть может, начальной и конечной) различны.

Путь — последовательность рёбер (в неориентированном графе) и/или дуг (в ориентированном графе), такая, что конец одной дуги (ребра) является началом другой дуги (ребра). Или последовательность вершин и дуг (рёбер) в которой каждый элемент инцидентен предыдущему и последующему. Может рассматриваться как частный случай маршрута.

Путь в орграфе — это последовательность вершин v₁, v₂, …, v_n, для которой существуют дуги v₁ → v₂, v₂ → v₃, …, v_n-1 → v_n. Говорят, что этот путь начинается в вершине v₁, проходит через вершины v₂, v₃, …, _vn-1, и заканчивается в вершине v_n.

Вес ребра — значение, поставленное в соответствие данному ребру взвешенного графа. Обычно, вес — вещественное число, в таком случае его можно интерпретировать как «длину» ребра.

Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).

Граф называют связным, если из каждой его вершины существует путь в любую другую его вершину. Другими словами, граф - связным, если для любой пары его вершин существует соединяющая их простая цепь, или, если из любой его вершины можно прийти к любой другой.

Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер.

Полным графом называется граф, в котором для каждой пары вершин v₁,v₂, существует ребро, инцидентное v₁ и инцидентное v₂ (каждая вершина соединена ребром с любой другой вершиной)

Для представления данных в алгоритмах на дискретных структурах часто используются графы, которые называются деревьями.

Деревом называют связный граф, не содержащий циклов (между любой парой вершин которого существует ровно один путь).

На рис. 6.8 показано, так называемое, корневое дерево. Одна из вершин корневого дерева (вершина 1) выделена, ее называют корнем дерева. Оставшиеся вершины разбиты на поддеревья (поддерево с вершинами 2,5,6 и поддерево 4,7,8,9). Вершины 5,6,3,7,8,9 называют листьями дерева. Несвязный неорграф, компонентами которого являются деревья, называют лесом.

Если граф связный, но не является деревом, в нем всегда можно выделить часть, включающую все вершины и образующую дерево. Такую часть графа называют остовом графа. Если граф несвязен, то можно превратить в дерево каждую его компоненту. Полученная совокупность деревьев носит название остовного леса.

Вообще говоря, в графе можно выделить несколько различных остовов. Каждый из них будет являться деревом, включающим все вершины графа, а следовательно, число ребер любом из остовов будет на единицу меньше числа вершин графа. Если выделен какой-либо остов, то все ребра графа, не вошедшие в этот остов, образуют коостов, соответствующий данному остову.

Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом. Другими словами — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.

Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном, взвешенном, неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

Пример минимального остовного дерева в графе. Числа на ребрах обозначают вес ребер.

Компонента связности графа — некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.

Ребро G называется безопасным, если для некоторой компоненты F это ребро является самым лёгким из всех рёбер, соединяющих вершины этой компоненты с оставшимися вершинами.

Допустим, есть n городов, которые необходимо соединить дорогами, так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Разрешается строить дороги между заданными парами городов и известна стоимость строительства каждой такой дороги. Требуется решить, какие именно дороги нужно строить, чтобы минимизировать общую стоимость строительства.

Эта задача может быть сформулирована в терминах теории графов как задача о нахождении минимального остовного дерева в графе, вершины которого представляют города, рёбра — это пары городов, между которыми можно проложить прямую дорогу, а вес ребра равен стоимости строительства соответствующей дороги.

Приведем еще один пример практического применения теории графов.

На строительном участке нужно создать телефонную сеть, соединяющую все бытовки. Для того, чтобы телефонные линии не мешали строительству, их решили проводить вдоль дорог. Схема участка изображена на рисунке 1, где бытовкам соответствуют вершины графа и указаны длины дорог между ними.

Рис. 1

Каким образом провести телефонные линии, чтобы их общая длина была минимальной?

Схему участка можно естественным образом принять за граф G. Искомая телефонная сеть будет представлять собой минимальное остовное дерево (МОД) графа G.

Алгоритм Крускала

Алгоритм Крускала (или алгоритм Краскала) — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые описан Джозефом Крускалом в 1956 году.

Алгоритм Крускала объединяет вершины графа в несколько связных компонент, каждая из которых является деревом. На каждом шаге из всех ребер, соединяющих вершины из различных компонент связности, выбирается ребро с наименьшим весом. Для этого в алгоритме Крускала все ребра графа G перебираются по возрастанию веса. Для очередного ребра проверяется, не лежат ли концы ребра в разных компонентах связности, и если это так, ребро добавляется, и компоненты объединяются.

Построение начинается с выбора кратчайшего ребра е₁ в G. На каждом последующем шаге будем выбирать из оставшихся ребро минимальной длины, не образующее цикла с ранее выбранными ребрами. Если имеется несколько таких ребер одинаковой длины, то можно выбрать любое из них. Процесс заканчивается построением остовного дерева.

Рис. К1. Начальная фаза. Минимальный покрывающий лес пуст

Рис. К2. Перебираем ребра в порядке возрастания веса: первое ребро с весом 2. Добавляем его.

Рис. К3. Следующее безопасное ребро с весом 6. Добавляем его.

Рис. К4. Рис. К5. Рис. К6.

Рис. К7.

Рис. К8. Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.

Сетевое планирование – метод управления, основанный на использовании математического аппарата теории графов и системного подхода для отображения и алгоритмизации комплексов взаимосвязанных работ, действий или мероприятий для достижения четко поставленной цели.

Метод сетевого планирования и управления является методом решения задач исследования операций, в которых необходимо оптимально распределить сложные комплексы работ (например, строительство большого промышленного объекта, выполнение сложного проекта и т.п.). Метод, система ПЕРТ – оценка программ и способ проверки, возник в 1958 г. в США, затем быстро был признан во всём мире, в том числе и в СССР.

Методы СПУ используются при планировании сложных комплексных проектов, например, таких как:

− строительство и реконструкция каких-либо объектов;

− выполнение научно-исследовательских и конструкторских работ;

− подготовка производства к выпуску продукции;

− перевооружение армии;

− развертывание системы медицинских или профилактических мероприятий.

Характерной особенностью таких проектов является то, что они состоят из ряда отдельных, элементарных работ. Они обуславливают друг друга так, что выполнение некоторых работ не может быть начато раньше, чем завершены некоторые другие.

Например, укладка фундамента не может быть начата раньше, чем будут доставлены необходимые материалы; эти материалы не могут быть доставлены раньше, чем будут построены подъездные пути; любой

этап строительства не может быть начат без составления соответствующей технической документации и т.д.

СПУ состоит из трех основных этапов.

1. Структурное планирование.

2. Календарное планирование.

3. Оперативное управление.

Структурное планирование начинается с разбиения проекта на четко определенные операции, для которых определяется продолжительность. Затем строится сетевой график, который представляет взаимосвязи работ проекта. Это позволяет детально анализировать все работы и вносить улучшения в структуру проекта еще до начала его реализации.

Календарное планирование предусматривает построение календарного графика, определяющего моменты начала и окончания каждой работы и другие временные характеристики сетевого графика. Это позволяет, в частности, выявлять критические операции, которым необходимо уделять особое внимание, чтобы закончить проект в директивный срок. Во время календарного планирования определяются временные характеристики всех работ с целью

проведения оптимизации сетевой модели, которая улучшает эффективность использования какого-либо ресурса.

В ходе оперативного управления используются сетевой и календарных графики для составления периодических отчетов о ходе выполнения проекта. При этом сетевая модель может подвергаться оперативной корректировке, вследствие чего будет разрабатываться новый календарный план остальной части проекта.

Сущность метода сетевого планирования и управления (СПУ) заключается в особом моделировании исследуемого процесса, а именно – создаётся информационно-динамическая модель задачи.

В качестве такой модели в методе СПУ используется графическая модель в

виде сетевого графика. Весь комплекс операций в модели расчленён на отдельные, чётко определённые работы. Сетевой график изображается в виде ориентированного графа (множество вершин, соединённых направленными дугами).

Основными понятиями сетевых моделей являются понятия события и работы.

Работа – это некоторый процесс, приводящий к достижению определенного результата и требующий затрат каких-либо ресурсов, имеет протяженность во времени.

Термин «работа» может иметь следующие значения:

1. действительная работа, требующая затрат времени и ресурсов на определённую операцию;

2. «ожидание» – т.е. процесс, не требующий затрат труда, но занимающий время (например, процесс отвердения бетона, высыхание краски и т.п.);

3. фиктивная работа, которая указывает на логическую связь между двумя или несколькими операциями, не требующая ни затрат времени, ни ресурсов.

Она изображается на графике пунктирной линией (стрелкой) и указывает на то, что начало последующей операции, зависит от результатов предыдущей.

Событие – момент времени, когда завершаются одни работы и начинаются другие. Событие представляет собой результат проведенных работ и, в отличие от работ, не имеет протяженности во времени. Например, фундамент залит бетоном, старение отливок завершено, комплектующие поставлены, отчеты сданы и т.д.

Таким образом, начало и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями. Поэтому для идентификации конкретной работы используют код работы (i, j), состоящий из номеров начального (i-го) и конечного (j-го) событий, например (2,4); (3,8); (9,10).

На этапе структурного планирования взаимосвязь работ и событий изображаются с помощью сетевого графика, где работы изображаются стрелками, которые соединяют вершины, изображающие события. Работы, выходящие из некоторого события не могут начаться, пока не будут завершены все операции, входящие в это событие.

Событие, не имеющее предшествующих ему событий, т.е. с которого начинается проект, называют исходным событием.

Событие, которое не имеет последующих событий и отражает конечную цель проекта, называется завершающим.

Основная цель сетевого планирования - сокращение до минимума продолжительности проекта. Задача сетевого планирования состоит в том, чтобы графически, наглядно и системно отобразить и оптимизировать последовательность и взаимозависимость работ, действий или мероприятий, обеспечивающих своевременное и планомерное достижение конечных целей.

Для отображения и алгоритмизации тех или иных действий или ситуаций используются экономико-математические модели, которые принято называть сетевыми моделями, простейшие из них - сетевые графики. С помощью сетевой модели руководитель работ или операции имеет возможность системно и масштабно представлять весь ход работ или оперативных мероприятий, управлять процессом их осуществления, а также маневрировать ресурсами.

Наиболее распространенными направлениями применения сетевого планирования являются:

• целевые научно-исследовательские и проектно-конструкторские разработки сложных объектов, машин и установок, в создании которых принимают участие многие предприятия и организации;

• планирование и управление основной деятельностью разрабатывающих организаций;

• планирование комплекса работ по подготовке и освоению производства новых видов промышленной продукции;

• строительство и монтаж объектов промышленного, культурно-бытового и жилищного назначения;

• реконструкция и ремонт действующих промышленных и других объектов;

• планирование подготовки и переподготовки кадров, проверка исполнения принятых решений, организация комплексной проверки деятельности предприятий, объединений, строительно-монтажных организаций и учреждений.

Использование методов сетевого планирования способствует сокращению сроков создания новых объектов на 15-20%, обеспечению рационального использования трудовых ресурсов и техники.