Обзор алгоритмов на графах

Алгоритм Прима

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

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

Приведем  наиболее общую cхему алгоритма:

1. Множество остовных вершин – исходная веришны
2. Множество оставшихся  - все вершины за исключением исходной.
3. Пока множество оставшихся не пусто:

1. Ищем ребро соединяющее множество остовных и множество оставшихся и имеющее наименьший вес.
2. Для найденного ребра, вершину принадлежащую множеству оставшихся:

• Вычеркиваем из множества оставшихся.
• Добавляем к множеству остовных.

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

Искомые ребра  соединяют вершины. Поэтому возможны две стратегии построения. Можно  идти от вершин и для каждой из них  искать минимальное ребро (как это  сделано в алгоритме Прима) а  можно для каждого ребра выяснять можно ли его включить в строящееся дерево. Алгоритм Краскала предлагает делать это следующим образом. Во-первых, ребра графа пронумеровываем в порядке возрастания весов. Затем для каждого ребра начиная с первого проверяем соединяет или нет оно две несвязные вершины, если да, то его можно включить в остовное дерево. Ясно, что если мы имеем V вершин, то работа алгоритма начинается с V несвязных компонент графа (пока из графа все ребра исключаем). Для того, чтобы их связать необходимо найти V-1 ребро.

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

Схема алгоритма:

1. Множество ребер H искомого остовного дерева полагаем пустым.
2. Формируем множество , элементами которого являются множества вершин, соответствующих компонентам исходного остовного леса (множество изолированных вершин исходного графа). Каждая такая компонента состоит из единственной вершины.
3. Сортируем множество ребер Е исходного графа по возрастанию весов и формируем очередь Q, элементами которого являются ребра исходного графа.
4. Если множество содержит более одного элемента (остовной лес состоит из нескольких компонент) и очередь Q не пуста, то переходим на шаг 5, иначе – на шаг 7.
5. Извлекаем из очереди Q ребро е. Если его концы принадлежат различным множествам , из , то переходим на шаг 6, иначе – отбрасываем ребро и переходим на шаг 4.
6. Обьединяем множества вершин , (полагая ), удаляем множества , из множества и добавляем в множество W. Добавляем ребро е в множество Н. Возвращаемся на шаг 4.
7. Множество H есть множество ребер полученного остовного дерева.

 

Практическое применение алгоритмов решения задачи

 

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

                                            Минимальное остовное дерево может нагляднее представить эволюцию животных видов.

 

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

 

Задача плоской  укладки

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

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

Пример плоского графа

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

Гамма-алгоритм

На вход подаются графы, обладающие следующими свойствами:

1. граф связный;
2. граф имеет хотя бы один цикл;
3. граф не имеет мостиков, т. е. ребер, после удаления которых граф распадается на две компонеты связности.

Если нарушено свойство (1), то граф нужно укладывать отдельно по компонентам связности. Если нарушено свойство (2), то граф — дерево и нарисовать его плоскую укладку тривиально.

Инициализация алгоритма  производится так: выбираем любой простой  цикл и получаем две грани: Γ1 —  внешнюю и Γ2 — внутреннюю.

Обозначим выбранный цикл как G′. На каждом шаге будем строить  множество сегментов. Каждый сегмент S относительно уже построенного графа G′ представляет собой одно из двух:

1. ребро, оба конца которого принадлежат G′, но само оно не принадлежит G′;
2. связную компоненту графа G – G′, дополненную всеми ребрами графа G, один из концов которых принадлежит связной компоненте, а второй из графа G′.

Те вершины, которые одновременно принадлежат G′ и какому-то сегменту, назовем контактными.

Если все контактные вершины  сегмента S имеют номера вершин какой-то грани Γ, то мы будем говорить, что  грань Γ вмещает этот сегмент  и обозначать S⊂Γ. Может быть имеется не одна такая грань, вмещающая сегмент S, множество таких граней обозначим Γ(S), а их число |Γ(S)|.

