Читайте также:
|
Среди большого множества задач на графах можно встретить следующую: как изобразить некий граф на плоскости так, чтобы никакие два его ребра не пересекались, т.е. нарисовать исходный граф как граф без самопересечений. Такую задачу принято называть задачей о плоской укладке графа.
Плоский граф — это граф, нарисованный таким образом, что его ребра не пересекаются. Говорят, что граф допускает плоскую укладку, если его можно нарисовать как плоский. Также плоские графы называют планарными.
Пример плоского графа
Для плоской укладки графа и попутной проверки, планарен ли он, удобно пользоваться гамма-алгоритмом.
Гамма-алгоритм
На вход подаются графы, обладающие следующими свойствами:
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) Пока множество сегментов непусто:
a) Для каждого сегмента S найти множество Γ(S). Если существует сегмент S, для которого |Γ(S)| = 0, то граф не планарный, конец.
b) Выбираем один из сегментов с минимальным числом, вмещающих его граней.
c) Выбираем одну из подходящих граней для выбранного сегмента.
d) В данном сегменте выбираем цепь между двумя контактными вершинами и укладываем ее в выбранной грани. Учтем изменения в структуре сегментов и перейдем к п. a).
3) Построена плоская укладка G′ исходного графа G, конец.
Практическое применение алгоритма решения задачи
Область применения алгоритма для решения этой задачи весьма обширна. Хорошим примером может послужить проблема изготовления электронных микросхем. Электрические цепи печатным способом наносятся на плату из изолирующего материала. Так как наносимые цепи не изолированы, то они не должны пересекаться. Отсюда вытекает вопрос, как расположить контакты на схеме, чтобы можно было без пересечений нанести цепи на плату. А если так сделать нельзя, то каким минимальным числом плат (слоевграфа) можно обойтись.
Дата добавления: 2015-02-16; просмотров: 146 | Поможем написать вашу работу | Нарушение авторских прав |