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

 

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, изображенного на рис 3, построить его укладку на плоскости.

Решение. Уложим сначала цикл С =(1, 2, 3, 4, 1), который разбивает плоскостьна две грани Г₁ в Г₂. На рис. 4 изображены граф G'=С и сегменты S₁, S₂, S₃ относительно G'с контактными вершинами, обведенными кружками. Таккак Г(S_i)={Г₁, Г₂} (i=1, 2, 3), то любую a-цепь произвольного сегмента можно укладывать в любую допустимую для него грань. Поместим, например, a-цепь L = (2, 5, 4) в Г₁. Возникает новый граф G' и его сегменты (рис. 5). При этом Г(S₁) = {Г₃}, Г(S₂) = {Г₁, Г₂}, Г(S₃) = {Г₁, Г₂, Г₃}. Укладываем цепь L = (1, 5) в Г₃ (рис. 6). Тогда Г(S₁) = {Г₁, Г₂}, Г(S₂) = {Г₁, Г₂}. Далее, уложим a-цепь L = (2, 6, 4) сегмента S₁ в Г₁ (рис. 7). В результате имеем Г(S₁) = {Г₅}, Г(S₂) = {Г₁, Г₂, Г₃}. Наконец, уложив ребро (6,3) в Г₅, а ребро (2,4) - например, а Г₁, получаем укладку графа G на плоскости (рис. 8).

Рис. 3.

Рис. 4.

Рис. 5.

Рис. 6.

Рис. 7.

               

Рис. 8.

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

Решение: цикл G' и сегменты относительно этого цикла изображены на рис. 10. При этом Г(S_i) = {Г_1, Г₂} (i=1,2,3). Помещает S₁ в грань Г₂. Тогда S₂ необходимо поместить в грань Г₁ (рис. 11). Поскольку Г(S₁)=Æ, то К_3,3 - непланарный граф.

Рис. 9.

Рис. 10.

Рис. 11.

Контрольные вопросы:

1. Плоские графы.

2. Планарные графы.

3. Решить задачи:

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

а)

б)

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

а)                                                  б)

 

 

в)                                               г)

 

 

 

Практические занятия

1. Практическое занятие №14 «Метрические характеристики графов»

1. Практическое занятие №15 «Построения остовного дерева»

КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ ДИСЦИПЛИНЫ

Вопросы к экзамену

 

ПРИМЕРНЫЙ ПЕРЕЧЕНЬ ВОПРОСОВ ДЛЯ ПОДГОТОВКИ К СДАЧЕ ЭКЗАМЕНА ПО ДИСЦИПЛИНЕ «ТЕОРИЯ ВЕРОЯТНОСТЕЙ И МАТЕМАТИЧЕСКАЯ СТАТИСТИКА»

Теоретическая часть:

Раздел 1. Основные понятия комбинаторики

Тема 1.1. Основные понятия комбинаторики

1. Основные комбинаторные объекты. Размещения. Примеры

2. Основные комбинаторные объекты. Сочетания. Примеры

3. Основные комбинаторные объекты. Перестановки. Примеры.

4. Два основных принципа комбинаторики

 

Раздел 2. Основы теории вероятностей