Алгоритм плоской укладки

Алгоритм укладки гр. На пл-ти

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

гр G новой цепи L

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

ОПР. Cегментом от-но = () – подграф гр. G=(V,E) cлед. 2-х видов

1.)e=(v,u) E: e , v,u

2.) связная комп-а гр G\ , дополн-я всеми ребрами графа G, инцид-и вершинам взятой комп-ы и концами этих ребер.

ОПР. Вершина v сегмента – контактная, если v . Т.к. - плоский, то он разб-м пл-ю на грани.

ОПР. Допустимой гранью для сег. от-но - грань Г (гамма) гр. сод-я все контактные вершины сег-та

Г( – мн-во допустимых граней для . Для непланарных графов может Г(G) =

Рассмотрим простую цепь L сегмента ,содержащую 2 разл. Контакт.вершины, и не содержащ. Других контактных вершин, такие цепи назыв - цепями. Всякая -цепь может быть уложена в любую грань, допустимую для данного сегмента.

ОПР. 2 cегм. G1 и G2 от-но -конфликтующие, если

1.) =Г(G1) Г(G2)= 2.) 2 -цепи, L1 G1, L2 G2, которые без

Нельзя уложить одновременно ни в какую грань Г

Пусть G-плоская укладка нек-ого подграфа гр. G. Для каждого сег , от-но находим мн-во допустимых граней.

Тогда могут быть только 3 случая(и только 3)

1.) сегм для которого Г( = . В этом случае G не планарен

2.) нек-ого сегмента ! Допуст. Грань Г. Тогда можно расположить любой сег. в грани Г, при этом грань Г разобьется на 2 грани

3.) мн-ва |Г()| 2. Для сегмента в этом случае можно расположить -цепь в любой допустимой грани

Шаг 1. Выбираем любой простой цикл Cгр. G. Этот цикл укладывается на плоскости и = C

Шаг 2. Находим все грани гр. и все сегменты от-но Если мн-во сегментов пусто то переходим на шаг 7. Т.епостр-а укладка графа Gна плоскости

Шаг 3. Для каждого сегмента от-но определяем мн-во допустимых граней Г(). Если найдется сегмент для которого Г(, то исходный граф Gне планарен

Конец алгоритма, иначе шаг 4.

Шаг 4.Если сущ. Сегмент для которого имеется единственная доп-я грань Г, то происходит переход на шаг 6. Иначе шаг 5.

Шаг 5. Для нек-госег-та , для которого мощность мн-ва|Г()|> 1

Выбираем произвольную доп. Грань

Шаг 6. Произвольная -цепь (L) сегмента помещается в грань Г. меняется на L и происходит переход к шагу 2.

Шаг 7. Пост-а укладка грG на плоскости. Конец алгоритма

Пример

Дан граф G. Выяснить, планарен ли он, в случае непланарности найти толщину и искаженность

V1 V2 V3 V4 шаг1. Выберем простой цикл

С = { } Он разбивает плоскость на 2 грани Г1, Г2

V8 V7 V6 V7 Пусть = С = () Шаг 2 Нарисуем = С и сегменты. исходного графа G от-но сегменты V1 V2 V3 V4

Г2 Г1

V8 V7 V6 V7

Контактные вершины – O

Г()={Г1,Г2}, i=1,2,3,4

Дата добавления: 2015-10-28