Общий шаг алгоритма следующий: обозреваются все сегменты и определяются числа |Γ()|. Если хоть одно из них равно 0, то граф не планарен. Иначе, выбираем сегмент, для которого число |Γ(S)| минимально, или один из множества, если таких сегментов несколько. В этом сегменте найдем цепь между двумя контактными вершинами и уложим ее в любую из граней множества Γ(S), совместив контактные вершины сегмента с соответствующими вершинами грани. При этом данная грань разобьется на две. Уже уложенная часть графа G′ по количеству ребер и вершин увеличится, а сегмент, из которого вынута цепь, исчезнет или развалится на меньшие с новыми контактными вершинами, ведущими к вершинам G′.

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

Схема алгоритма:

1. Выберем любой простой цикл C исходного графа G; изобразим его на плоскости в виде грани, которую примем за уже уложенную часть G′; сформируем сегменты ; если множество сегментов пусто, то перейти к п. 3.
2. Пока множество сегментов непусто:

1. Для каждого сегмента S найти множество Γ(S). Если существует сегмент S, для которого |Γ(S)| = 0, то граф не планарный, конец.
2. Выбираем один из сегментов с минимальным числом, вмещающих его граней.
3. Выбираем одну из подходящих граней для выбранного сегмента.
4. В данном сегменте выбираем цепь между двумя контактными вершинами и укладываем ее в выбранной грани. Учтем изменения в структуре сегментов и перейдем к п. a).

3. Построена плоская укладка G′ исходного графа G, конец.

 

Практическое применение алгоритма решения задачи

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

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

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

(Графы, рассматриваемые  далее, являются неориентированными  и не имеют петель)

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

Граф, раскрашенный таким образом называется r-хроматическим, а число цветов, необходимых для такой раскраски графа, называется хроматическим числом графа G и обозначается .

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

Метод неявного перебора

Схема алгоритма:

Предположим, что множество вершин как-то упорядочено и

  — i-я вершина этого множества. Тогда первоначальная допустимая раскраска может быть получена так:

 

1. Окрасить  в цвет 1.
2. Каждую из оставшихся вершин окрашивать последовательно: вершина окрашивается в цвет с наименьшим возможным «номером» (т. е. выбираемый цвет должен быть первым в данном упорядочении цветом, не использованным при окраске какой-либо вершины, смежной ).

Данный алгоритм можно ускорить, используя следующие  замечания:

1. При любом упорядочении вершин допустимые цвета j для вершины удовлетворяют условию j ≤ i.
2. С вычислительной точки зрения выгодно размещать вершины так, чтобы первые вершины образовывали максимальную клику графа. Тогда все вершины, входящие в эту клику будут окрашены в цвет 1 и алгоритм может закончить работу раньше.

 

Приближенный алгоритм

В этом простейшем из методов вершины вначале располагаются  в порядке невозрастания их степеней.

Описание  алгоритма:

Первая вершина  окрашивается в цвет 1. Затем список вершин просматривается сверху вниз (по невозрастанию степеней) и в цвет 1 окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Потом возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет 2 и снова просматриваем список вершин сверху вниз, окрашивая в цвет 2 любую неокрашенную вершину, которая не соединена ребром с другой, уже окрашенной в цвет 2 вершиной. Аналогично действуем с цветами 3, 4 и т. д., пока не будут окрашены все вершины. Число использованных цветов будет тогда приближенным значением хроматического числа графа.

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

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

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

Применение алгоритмов решения  задачи о раскраске графа на практике:

 

• Теория расписаний

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

• Распределение ресурсов

Пусть для выполнения каких-то n работ надо распределить m имеющихся в наличии ресурсов. Считаем, что каждая из работ выполняется за некоторый (одинаковый для всех работ) промежуток времени и что для выполнения i-й работы требуется подмножество ресурсов Si.