Поиск минимального остовного дерева графа

Введение

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

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

Задача о минимальном остовном дереве

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

1. Первым ребром остова является ребро, имеющее самый маленький вес в начальном графе.
2. В случае, если в остове уже есть i (i

Рисунок 1. Задача о минимальном остовном дереве. Автор24 — интернет-биржа студенческих работ

Рисунок 2. Минимальный остов. Автор24 — интернет-биржа студенческих работ

Рассмотрим пример нахождения минимального остовного дерева графа, изображённого на рисунке один. Формирование остова следует начать с ребра, имеющего наименьший вес. Таких рёбер два, ($V_1, V_3$) и ($V_2, V_5$), выбираем первый вариант. Рёбра присоединяются к остову в следующей очерёдности: ($V_1, V_3$), ($V_2, V_5$), ($V_1, V_2$), ($V_4, V_5$). И тогда суммарная весовая характеристика остова будет:

$W = 1 + 2 + 1 + 4 = 8$.

Следует отметить, что рёбра ($v_2, v_3$), ($v_1, v_5$) не вошли в состав остова, хотя и обладают меньшим весом чем ребро ($v_4, v_5$), поскольку их присутствие приводит к образованию циклов с рёбрами, уже находящимися в составе остова.

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

Очень много практических задач возможно свести к нахождению самого маленького расстояния между двумя вершинами (или некоторым количеством пар вершин) в заданном графе (или орграфе). Задача может быть поставлена в разных вариациях:

1. Найти маршрут с самым маленьким числом проходимых вершин (например, доехать из одного населённого пункта в другой с минимальным количеством пересадок).
2. Найти маршрут с наименьшей суммарной дистанцией, если все рёбра имеют неотрицательный вещественный вес (в числовом выражении).
3. Найти маршрут с наименьшей суммарной дистанцией, если возможно наличие рёбер, в том числе, и с отрицательным весом.

Расположение «центров», которые покрывают требуемую зону

Примерами задач такого типа могут служить:

1. Необходимо разместить телевизионные или радиопередающие системы для покрытия их вещанием определённой зоны (территории).
2. Необходимо разместить военные базы для контроля заданной территории.
3. Необходимо разместить торговые центры (точки) для обслуживания определённого района.

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

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

Задача планирования производства

Практическими примерами задач этого типа является планирование производства в организациях различных промышленных сфер. Рассмотрим пример. Необходимо изготовить n товаров на определённом промышленном оборудовании. При этом для одного оборудования при переходе с производства старых товаров на производство новых товаров его нужно перенастраивать, а для других товаров этого делать не требуется. Цена переналадки оборудования одна и та же вне зависимости от типа товаров. Необходимо определить цикл последовательного выполнения операций, которые не требуют выполнять перенастройку оборудования, или доказать, что это невозможно. Для решения этой задачи, требуется выстроить орграф, с вершинами, соответствующими наименованиям товаров. Если существует дуга (n, v), то это значит, что товар v возможно делать после товара n и перенастройка оборудования не требуется. В этом случае задача состоит в определении одного или множества возможных гамильтоновых циклов в данном орграфе.

Задача раскраски графа

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

Рисунок 3. Раскраска графа. Автор24 — интернет-биржа студенческих работ

Требуется определить хроматическое число графа, изображённого на рисунке 2. Выполним раскраску вершин 1, 3, 5, 7 в красные цвета. Вершины 2, 6, 8 раскрасим жёлтым цветом, а вершину 4 выкрасим зелёным. Вычисления хроматического числа дали итог равный трём.