АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. IDL-описаниеи библиотека типа
  2. II. ОПИСАНИЕ МАССОВОЙ ДУШИ У ЛЕБОНА
  3. IX. ПАДЕНИЕ И СМЕРТЬ ГРАФА РОБЕРТА
  4. XI. Описание заболевания
  5. А — одностороннее боковое освещение; б — двустороннее боковое освещение; в — верхнее освещение; г — комбинированное освещение: 1 — уровень рабочей плоскости
  6. Алгоритм нахождения сильных компонент графа
  7. Алгоритм укладки графа на плоскости
  8. Алгоритмы на графах
  9. Анализ основных конкурентов (схема и описание)
  10. Аналитическая геометрия на плоскости
  11. Аналитическое описание движения
  12. Античное историческое сознание и историописание

 

0. Выберем некоторый простой цикл С графа G и уложим его на плоскости; положим G'=С.

1. Найдем грани графа G' и сегменты относительно G'. Если множество сегментов пусто, то перейдем к п. 7.

2. Для каждого сегмента S определим множество Г(S).

3. Если существует сегмент S, для которого Г(S)=Æ, то граф G непланарен. Конец. Иначе перейти к п. 4.

4. Если существует сегмент S, для которого имеется единственная допустимая грань Г, то перейти к п. 6. Иначе – к п. 5.

5. Для некоторого сегмента S (Г(S)>1) выбираем произвольную допустимую грань Г.

6. Поместить произвольную a–цепь L ÎS в грань Г; заменить G' на G'ÈL и перейти к п. 1.

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

 

Проиллюстрируем работу алгоритма на примерах.

Пример 1. Для графа G, изображенного на рис 11, построить его уклад­ку на плоскости.

Решение. Уложим сначала цикл С =(1, 2, 3, 4, 1), который разбивает плоскостьна две грани Г1 в Г2. На рис. 12 изображены граф G'=С и сегменты S1, S2, S3 относительно G'с контактными вершинами, обведенными кружками. Таккак Г(Si)={Г1, Г2} (i=1, 2, 3), то любую a-цепь произвольного сегмента можно укладывать в любую допустимую для него грань. Поместим, например, a-цепь L = (2, 5, 4) в Г1. Возникает новый граф G' и его сегменты (рис. 13). При этом Г(S1) = {Г3}, Г(S2) = {Г1, Г2}, Г(S3) = {Г1, Г2, Г3}. Укладываем цепь L = (1, 5) в Г3 (рис. 14). Тогда Г(S1) = {Г1, Г2}, Г(S2) = {Г1, Г2}. Далее, уложим a-цепь L = (2, 6, 4) сегмента S1 в Г1 (рис. 15). В результате имеем Г(S1) = {Г5}, Г(S2) = {Г1, Г2, Г3}. Наконец, уложив ребро (6,3) в Г5, а ребро (2,4) - например, а Г1, получаем укладку графа G на плоскости (рис. 16).

 

1 2 3

 


6 5 4

 

Рис. 11

1 2 5 6 2

 


Г2 Г1

       
   
 
 

 


4 3 1 2 4 2 3 4 4

G' S1 S2 S3

Рис. 12

1 2 5 6 2

               
   
     
   
 
 
 

 


Г2 Г3 Г1

 

                       
   
           
 
 


4 3 1 2 3 4 4

G' S1 S2 S3

Рис. 13

 

1 2 6 2

Г4

Г2 Г3 Г1

               
       


4 3 2 3 4 4

G' S1 S2

Рис. 14

1 2 6 2

Г4

Г2 Г3 Г1

5 6

Г5

4 3 3 4

G' S1 S2

Рис. 15

1 2

 

5 6

 

4 3

G'

Рис. 16

Пример 2. Для графа К3,3, изображенного на рис.17, построить, если это возможно, его уклад­ку на плоскости.

Решение цикл G' и сегменты относительно этого цикла изображены на рис. 18. При этом Г(Si) = {Г1, Г2} (i=1,2,3). Помещает S1 в грань Г2. Тогда S2 необходимо поместить в грань Г1 (рис. 19). Поскольку Г(S1)=Æ, то К3,3 - непланарный граф.

 

1 2 3

 
 

 


6 5 4

Рис. 17

1 6 3 1 2 3

               
       

 


Г1 Г2

 

               
       
 
 


5 2 4 4 6 5

G' S1 S2 S2

Рис. 18

 
 


1 6 3 3

       
   
 

 

 


5 2 4 5

G' S1

Рис. 19


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.009 сек.)